Paper 2007/089
BlackBox Extension Fields and the Inexistence of FieldHomomorphic OneWay Permutations
Ueli Maurer and Dominik Raub
Abstract
The blackbox field (BBF) extraction problem is, for a given field $\F$, to determine a secret field element hidden in a blackbox which allows to add and multiply values in $\F$ in the box and which reports only equalities of elements in the box. This problem is of cryptographic interest for two reasons. First, for $\F=\F_p$ it corresponds to the generic reduction of the discrete logarithm problem to the computational DiffieHellman problem in a group of prime order $p$. Second, an efficient solution to the BBF problem proves the inexistence of certain fieldhomomorphic encryption schemes whose realization is an interesting open problems in algebrabased cryptography. BBFs are also of independent interest in computational algebra. In the previous literature, BBFs had only been considered for the prime field case. In this paper we consider a generalization of the extraction problem to BBFs that are extension fields. More precisely we discuss the representation problem defined as follows: For given generators $g_1,\ldots,g_d$ algebraically generating a BBF and an additional element $x$, all hidden in a blackbox, express $x$ algebraically in terms of $g_1,\ldots,g_d$. We give an efficient algorithm for this representation problem and related problems for fields with small characteristic (e.g. $\F=\F_{2^n}$ for some $n$). We also consider extension fields of large characteristic and show how to reduce the representation problem to the extraction problem for the underlying prime field. These results imply the inexistence of fieldhomomorphic (as opposed to only grouphomomorphic, like RSA) oneway permutations for fields of small characteristic.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 blackbox fieldsgeneric algorithms
 Contact author(s)
 d raub @ inf ethz ch
 History
 20070308: received
 Short URL
 https://ia.cr/2007/089
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/089, author = {Ueli Maurer and Dominik Raub}, title = {BlackBox Extension Fields and the Inexistence of FieldHomomorphic OneWay Permutations}, howpublished = {Cryptology ePrint Archive, Paper 2007/089}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/089}}, url = {https://eprint.iacr.org/2007/089} }