TY - GEN
T1 - A family of FDH signature schemes based on the quadratic residuosity assumption
AU - Ateniese, Giuseppe
AU - Fech, Katharina
AU - Magri, Bernardo
N1 - Publisher Copyright:
© 2018, Springer Nature Switzerland AG.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Digital signatures
KW - Full domain hash
KW - Lossy trapdoor function
KW - Quadratic residuosity
KW - Tight security proof
UR - http://www.scopus.com/inward/record.url?scp=85058505524&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-05378-9_14
DO - 10.1007/978-3-030-05378-9_14
M3 - Conference contribution
AN - SCOPUS:85058505524
SN - 9783030053772
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 248
EP - 262
BT - Progress in Cryptology – INDOCRYPT 2018 - 19th International Conference on Cryptology in India, Proceedings
A2 - Chakraborty, Debrup
A2 - Iwata, Tetsu
PB - Springer-Verlag Italia
T2 - 19th International Conference on Cryptology in India, INDOCRYPT 2018
Y2 - 9 December 2018 through 12 December 2018
ER -