Cryptology ePrint Archive: Report 2008/505

Lower Bounds on Black-Box Ring Extraction

Tibor Jager and Andy Rupp

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.

Category / Keywords: public-key cryptography / Generic equivalence of discrete logarithm and Diffie-Hellman problems, ring-homomorphic encryption, generic ring algorithms, black-box ring extraction

Date: received 30 Nov 2008

Contact author: tibor jager at rub de

Available formats: PDF | BibTeX Citation

Version: 20081202:020928 (All versions of this report)

Discussion forum: Show discussion | Start new discussion