A family of FDH signature schemes based on the quadratic residuosity assumption

Giuseppe Ateniese, Katharina Fech, Bernardo Magri

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


Signature schemes are arguably the most crucial cryptographic primitive, and devising tight security proofs for signature schemes is an important endeavour, as it immediately impacts the feasibility of deployment in real world applications. Hash-then-sign signature schemes in the Random Oracle Model, such as RSA-FDH, and Rabin-Williams variants are among the fastest schemes to date, but that unfortunately do not enjoy tight security proofs based on the one-wayness of their trapdoor function; instead, all known tight proofs rely on variants of the (non-standard) Φ-Hiding assumption. As our main contribution, we introduce a family of hash-then-sign signature schemes, inspired by a lossy trapdoor function from Freeman et al. (JoC’ 13), that is tightly secure under the Quadratic Residuosity assumption. Our first scheme has the property of having unique signatures, while the second scheme is deterministic with an extremely fast signature verification, requiring at most 3 modular multiplications.

Original languageEnglish
Title of host publicationProgress in Cryptology – INDOCRYPT 2018 - 19th International Conference on Cryptology in India, Proceedings
EditorsDebrup Chakraborty, Tetsu Iwata
PublisherSpringer-Verlag Italia
Number of pages15
ISBN (Print)9783030053772
Publication statusPublished - 2018
Event19th International Conference on Cryptology in India, INDOCRYPT 2018 - New Delhi, India
Duration: 9 Dec 201812 Dec 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11356 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Cryptology in India, INDOCRYPT 2018
CityNew Delhi


  • Digital signatures
  • Full domain hash
  • Lossy trapdoor function
  • Quadratic residuosity
  • Tight security proof


Dive into the research topics of 'A family of FDH signature schemes based on the quadratic residuosity assumption'. Together they form a unique fingerprint.

Cite this