Multi Designated Verifier Ring Signatures
Authors
Sebastian Kolby, Elena Pagnin, Sophia Yakoubov
Sebastian Kolby
Aarhus University, Aarhus, Denmark
sk at cs dot au dot dk
sk at cs dot au dot dk
Elena Pagnin
Chalmers University of Technology and University of Gothenburg, Gothenburg, Sweden
elenap at chalmers dot se
elenap at chalmers dot se
Sophia Yakoubov
Aarhus University, Aarhus, Denmark
sophia dot yakoubov at cs dot au dot dk
sophia dot yakoubov at cs dot au dot dk
Abstract
We study signatures well suited for sensitive applications (e.g. whistleblowing) where both the signer's anonymity and deniability are important. Two independent lines of work have tackled these two goals: ring signatures ensure the signer's anonymity (within a set of signers, called a ring), and — separately — multi designated verifier signatures ensure that all the intended recipients agree on whether a signature is valid, while maintaining the signer's deniability by preventing the intended recipients from convincing an outsider of the validity of the signature. In this paper, we introduce multi designated verifier ring signatures (MDVRS), which simultaneously offer both signer anonymity and deniability. This makes MDVRS uniquely suited for sensitive scenarios.
Following the blueprint of Damgård et al (TCC'20) for multi designated verifier signatures, we introduce provably simulatable designated verifier ring signatures (PSDVRS) as an intermediate building block which we then compile into an MDVRS. We instantiate PSDVRS in a concretely efficient way from discrete logarithm based sigma protocols, encryption and commitments.
References
[AC20]
Thomas Attema and Ronald Cramer. Compressed $\varSigma$-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 513–543. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56877-1_18
[ACF21]
Thomas Attema, Ronald Cramer, and Serge Fehr. Compressing Proofs of k-Out-Of-n Partial Knowledge. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 65–91, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84259-8_3
[AFK23]
Thomas Attema, Serge Fehr, and Michael Klooß. Fiat-Shamir Transformation of Multi-Round Interactive Proofs (Extended Version). Journal of Cryptology, 36(4):36, October 2023. DOI: 10.1007/s00145-023-09478-y
[AHAN+22]
Diego F. Aranha, Mathias Hall-Andersen, Anca Nitulescu, Elena Pagnin, and Sophia Yakoubov. Count Me In! Extendability for Threshold Ring Signatures. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022, Part II, volume 13178 of LNCS, pages 379–406. March 2022. Springer, Cham. DOI: 10.1007/978-3-030-97131-1_13
[BBG+22]
Danai Balla, Pourandokht Behrouz, Panagiotis Grontas, Aris Pagourtzis, Marianna Spyrakou, and Giannis Vrettos. Designated-Verifier Linkable Ring Signatures with Unconditional Anonymity. In Algebraic Informatics: 9th International Conference, CAI 2022, Virtual Event, October 27–29, 2022, Proceedings, pages 55–68. 2022. Springer. DOI: https://doi.org/10.1007/978-3-031-19685-0_5
[BFM88]
Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In 20th ACM STOC, pages 103–112. May 1988. ACM Press. DOI: 10.1145/62212.62222
[BGK+22]
Pourandokht Behrouz, Panagiotis Grontas, Vangelis Konstantakatos, Aris Pagourtzis, and Marianna Spyrakou. Designated-verifier linkable ring signatures. In Information Security and Cryptology–ICISC 2021: 24th International Conference, Seoul, South Korea, December 1–3, 2021, Revised Selected Papers, pages 51–70. 2022. Springer. DOI: https://doi.org/10.1007/978-3-031-08896-4_3
[BGLS03]
Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In Eli Biham, editor, EUROCRYPT 2003, volume 2656 of LNCS, pages 416–432. May 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-39200-9_26
[BKM06]
Adam Bender, Jonathan Katz, and Ruggero Morselli. Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles. In Shai Halevi and Tal Rabin, editors, TCC 2006, volume 3876 of LNCS, pages 60–79. March 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11681878_4
[BLS01]
Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. In ASIACRYPT 2001, volume 2248 of LNCS. Springer, Berlin, Heidelberg, pages 514–532. 2001. DOI: 10.1007/3-540-45682-1_30
[BSS02]
Emmanuel Bresson, Jacques Stern, and Michael Szydlo. Threshold Ring Signatures and Applications to Ad-hoc Groups. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 465–480. August 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45708-9_30
[CDS94]
Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Yvo Desmedt, editor, CRYPTO'94, volume 839 of LNCS, pages 174–187. August 1994. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48658-5_19
[Cho06]
Sherman S. M. Chow. Identity-Based Strong Multi-Designated Verifiers Signatures. In European Public Key Infrastructure Workshop. 2006. DOI: https://doi.org/10.1007/11774716_23
[Cho08]
Sherman S. M. Chow. Multi-Designated Verifiers Signatures Revisited. International Journal of Network Security, 7:348-357, 2008. DOI: https://doi.org/10.6633/IJNS.200811.7(3).06
[CK21]
Matteo Campanelli and Hamidreza Khoshakhlagh. Succinct Publicly-Certifiable Proofs - Or, Can a Blockchain Verify a Designated-Verifier Proof?. In Avishek Adhikari, Ralf Küsters, and Bart Preneel, editors, INDOCRYPT 2021, volume 13143 of LNCS, pages 607–631. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92518-5_27
[CLHY05]
Sherman SM Chow, Richard WC Lui, Lucas CK Hui, and Siu-Ming Yiu. Identity based ring signature: Why, how and what next. In Public Key Infrastructure: Second European PKI Workshop: Research and Applications, EuroPKI 2005, Canterbury, UK, June 30-July 1, 2005, Revised Selected Papers 2, pages 144–161. 2005. Springer. DOI: https://doi.org/10.1007/11533733_10
[Cv91]
David Chaum and Eugène van Heyst. Group Signatures. In Donald W. Davies, editor, EUROCRYPT'91, volume 547 of LNCS, pages 257–265. April 1991. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46416-6_22
[DHM+20]
Ivan Damgård, Helene Haagh, Rebekah Mercer, Anca Nitulescu, Claudio Orlandi, and Sophia Yakoubov. Stronger Security and Constructions of Multi-designated Verifier Signatures. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part II, volume 12551 of LNCS, pages 229–260. November 2020. Springer, Cham. DOI: 10.1007/978-3-030-64378-2_9
[DKNS04]
Yevgeniy Dodis, Aggelos Kiayias, Antonio Nicolosi, and Victor Shoup. Anonymous Identification in Ad Hoc Groups. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 609–626. May 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24676-3_36
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186–194. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[FS07]
Eiichiro Fujisaki and Koutarou Suzuki. Traceable Ring Signature. In Tatsuaki Okamoto and Xiaoyun Wang, editors, PKC 2007, volume 4450 of LNCS, pages 181–200. April 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-71677-8_13
[GKO+23]
Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, and Daniel Tschudi. Witness-Succinct Universally-Composable SNARKs. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part II, volume 14005 of LNCS, pages 315–346. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30617-4_11
[GM17]
Jens Groth and Mary Maller. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 581–612. August 2017. Springer, Cham. DOI: 10.1007/978-3-319-63715-0_20
[Jou04]
Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. Journal of Cryptology, 17(4):263–276, September 2004. DOI: 10.1007/s00145-004-0312-y
[JSI96]
Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. Designated Verifier Proofs and Their Applications. In Ueli M. Maurer, editor, EUROCRYPT'96, volume 1070 of LNCS, pages 143–154. May 1996. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-68339-9_13
[LSMP07]
Yong Li, Willy Susilo, Yi Mu, and Dingyi Pei. Designated verifier signature: definition, framework and new constructions. In Ubiquitous Intelligence and Computing: 4th International Conference, UIC 2007, Hong Kong, China, July 11-13, 2007. Proceedings 4, pages 1191–1200. 2007. Springer. DOI: https://doi.org/10.1007/978-3-540-73549-6_116
[LV04]
Fabien Laguillaumie and Damien Vergnaud. Multi-designated Verifiers Signatures. In Javier López, Sihan Qing, and Eiji Okamoto, editors, ICICS 04, volume 3269 of LNCS, pages 495–507. October 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-30191-2_38
[Ped92]
Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 129–140. August 1992. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46766-1_9
[RST01]
Ronald L. Rivest, Adi Shamir, and Yael Tauman. How to Leak a Secret. In ASIACRYPT 2001, volume 2248 of LNCS. Springer, Berlin, Heidelberg, pages 552–565. 2001. DOI: 10.1007/3-540-45682-1_32
[SALY17]
Shi-Feng Sun, Man Ho Au, Joseph K. Liu, and Tsz Hon Yuen. RingCT 2.0: A Compact Accumulator-Based (Linkable Ring Signature) Protocol for Blockchain Cryptocurrency Monero. In Simon N. Foley, Dieter Gollmann, and Einar Snekkenes, editors, ESORICS 2017, Part II, volume 10493 of LNCS, pages 456–474. September 2017. Springer, Cham. DOI: 10.1007/978-3-319-66399-9_25
[SBWP03]
Ron Steinfeld, Laurence Bull, Huaxiong Wang, and Josef Pieprzyk. Universal Designated-Verifier Signatures. In Chi-Sung Laih, editor, ASIACRYPT 2003, volume 2894 of LNCS, pages 523–542. 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-40061-5_33
[SKM04]
Shahrokh Saeednia, Steve Kremer, and Olivier Markowitch. An Efficient Strong Designated Verifier Signature Scheme. In Jong In Lim and Dong Hoon Lee, editors, ICISC 03, volume 2971 of LNCS, pages 40–54. November 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24691-6_4
[SWP04]
Ron Steinfeld, Huaxiong Wang, and Josef Pieprzyk. Efficient Extension of Standard Schnorr/RSA Signatures into Universal Designated-Verifier Signatures. In Feng Bao, Robert Deng, and Jianying Zhou, editors, PKC 2004, volume 2947 of LNCS, pages 86–100. March 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24632-9_7
[SZM04]
Willy Susilo, Fangguo Zhang, and Yi Mu. Identity-Based Strong Designated Verifier Signature Schemes. In Huaxiong Wang, Josef Pieprzyk, and Vijay Varadharajan, editors, ACISP 04, volume 3108 of LNCS, pages 313–324. July 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-27800-9_27
[ZK02]
Fangguo Zhang and Kwangjo Kim. ID-Based Blind Signature and Ring Signature from Pairings. In Yuliang Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 533–547. December 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-36178-2_33
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Sebastian Kolby, Elena Pagnin, and Sophia Yakoubov, Multi Designated Verifier Ring Signatures. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a33zivrzn.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.