## CryptoDB

### Paper: Lower Bounds on Black-Box Ring Extraction

Authors: Tibor Jager Andy Rupp URL: http://eprint.iacr.org/2008/505 Search ePrint Search Google 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
}