IACR paper details
Title  On BlackBox Ring Extraction and Integer Factorization 

Booktitle  IACR Eprint archive 

Pages  

Year  2008 

URL  http://eprint.iacr.org/2008/156 

Author  Kristina Altmann 

Author  Tibor Jager 

Author  Andy Rupp 

Abstract 
The blackbox 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 DiffieHellman problem and (ii) the inexistence of secure ringhomomorphic encryption schemes.
In the special case of a finite field, Boneh/Lipton and Maurer/Raub showed that there exist algorithms solving the blackbox extraction problem in subexponential time. It is unknown whether there exist more efficient algorithms.
In this work we consider the blackbox extraction problem over finite rings of characteristic $n$, where $n$ has at least two different prime factors. We provide a polynomialtime reduction from factoring $n$ to the blackbox extraction problem for a large class of finite commutative unitary rings. Under the factoring assumption, this implies the inexistence of certain efficient generic reductions from computing discrete logarithms to the DiffieHellman problem on the one side, and might be an indicator that secure ringhomomorphic encryption schemes exist on the other side.


Search for the paper
@misc{eprint200817833,
title={On BlackBox Ring Extraction and Integer Factorization},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / Black Box Extraction Problem, Integer Factorization, Homomorphic Encryption},
url={http://eprint.iacr.org/2008/156},
note={ tibor.jager@rub.de 14066 received 7 Apr 2008, last revised 6 Jul 2008},
author={Kristina Altmann and Tibor Jager and Andy Rupp},
year=2008
}
Download a complete BibTeX file.