How discreet is the discrete log?

ABSTRACT

Blum and Micali [4] showed how to hide one bit using the discrete logarithm function. In this paper we show how to hide c•loglog p bits for any constant c, where p is the modulus.

REFERENCES

• 1: L. Adleman, K. Manders, G. Miller, "On Taking Roots in Finite Fields", 18th FOCS (1977), 175-178.
• 2: L. Adleman, "A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography", 20th FOCS (1979), 55-60.
• 3: E. Berlekamp, "Factoring Polynomials Over Large Finite Fields" Mathematics of Computation, 24. (1970), 713-735.
• 4: M. Blum & S. Micali, "How To Generate Cryptographically Strong Sequences Of Pseudo Random Bits", 23rd FOCS (1982),112-117.
• 5: W. Diffie & M. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, IT-22, 6 (1976), 644-654.
• 6: James Finn, Probabilistic methods in number-theoretic algorithms and digital signature schemes, 1982
• 7: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 8: K. Ireland & M. Rosen, Elements of Number Theory, Bogden & Quigly, Inc., New York, 1972.
• 9: R. Lipton, "How to Cheat at Mental Poker", Unpublished Manuscript, 1979.
• 10: S. Pohlig & M. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance", IEEE Transactions on Information Theory, IT-24, 1 (1978), 106-110.
• 11: M. Rabin, "Probabilistic Algorithms in Finite Fields", SIAM Journal of Computing, 9 No. 2, (May 1980), 273-280.
• 12: A. Shamir, R. Rivest, L Adleman, "Mental Poker", MIT Technical Report (Feb. 1979).
• 13: A. Yao, "Theory and Applications of Trapdoor Functions", 23rd FOCS (1982), 80-91.
• 14: A. Yao, "Protocols for Secure Computations", 23rd FOCS (1982), 160-164.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Information hiding

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms