Abstract
We introduce the notion of a black box field and present several algorithms for manipulating such fields. Black box fields arise naturally in cryptography and our algorithms have several cryptographic implications. First, our results show that any algebraically homomorphic cryptosystem can be broken in sub-exponential time. The existence of such cryptosystems was posed as an open problem in [12]. Second we show that over elliptic (or hyperelliptic) curves the hardness of computing discrete-log implies the security of the Diffie-Hellman protocol. This provable security of the Diffie-Hellman protocol over elliptic curves demonstrates an additional advantage of elliptic curve cryptosystems over conventional ones. Finally, we prove that manipulating black box fields over the rationals is as hard as factoring integers.
Supported in part by NSF CCR-9304718.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Abadi, J. Feigenbaum, “Secure circuit evaluation: a protocol based on hiding information from an oracle”, J. Cryptology, No. 2, 1990, pp. 1–12.
L. Adleman, J. DeMarrais, Ming-Deh Huang, “A sub-exponential algorithm for discrete logarithm over the rational subgroup of the Jacobian of large genus hyperelliptic curves over finite fields”, Proceedings of ANTS, 1994.
L. Babai, E. Szemerédi, “On the complexity of matrix group problems I”, Proceedings FOCS 1984, pp. 229–240.
J. Buchmann, H. Williams, “A key exchange system based on imaginary quadratic fields”, Journal of cryptography, vol. 1, no. 2, pp. 107–118, 1988.
E. Canfield, P. Erdös, C. Pomerance, “On a problem of Oppenheim concerning “Factorisatio Numerorum”, J. Number Theory 17, 1983, pp. 1–28.
H. Cohen, “A course in computational algebraic number theory”, Springer-Verlag, 1991.
I. Damgard, “On the randomness of Legendre and Jacobi sequences”, Proceedings of Crypto 1988, pp. 163–172.
H. Davenport, “On the distribution of quadratic residues (mod p)”, J. London Math. Soc., 8, 1933, pp. 46–52.
N. DeBruijn, “On the number of positive integers ≤ x and free of prime factors > y”, Indag. Math. 38, 1966, pp. 239–247.
B. den Boer, “Diffie-Hellman is as strong as discrete log for certain primes”, Proceedings of Crypto 1988, pp. 530–539.
W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
J. Feigenbaum, N. Merrirr, “Open Questions and summary of discussions”, Proceedings of DIMACS workshop on Distributed Computing and Cryptography, Vol. 2, 1989.
N. Koblitz, “A family of Jacobians suitable for discrete log cryptosystems”, Proceedings of Crypto 88, pp. 94–99.
N. Koblitz, “Elliptic curve cryptosystems”, Math. of comp., Vol. 48, 1987, pp. 203–209.
H. Lenstra Jr., “Factoring integers with elliptic curves”, Annals of Math. 126, 1987, pp. 649–673.
A. Lenstra, H. Lenstra Jr., M. Manasse, J. Pollard, “The number field sieve”, Proceedings of STOC 1990, pp. 564–572.
R. Lipton, “Straight line complexity and integer factorization”, First algorithmic number theory symposium, 1994.
U. Maurer, “Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms”, Proceedings of Crypto 1994, pp. 271–281.
U. Maurer, Y. Yacobi, “Non-interactive public-key cryptography”, EUROCRYPT 91, Lecture notes in computer science, Springer-Verlag, vol. 547, pp. 498–507, 1991.
K. McCurley, “A key distribution system equivalent to factoring”, Journal of cryptography, vol. 1, no. 2, 1988, pp. 95–105.
K. McCurley, “The discrete logarithm problem”, In cryptology and computational number theory, AMS lecture notes, C. Pomerance editor, 1989.
A. Menezes, S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field”, Proceedings of STOC 1991, pp. 80–89.
V. Miller, “Use of elliptic curves in cryptography”, Proceedings of Crypto 1985, pp. 417–426.
S. Pohlig, M. Hellman, “An improved algorithm for computing discrete logarithms over GF(p) and its cryptographic significance”, IEEE Trans. Inform. Theory, Vol. 24, 1978, pp. 106–110.
V. Nechaev, “Complexity of a determinate algorithm for the discrete logarithm”, Mathematical Notes, Vol. 55, No. 2, pp. 165–172, 1994.
R. Schoof, “Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p”, Math. of Comp., Vol. 44, no. 170, 1985, pp. 483–494.
V. Shoup, “Lower bounds for discrete logarithms and related problems”, Manuscript, 1995.
J. Silverman, “The arithmetic of elliptic curves”, Springer-Verlag, 1986.
M. Steele, A. Yao, “Lower bounds for algebraic decision trees”, J. of alg., Vol. 3, 1982, pp. 1–8.
S. Wolf, “Diffie-Hellman and Discrete Logarithms”, Thesis ETH Zurich, 1995.
Specifications for the digital signature standard, National Institute for Standards and Technology, Federal Information Processing Standard Publication XX, draft, August 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Lipton, R.J. (1996). Algorithms for Black-Box Fields and their Application to Cryptography. In: Koblitz, N. (eds) Advances in Cryptology — CRYPTO ’96. CRYPTO 1996. Lecture Notes in Computer Science, vol 1109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68697-5_22
Download citation
DOI: https://doi.org/10.1007/3-540-68697-5_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61512-5
Online ISBN: 978-3-540-68697-2
eBook Packages: Springer Book Archive