International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Lower Bounds on Black-Box Ring Extraction

Tibor Jager
Andy Rupp
Search ePrint
Search Google
Abstract: The black-box ring extraction problem is the problem of extracting a secret ring element from a black-box by performing only the ring operations and testing for equality of elements. An efficient algorithm for the black-box ring extraction problem implies the equivalence of the discrete logarithm and the Diffie-Hellman problem. At the same time this implies the inexistence of secure ring-homomorphic encryption schemes. It is unknown whether the known algorithms for the black-box ring extraction problem are optimal. In this paper we derive exponential-time lower complexity bounds for a large class of rings satisfying certain conditions. The existence of these bounds is surprising, having in mind that there are subexponential-time algorithms for certain rings which are very similar to the rings considered in this work. In addition, we introduce a novel technique to reduce the problem of factoring integers to the black-box ring extraction problem, extending previous work to a more general class of algorithms and obtaining a much tighter reduction.
  title={Lower Bounds on Black-Box Ring Extraction},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Generic equivalence of discrete logarithm and Diffie-Hellman problems, ring-homomorphic encryption, generic ring algorithms, black-box ring extraction},
  note={ 14213 received 30 Nov 2008},
  author={Tibor Jager and Andy Rupp},