International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lower Bounds on Black-Box Ring Extraction

Authors:
Tibor Jager
Andy Rupp
Download:
URL: http://eprint.iacr.org/2008/505
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.
BibTeX
@misc{eprint-2008-18170,
  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},
  url={http://eprint.iacr.org/2008/505},
  note={ tibor.jager@rub.de 14213 received 30 Nov 2008},
  author={Tibor Jager and Andy Rupp},
  year=2008
}