Paper 2008/156
On Black-Box Ring Extraction and Integer Factorization
Kristina Altmann, 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.
Note: This is an extended version of the paper with the same title that appeared in the proceedings of ICALP 2008.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Black Box Extraction ProblemInteger FactorizationHomomorphic Encryption
- Contact author(s)
- tibor jager @ rub de
- History
- 2008-07-06: last of 2 revisions
- 2008-04-08: received
- See all versions
- Short URL
- https://ia.cr/2008/156
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/156,
author = {Kristina Altmann and Tibor Jager and Andy Rupp},
title = {On Black-Box Ring Extraction and Integer Factorization},
howpublished = {Cryptology ePrint Archive, Paper 2008/156},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/156}},
url = {https://eprint.iacr.org/2008/156}
}
