Skip to main content
placeholder image

Optimal Tightness for Chain-Based Unique Signatures

Chapter


Abstract


  • Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo et al. proposed a particular chain-based unique signature scheme where each unique signature is composed of n BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is n·qH1/n for qH hash queries and it is logarithmically tight when n= log qH. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists. We show that the proposed chain-based unique signature scheme by Guo et al. must have the reduction loss q1/n for q signature queries when each unique signature consists of n BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss 4 · q1/n for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss n·qH1/n that is logarithmically tight at most. The core of our reduction idea is a non-uniform simulation that is specially invented for the chain-based unique signature construction.

Publication Date


  • 2022

Citation


  • Guo, F., & Susilo, W. (2022). Optimal Tightness for Chain-Based Unique Signatures. In Unknown Book (Vol. 13276 LNCS, pp. 553-583). doi:10.1007/978-3-031-07085-3_19

International Standard Book Number (isbn) 13


  • 9783031070846

Scopus Eid


  • 2-s2.0-85132121708

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 553

End Page


  • 583

Abstract


  • Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo et al. proposed a particular chain-based unique signature scheme where each unique signature is composed of n BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is n·qH1/n for qH hash queries and it is logarithmically tight when n= log qH. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists. We show that the proposed chain-based unique signature scheme by Guo et al. must have the reduction loss q1/n for q signature queries when each unique signature consists of n BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss 4 · q1/n for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss n·qH1/n that is logarithmically tight at most. The core of our reduction idea is a non-uniform simulation that is specially invented for the chain-based unique signature construction.

Publication Date


  • 2022

Citation


  • Guo, F., & Susilo, W. (2022). Optimal Tightness for Chain-Based Unique Signatures. In Unknown Book (Vol. 13276 LNCS, pp. 553-583). doi:10.1007/978-3-031-07085-3_19

International Standard Book Number (isbn) 13


  • 9783031070846

Scopus Eid


  • 2-s2.0-85132121708

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 553

End Page


  • 583