Abstract | ||
---|---|---|
To prove or disprove the computational equivalence of solving the RSA problem and factoring integers is a longstanding open problem in cryptography. This paper provides some evidence towards the validity of this equivalence. We show that any efficient generic ring algorithm which solves the (flexible) low-exponent RSA problem can be converted into an efficient factoring algorithm. Thus, the low-exponent RSA problem is intractable w.r.t. generic ring algorithms provided that factoring is hard. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11935230_16 | ASIACRYPT |
Keywords | Field | DocType |
factoring integer,intractable w,longstanding open problem,low-exponent rsa problem,rsa problem,efficient factoring algorithm,computational equivalence,efficient generic ring algorithm,generic ring | Integer,Discrete mathematics,Open problem,Computer science,Cryptography,Algorithm,Theoretical computer science,Equivalence (measure theory),RSA problem,Factoring | Conference |
Volume | ISSN | ISBN |
4284 | 0302-9743 | 3-540-49475-8 |
Citations | PageRank | References |
14 | 0.70 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gregor Leander | 1 | 1287 | 77.03 |
Andy Rupp | 2 | 196 | 16.95 |