Algorithms for black box fields and their application to cryptography

Authors: D. Boneh and R. Lipton

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.

In Proceedings Crypto '96, Lecture Notes in Computer Science, Vol. 1109, Springer-Verlag, pp. 283--297, 1996

Full paper: PostScript         [first posted 11/1997 ]