Communications in Cryptology IACR CiC

An Explicit High-Moment Forking Lemma and its Applications to the Concrete Security of Multi-Signatures

Authors

Gil Segev, Liat Shapira
Gil Segev ORCID
School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel
segev at cs dot huji dot ac dot il
Liat Shapira
School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel
liat dot shapira at mail dot huji dot ac dot il

Abstract

In this work we first present an explicit forking lemma that distills the information-theoretic essence of the high-moment technique introduced by Rotem and Segev (CRYPTO '21), who analyzed the security of identification protocols and Fiat-Shamir signature schemes. Whereas the technique of Rotem and Segev was particularly geared towards two specific cryptographic primitives, we present a stand-alone probabilistic lower bound, which does not involve any underlying primitive or idealized model. The key difference between our lemma and previous ones is that instead of focusing on the tradeoff between the worst-case or expected running time of the resulting forking algorithm and its success probability, we focus on the tradeoff between higher moments of its running time and its success probability.

Equipped with our lemma, we then establish concrete security bounds for the BN and BLS multi-signature schemes that are significantly tighter than the concrete security bounds established by Bellare and Neven (CCS '06) and Boneh, Drijvers and Neven (ASIACRYPT '18), respectively. Our analysis does not limit adversaries to any idealized algebraic model, such as the algebraic group model in which all algorithms are assumed to provide an algebraic justification for each group element they produce. Our bounds are derived in the random-oracle model based on the standard-model second-moment hardness of the discrete logarithm problem (for the BN scheme) and the computational co-Diffie-Hellman problem (for the BLS scheme). Such second-moment assumptions, asking that the success probability of any algorithm in solving the underlying computational problems is dominated by the second moment of the algorithm's running time, are particularly plausible in any group where no better-than-generic algorithms are currently known.

References

[AABN02]
Michel Abdalla, Jee Hea An and Mihir Bellare, and Chanathip Namprempre. From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security. In Lars R. Knudsen, editor, Advances in Cryptology – EUROCRYPT 2002, volume 2332 of Lecture Notes in Computer Science, pages 418–433. 2002. Springer, Heidelberg. DOI: 10.1007/3-540-46035-7_28
[AB21]
Handan Kilinç Alper and Jeffrey Burdges. Two-Round Trip Schnorr Multi-signatures via Delinearized Witnesses. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 157–188, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84242-0_7
[AHK20]
Thomas Agrikola, Dennis Hofheinz, and Julia Kastner. On Instantiating the Algebraic Group Model from Falsifiable Assumptions. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 96–126. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45724-2_4
[BB08]
Dan Boneh and Xavier Boyen. Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups. Journal of Cryptology, 21(2):149–177, April 2008. DOI: 10.1007/s00145-007-9005-7
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 327–357. May 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49896-5_12
[BD20]
Mihir Bellare and Wei Dai. The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-rewinding Proofs for Schnorr Identification and Signatures. In Karthikeyan Bhargavan, Elisabeth Oswald, and Manoj Prabhakaran, editors, Progress in Cryptology - INDOCRYPT 2020: 21st International Conference in Cryptology in India, volume 12578 of Lecture Notes in Computer Science, pages 529–552. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-65277-7_24
[BD21]
Mihir Bellare and Wei Dai. Chain Reductions for Multi-signatures and the HBMS Scheme. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 650–678. December 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-92068-5_22
[BDN18]
Dan Boneh, Manu Drijvers, and Gregory Neven. Compact Multi-signatures for Smaller Blockchains. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part II, volume 11273 of Lecture Notes in Computer Science, pages 435–464. December 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03329-3_15
[BFL20]
Balthazar Bauer, Georg Fuchsbauer, and Julian Loss. A Classification of Computational Assumptions in the Algebraic Group Model. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 121–151. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56880-1_5
[BGOY07]
Alexandra Boldyreva, Craig Gentry, Adam O'Neill, and Dae Hyun Yum. Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007: 14th Conference on Computer and Communications Security, pages 276–285. October 2007. ACM Press. DOI: 10.1145/1315245.1315280
[BLS01]
Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. In Colin Boyd, editor, Advances in Cryptology – ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 514–532. December 2001. Springer, Heidelberg. DOI: 10.1007/3-540-45682-1_30
[BN06]
Mihir Bellare and Gregory Neven. Multi-signatures in the plain public-Key model and a general forking lemma. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006: 13th Conference on Computer and Communications Security, pages 390–399. 2006. ACM Press. DOI: 10.1145/1180405.1180453
[Bol03]
Alexandra Boldyreva. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In Yvo Desmedt, editor, PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, pages 31–46. January 2003. Springer, Heidelberg. DOI: 10.1007/3-540-36288-6_3
[BR93]
Mihir Bellare and Phillip Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM CCS 93: 1st Conference on Computer and Communications Security, pages 62–73. November 1993. ACM Press. DOI: 10.1145/168588.168596
[BTT22]
Cecilia Boschini, Akira Takahashi, and Mehdi Tibouchi. MuSig-L: Lattice-Based Multi-signature with Single-Round Online Phase. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part II, volume 13508 of Lecture Notes in Computer Science, pages 276–305. August 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-15979-4_10
[DEF+19]
Manu Drijvers, Kasra Edalatnejad, Bryan Ford, Eike Kiltz, Julian Loss, Gregory Neven, and Igors Stepanovs. On the Security of Two-Round Multi-Signatures. In 2019 IEEE Symposium on Security and Privacy, pages 1084–1101. May 2019. IEEE Computer Society Press. DOI: 10.1109/SP.2019.00050
[DOTT22]
Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. Two-Round $n$-out-of-$n$ and Multi-Signatures and Trapdoor Commitment from Lattices. Journal of Cryptology, 35(2):14, April 2022. DOI: 10.1007/s00145-022-09425-3
[FKL18]
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The Algebraic Group Model and its Applications. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 33–62. August 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-96881-0_2
[FPS20]
Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin. Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 63–95. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45724-2_3
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology – CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186–194. August 1987. Springer, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[FSZ22]
Nils Fleischhacker, Mark Simkin, and Zhenfei Zhang. Squirrel: Efficient Synchronized Multi-Signatures from Lattices. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 1109–1123. November 2022. ACM Press. DOI: 10.1145/3548606.3560655
[IN83]
Kazuharu Itakura and Katsuhiro Nakamura. A public-key cryptosystem suitable for digital multisignatures. NEC Research & Development, 71:1–8, 1983.
[JT20]
Joseph Jaeger and Stefano Tessaro. Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th Theory of Cryptography Conference, Part III, volume 12552 of Lecture Notes in Computer Science, pages 414–443. November 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64381-2_15
[KMP16]
Eike Kiltz, Daniel Masny, and Jiaxin Pan. Optimal Security Proofs for Signatures from Identification Schemes. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 33–61. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53008-5_2
[LHL95]
Chuan-Ming Li, Tzonelih Hwang, and Narn-Yih Lee. Threshold-Multisignature Schemes where Suspected Forgery Implies Traceability of Adversarial Shareholders. In Alfredo De Santis, editor, Advances in Cryptology – EUROCRYPT'94, volume 950 of Lecture Notes in Computer Science, pages 194–204. May 1995. Springer, Heidelberg. DOI: 10.1007/BFb0053435
[LK23]
Kwangsu Lee and Hyoseung Kim. Two-Round Multi-Signatures from Okamoto Signatures. Mathematics, 11(14), 2023. DOI: 10.3390/math11143223
[LOS+06]
Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters. Sequential Aggregate Signatures and Multisignatures Without Random Oracles. In Serge Vaudenay, editor, Advances in Cryptology – EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 465–485. 2006. Springer, Heidelberg. DOI: 10.1007/11761679_28
[Mau05]
Ueli M. Maurer. Abstract Models of Computation in Cryptography (Invited Paper). In Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of Lecture Notes in Computer Science, pages 1–12. December 2005. Springer, Heidelberg. DOI: 10.1007/11586821_1
[MOR01]
Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Accountable-Subgroup Multisignatures: Extended Abstract. In Michael K. Reiter and Pierangela Samarati, editors, ACM CCS 2001: 8th Conference on Computer and Communications Security, pages 245–254. November 2001. ACM Press. DOI: 10.1145/501983.502017
[MPSW19]
Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. Simple Schnorr multi-signatures with applications to Bitcoin. Designs, Codes and Cryptography, 87(9):2139–2164, 2019. DOI: 10.1007/s10623-019-00608-x
[MTT19]
Taiga Mizuide, Atsushi Takayasu, and Tsuyoshi Takagi. Tight Reductions for Diffie-Hellman Variants in the Algebraic Group Model. In Mitsuru Matsui, editor, Topics in Cryptology – CT-RSA 2019, volume 11405 of Lecture Notes in Computer Science, pages 169–188. March 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-12612-4_9
[NRS21]
Jonas Nick, Tim Ruffing, and Yannick Seurin. MuSig2: Simple Two-Round Schnorr Multi-signatures. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 189–221, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84242-0_8
[NRSW20]
Jonas Nick, Tim Ruffing, Yannick Seurin, and Pieter Wuille. MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020: 27th Conference on Computer and Communications Security, pages 1717–1731. November 2020. ACM Press. DOI: 10.1145/3372297.3417236
[OO93]
Kazuo Ohta and Tatsuaki Okamoto. A Digital Multisignature Scheme Based on the Fiat-Shamir Scheme. In Hideki Imai, Ronald L. Rivest, and Tsutomu Matsumoto, editors, Advances in Cryptology – ASIACRYPT'91, volume 739 of Lecture Notes in Computer Science, pages 139–148. November 1993. Springer, Heidelberg. DOI: 10.1007/3-540-57332-1_11
[PS00]
David Pointcheval and Jacques Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, June 2000. DOI: 10.1007/s001450010003
[PW23]
Jiaxin Pan and Benedikt Wagner. Chopsticks: Fork-Free Two-Round Multi-signatures from Non-interactive Assumptions. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 597–627. April 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-30589-4_21
[RS20]
Lior Rotem and Gil Segev. Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th Theory of Cryptography Conference, Part III, volume 12552 of Lecture Notes in Computer Science, pages 366–389. November 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64381-2_13
[RS21]
Lior Rotem and Gil Segev. Tighter Security for Schnorr Identification and Signatures: A High-Moment Forking Lemma for $\varSigma$-Protocols. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 222–250, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84242-0_9
[RY07]
Thomas Ristenpart and Scott Yilek. The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks. In Moni Naor, editor, Advances in Cryptology – EUROCRYPT 2007, volume 4515 of Lecture Notes in Computer Science, pages 228–245. May 2007. Springer, Heidelberg. DOI: 10.1007/978-3-540-72540-4_13
[Sho97]
Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Walter Fumy, editor, Advances in Cryptology – EUROCRYPT'97, volume 1233 of Lecture Notes in Computer Science, pages 256–266. May 1997. Springer, Heidelberg. DOI: 10.1007/3-540-69053-0_18
[SSY23]
Gil Segev, Amit Sharabi, and Eylon Yogev. Rogue-Instance Security for Batch Knowledge Proofs. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part I, volume 14369 of Lecture Notes in Computer Science, pages 121–157. 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-48615-9_5
[TZ23]
Stefano Tessaro and Chenzhi Zhu. Threshold and Multi-signature Schemes from Linear Hash Functions. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part V, volume 14008 of Lecture Notes in Computer Science, pages 628–658. April 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-30589-4_22

PDFPDF Open access

History
Submitted: 2024-01-01
Accepted: 2024-06-04
Published: 2024-07-08
How to cite

Gil Segev and Liat Shapira, "An Explicit High-Moment Forking Lemma and its Applications to the Concrete Security of Multi-Signatures," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a6qj89n4e.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.