Nothing Special   »   [go: up one dir, main page]

skip to main content
article

The RSA Group is Pseudo-Free

Published: 01 April 2010 Publication History

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).

Cited By

View all
  • (2019)Digital Signature Schemes over the Ring Z[e2πi/5]Proceedings of the 3rd International Conference on Computer Science and Application Engineering10.1145/3331453.3361313(1-4)Online publication date: 22-Oct-2019

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology
Journal of Cryptology  Volume 23, Issue 2
April 2010
203 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2010

Author Tags

  1. Cryptographic assumptions
  2. Pseudo-free Abelian group
  3. Safe primes
  4. Strong RSA problem

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024

Other Metrics

Citations

Cited By

View all
  • (2019)Digital Signature Schemes over the Ring Z[e2πi/5]Proceedings of the 3rd International Conference on Computer Science and Application Engineering10.1145/3331453.3361313(1-4)Online publication date: 22-Oct-2019

View Options

View options

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media