Algorithms for black box fields and their application to cryptography
Authors: D. Boneh and R. Lipton
Abstract:
We introduce the notion of a black box field and discuss the problem
of explicitly exposing field elements given in a black box form. We
present several sub-exponential algorithms for this problem using a
technique due to Maurer. These algorithms make use of elliptic curves
over finite fields in a crucial way. We present three applications for
our results: (1) We show that any algebraically homomorphic
encryption scheme can be broken in expected sub-exponential time. The
existence of such schemes has been open for a number of years. (2) We
give an expected sub-exponential time reduction from the problem of
finding roots of polynomials over finite fields with low straight line
complexity (e.g. sparse polynomials) to the problem of testing
whether such polynomials have a root in the field. (3) We show that
the hardness of computing discrete-log over elliptic curves implies
the security of the Diffie-Hellman protocol over elliptic
curves. Finally in the last section of the paper we prove the
hardness of exposing black box field elements in a field of
characteristic zero.
Reference:
In Proceedings Crypto '96, Lecture Notes in Computer Science,
Vol. 1109, Springer-Verlag, pp. 283--297, 1996
Full paper: PostScript [first posted 11/1997 ]