**On Black-Box Ring Extraction and Integer Factorization**

*Kristina Altmann and Tibor Jager and Andy Rupp*

**Abstract: **The black-box extraction problem over rings has (at least) two important interpretations in cryptography: An efficient algorithm for this problem implies (i) the equivalence of computing discrete logarithms and solving the Diffie-Hellman problem and (ii) the in-existence of secure ring-homomorphic encryption schemes.

In the special case of a finite field, Boneh/Lipton and Maurer/Raub showed that there exist algorithms solving the black-box extraction problem in subexponential time. It is unknown whether there exist more efficient algorithms.

In this work we consider the black-box extraction problem over finite rings of characteristic $n$, where $n$ has at least two different prime factors. We provide a polynomial-time reduction from factoring $n$ to the black-box extraction problem for a large class of finite commutative unitary rings. Under the factoring assumption, this implies the in-existence of certain efficient generic reductions from computing discrete logarithms to the Diffie-Hellman problem on the one side, and might be an indicator that secure ring-homomorphic encryption schemes exist on the other side.

**Category / Keywords: **public-key cryptography / Black Box Extraction Problem, Integer Factorization, Homomorphic Encryption

**Date: **received 7 Apr 2008, last revised 6 Jul 2008

**Contact author: **tibor jager at rub de

**Available format(s): **PDF | BibTeX Citation

**Note: **This is an extended version of the paper with the same title that appeared in the proceedings of ICALP 2008.

**Version: **20080706:134413 (All versions of this report)

**Short URL: **ia.cr/2008/156

[ Cryptology ePrint archive ]