Digital signatures from strong RSA without prime generation

David Cash, Rafael Dowsley, Eike Kiltz

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


We construct a signature scheme that is proved secure, without random oracles, under the strong RSA assumption. Unlike other efficient strong-RSA based schemes, the new scheme does not generate large prime numbers during signing. The public key size and signature size are competitive with other strong RSA schemes, but verification is less efficient. The new scheme adapts the prefix signing technique of Hohenberger and Waters (CRYPTO 2009) to work without generating primes.

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2015
Subtitle of host publication18th IACR International Conference on Practice and Theory in Public-Key Cryptography Gaithersburg, MD, USA, March 30 – April 1, 2015 Proceedings
EditorsJonathan Katz
Place of PublicationBerlin Germany
Number of pages19
ISBN (Electronic)9783662464472
ISBN (Print)9783662464465
Publication statusPublished - 2015
Externally publishedYes
EventInternational Conference on Practice and Theory in Public Key Cryptography 2015 - Gaithersburg, United States of America
Duration: 30 Mar 20151 Apr 2015
Conference number: 18th (Proceedings) (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Practice and Theory in Public Key Cryptography 2015
Abbreviated titlePKC 2015
Country/TerritoryUnited States of America
Internet address


  • Digital signatures
  • Strong RSA

Cite this