zbMATH — the first resource for mathematics

On black-box ring extraction and integer factorization. (English) Zbl 1155.94362
Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 437-448 (2008).
Summary: 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 show 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.
For the entire collection see [Zbl 1141.68001].

94A60 Cryptography
11Y05 Factorization
Full Text: DOI