Paper 2007/089

Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations

Ueli Maurer and Dominik Raub

Abstract

The black-box field (BBF) extraction problem is, for a given field $\F$, to determine a secret field element hidden in a black-box 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 Diffie-Hellman problem in a group of prime order $p$. Second, an efficient solution to the BBF problem proves the inexistence of certain field-homomorphic encryption schemes whose realization is an interesting open problems in algebra-based 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 black-box, 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 field-homomorphic (as opposed to only group-homomorphic, like RSA) one-way permutations for fields of small characteristic.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
black-box fieldsgeneric algorithms
Contact author(s)
d raub @ inf ethz ch
History
2007-03-08: received
Short URL
https://ia.cr/2007/089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/089,
      author = {Ueli Maurer and Dominik Raub},
      title = {Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.