- Main
The RSA Group is Pseudo-Free
Published Web Location
https://doi.org/10.1007/s00145-009-9042-5Abstract
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).
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:
-
-
-
-
-
-
-
-
-
-
-
-
-
-