Advertisement
Published in:
2005 | OriginalPaper | Chapter
The RSA Group is Pseudo-Free
Author : Daniele Micciancio
Published in: Advances in Cryptology – EUROCRYPT 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 (TCC 2004).