The RSA Group is Pseudo-Free |
| |
Authors: | Daniele Micciancio |
| |
Affiliation: | 1. Department of Computer Science and Engineering, University of California at San Diego, La Jolla, CA, 92093, USA
|
| |
Abstract: | We prove, under the strong RSA assumption, that the group of invertible integers modulo the product of two safe primes is
pseudo-free. More specifically, no polynomial-time algorithm can output (with non negligible probability) an unsatisfiable
system of equations over the free Abelian group generated by the symbols g
1,…,g
n
, together with a solution modulo the product of two randomly chosen safe primes when g
1,…,g
n
are instantiated to randomly chosen quadratic residues. Ours is the first provably secure construction of pseudo-free Abelian
groups under a standard cryptographic assumption and resolves a conjecture of Rivest (Theory of Cryptography Conference—Proceedings
of TCC 2004, LNCS, vol. 2951, pp. 505–521, 2004). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|