IACR paper details
Title  BlackBox Extension Fields and the Inexistence of FieldHomomorphic OneWay Permutations 

Booktitle  IACR Eprint archive 

Pages  

Year  2007 

URL  http://eprint.iacr.org/2007/089 

Author  Ueli Maurer 

Author  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.


Search for the paper
@misc{eprint200713371,
title={BlackBox Extension Fields and the Inexistence of FieldHomomorphic OneWay Permutations},
booktitle={IACR Eprint archive},
keywords={foundations / blackbox fields, generic algorithms,},
url={http://eprint.iacr.org/2007/089},
note={ d.raub@inf.ethz.ch 13580 received 8 Mar 2007},
author={Ueli Maurer and Dominik Raub},
year=2007
}
Download a complete BibTeX file.