Name
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 [1] and Maurer/ Raub [2] 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 nhas at least two different prime factors. We provide a polynomial-time reduction from factoring nto 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-70583-3_36 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
factoring assumption,finite field,integer factorization,black-box ring extraction,black-box extraction problem,secure ring-homomorphic encryption scheme,diffie-hellman problem,finite ring,finite commutative unitary ring,efficient algorithm,certain efficient generic reduction,discrete logarithm,polynomial time,homomorphic encryption,diffie hellman | Conference | 2008 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.49 |
References | Authors | |
13 | 13 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| kristina altmann | 1 | 5 | 0.49 |
| Tibor Jager | 2 | 420 | 27.65 |
| Andy Rupp | 3 | 196 | 16.95 |
| david hutchison | 4 | 5 | 0.49 |
| Luca Aceto | 5 | 1125 | 101.87 |
| Ivan Damgård | 6 | 5851 | 431.52 |
| leslie ann goldberg | 7 | 1411 | 125.20 |
| magnus m halldorsson | 8 | 100 | 8.87 |
| anna ingolfsdottir | 9 | 5 | 0.49 |
| J. Kittler | 10 | 14346 | 1465.03 |
| jon m kleinberg | 11 | 5 | 0.49 |
| Friedemann Mattern | 12 | 2350 | 232.81 |
| john c mitchell | 13 | 5 | 0.49 |