1. bookVolume 2022 (2022): Issue 2 (April 2022)
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Efficient Set Membership Proofs using MPC-in-the-Head

Published Online: 03 Mar 2022
Page range: 304 - 324
Received: 31 Aug 2021
Accepted: 16 Dec 2021
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness w corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. ℛ(w, x) = 1 and x is a member of a public set {x1, . . . , x𝓁}. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies.

In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC’07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS’18].We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.

Keywords

[1] Reverie (github project), 2020. https://github.com/trailofbits/reverie. Search in Google Scholar

[2] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2087–2104. ACM Press, October / November 2017.10.1145/3133956.3134104 Search in Google Scholar

[3] David Archer, Victor Arribas Abril, Steve Lu, Pieter Maene, Nele Mertens, Danilo Sijacic, and Nigel Smart. Bristol fashion MPC circuits. https://homes.esat.kuleuven.be/~nsmart/MPC/. Search in Google Scholar

[4] Carsten Baum, Alex J. Malozemoff, Marc Rosen, and Peter Scholl. Mac’n’cheese: Zero-knowledge proofs for arithmetic circuits with nested disjunctions. Cryptology ePrint Archive, Report 2020/1410, 2020. https://eprint.iacr.org/2020/1410. Search in Google Scholar

[5] Michael Ben-Or and Avinatan Hassidim. Fast quantum byzantine agreement. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 481–485. ACM Press, May 2005.10.1145/1060590.1060662 Search in Google Scholar

[6] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 103–128. Springer, Heidelberg, May 2019.10.1007/978-3-030-17653-2_4 Search in Google Scholar

[7] Daniel Benarroch, Matteo Campanelli, Dario Fiore, and Dimitris Kolonelos. Zero-knowledge proofs for set membership: Efficient, succinct, modular. Cryptology ePrint Archive, Report 2019/1255, 2019. https://eprint.iacr.org/2019/1255. Search in Google Scholar

[8] Daniel Bernstein. Chacha, a variant of salsa20. 01 2008. Search in Google Scholar

[9] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, Jens Groth, and Christophe Petit. Short accountable ring signatures based on DDH. In Günther Pernul, Peter Y. A. Ryan, and Edgar R. Weippl, editors, ESORICS 2015, Part I, volume 9326 of LNCS, pages 243–265. Springer, Heidelberg, September 2015.10.1007/978-3-319-24174-6_13 Search in Google Scholar

[10] Cecilia Boschini, Jan Camenisch, Max Ovsiankin, and Nicholas Spooner. Efficient post-quantum SNARKs for RSIS and RLWE and their applications to privacy. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, pages 247–267. Springer, Heidelberg, 2020.10.1007/978-3-030-44223-1_14 Search in Google Scholar

[11] Zvika Brakerski and Yael Tauman Kalai. A framework for efficient signatures, ring signatures and identity based encryption in the standard model. Cryptology ePrint Archive, Report 2010/086, 2010. https://eprint.iacr.org/2010/086. Search in Google Scholar

[12] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. IEEE Computer Society Press, May 2018.10.1109/SP.2018.00020 Search in Google Scholar

[13] Vitalik Buterin et al. A next-generation smart contract and decentralized application platform. 2014. Search in Google Scholar

[14] Jan Camenisch, Rafik Chaabouni, and abhi shelat. Efficient protocols for set membership and range proofs. In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, pages 234–252. Springer, Heidelberg, December 2008.10.1007/978-3-540-89255-7_15 Search in Google Scholar

[15] Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 1825–1842. ACM Press, October / November 2017.10.1145/3133956.3133997 Search in Google Scholar

[16] Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. Cryptology ePrint Archive, Report 2019/1076, 2019. https://eprint.iacr.org/2019/1076. Search in Google Scholar

[17] Sherman S. M. Chow, Victor K.-W. Wei, Joseph K. Liu, and Tsz Hon Yuen. Ring signatures without random oracles. In Ferng-Ching Lin, Der-Tsai Lee, Bao-Shuh Lin, Shiuhpyng Shieh, and Sushil Jajodia, editors, ASIACCS 06, pages 297–302. ACM Press, March 2006. Search in Google Scholar

[18] David Derler, Sebastian Ramacher, and Daniel Slamanig. Post-quantum zero-knowledge proofs for accumulators with applications to ring signatures from symmetric-key primitives. In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, pages 419–440. Springer, Heidelberg, 2018.10.1007/978-3-319-79063-3_20 Search in Google Scholar

[19] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security of the Fiat-Shamir transformation in the quantum random-oracle model. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 356–383. Springer, Heidelberg, August 2019.10.1007/978-3-030-26951-7_13 Search in Google Scholar

[20] Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, and Dongxi Liu. Lattice-based zero-knowledge proofs: New techniques for shorter and faster constructions and applications. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 115–146. Springer, Heidelberg, August 2019.10.1007/978-3-030-26948-7_5 Search in Google Scholar

[21] Muhammed F. Esgin, Raymond K. Zhao, Ron Steinfeld, Joseph K. Liu, and Dongxi Liu. MatRiCT: Efficient, scalable and post-quantum blockchain confidential transactions protocol. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 567–584. ACM Press, November 2019. Search in Google Scholar

[22] Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. On the non-malleability of the Fiat-Shamir transform. In Steven D. Galbraith and Mridul Nandi, editors, INDOCRYPT 2012, volume 7668 of LNCS, pages 60–79. Springer, Heidelberg, December 2012.10.1007/978-3-642-34931-7_5 Search in Google Scholar

[23] 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. Springer, Heidelberg, August 1987.10.1007/3-540-47721-7_12 Search in Google Scholar

[24] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 626–645. Springer, Heidelberg, May 2013.10.1007/978-3-642-38348-9_37 Search in Google Scholar

[25] Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. ZKBoo: Faster zero-knowledge for Boolean circuits. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016, pages 1069–1083. USENIX Association, August 2016. Search in Google Scholar

[26] Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk. Stacking sigmas: A framework to compose σ-protocols for disjunctions. Cryptology ePrint Archive, Report 2021/422, 2021. https://eprint.iacr.org/2021/422. Search in Google Scholar

[27] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218–229. ACM Press, May 1987.10.1145/28395.28420 Search in Google Scholar

[28] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691–729, 1991.10.1145/116825.116852 Search in Google Scholar

[29] Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. Springer, Heidelberg, May 2016.10.1007/978-3-662-49896-5_11 Search in Google Scholar

[30] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery.10.1145/237814.237866 Search in Google Scholar

[31] David Heath and Vladimir Kolesnikov. Stacked garbling for disjunctive zero-knowledge proofs. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 569–598. Springer, Heidelberg, May 2020.10.1007/978-3-030-45727-3_19 Search in Google Scholar

[32] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 21–30. ACM Press, June 2007.10.1145/1250790.1250794 Search in Google Scholar

[33] Marek Jawurek, Florian Kerschbaum, and Claudio Orlandi. Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 955–966. ACM Press, November 2013.10.1145/2508859.2516662 Search in Google Scholar

[34] Daniel Kales and Greg Zaverucha. Improving the performance of the picnic signature scheme. Cryptology ePrint Archive, Report 2020/427, 2020. https://eprint.iacr.org/2020/427.10.46586/tches.v2020.i4.154-188 Search in Google Scholar

[35] Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang. Improved non-interactive zero knowledge with applications to post-quantum signatures. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 525–537. ACM Press, October 2018.10.1145/3243734.3243805 Search in Google Scholar

[36] Russell W. F. Lai, Viktoria Ronge, Tim Ruffing, Dominique Schröder, Sri Aravinda Krishnan Thyagarajan, and Jiafan Wang. Omniring: Scaling private payments without trusted setup. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 31–48. ACM Press, November 2019. Search in Google Scholar

[37] Benoît Libert, San Ling, Khoa Nguyen, and Huaxiong Wang. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 1–31. Springer, Heidelberg, May 2016.10.1007/978-3-662-49896-5_1 Search in Google Scholar

[38] Qipeng Liu and Mark Zhandry. Revisiting post-quantum Fiat-Shamir. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 326–355. Springer, Heidelberg, August 2019.10.1007/978-3-030-26951-7_12 Search in Google Scholar

[39] Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler. SMILE: Set membership from ideal lattices with applications to ring signatures and confidential transactions. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 611–640, Virtual Event, August 2021. Springer, Heidelberg.10.1007/978-3-030-84245-1_21 Search in Google Scholar

[40] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge SNARKs from linearsize universal and updatable structured reference strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2111–2128. ACM Press, November 2019.10.1145/3319535.3339817 Search in Google Scholar

[41] Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. Zerocoin: Anonymous distributed E-cash from Bitcoin. In 2013 IEEE Symposium on Security and Privacy, pages 397–411. IEEE Computer Society Press, May 2013.10.1109/SP.2013.34 Search in Google Scholar

[42] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Technical report, 2008. Search in Google Scholar

[43] Shen Noether. Ring signature confidential transactions for monero. Cryptology ePrint Archive, Report 2015/1098, 2015. https://eprint.iacr.org/2015/1098. Search in Google Scholar

[44] Shen Noether, Adam Mackenzie, and the Monero Research Lab. Ring confidential transactions. Ledger, 1:1–18, Dec. 2016.10.5195/ledger.2016.34 Search in Google Scholar

[45] Jack O’Connor, Jean-Phillip Aumasson, Samuel Neves, and Zooko Wilcox-O’Hearn. Blake3: One function, fast everywhere. 01 2020. Search in Google Scholar

[46] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 238–252. IEEE Computer Society Press, May 2013.10.1109/SP.2013.47 Search in Google Scholar

[47] Ronald L. Rivest, Adi Shamir, and Yael Tauman. How to leak a secret. In Colin Boyd, editor, ASIACRYPT 2001, volume 2248 of LNCS, pages 552–565. Springer, Heidelberg, December 2001.10.1007/3-540-45682-1_32 Search in Google Scholar

[48] Tomas Sander and Amnon Ta-Shma. Auditable, anonymous electronic cash. In Michael J. Wiener, editor, CRYPTO’99, volume 1666 of LNCS, pages 555–572. Springer, Heidelberg, August 1999.10.1007/3-540-48405-1_35 Search in Google Scholar

[49] Srinath Setty. Spartan: Efficient and general-purpose zk-SNARKs without trusted setup. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 704–737. Springer, Heidelberg, August 2020.10.1007/978-3-030-56877-1_25 Search in Google Scholar

[50] Adi Shamir. How to share a secret. Communications of the Association for Computing Machinery, 22(11):612–613, November 1979.10.1145/359168.359176 Search in Google Scholar

[51] 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. Springer, Heidelberg, September 2017.10.1007/978-3-319-66399-9_25 Search in Google Scholar

[52] Wilson Abel Alberto Torres, Veronika Kuchta, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, and Jacob Cheng. Lattice RingCT V2.0 with multiple input and multiple output wallets. In Julian Jang-Jaccard and Fuchun Guo, editors, ACISP 19, volume 11547 of LNCS, pages 156–175. Springer, Heidelberg, July 2019.10.1007/978-3-030-21548-4_9 Search in Google Scholar

[53] Wilson Abel Alberto Torres, Ron Steinfeld, Amin Sakzad, Joseph K. Liu, Veronika Kuchta, Nandita Bhattacharjee, Man Ho Au, and Jacob Cheng. Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice RingCT v1.0). In Willy Susilo and Guomin Yang, editors, ACISP 18, volume 10946 of LNCS, pages 558–576. Springer, Heidelberg, July 2018.10.1007/978-3-319-93638-3_32 Search in Google Scholar

[54] Wilson Alberto Torres, Ron Steinfeld, Amin Sakzad, and Veronika Kuchta. Post-quantum linkable ring signature enabling distributed authorised ring confidential transactions in blockchain. Cryptology ePrint Archive, Report 2020/1121, 2020. https://eprint.iacr.org/2020/1121. Search in Google Scholar

[55] Dominique Unruh. Post-quantum security of Fiat-Shamir. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASI-ACRYPT 2017, Part I, volume 10624 of LNCS, pages 65–95. Springer, Heidelberg, December 2017.10.1007/978-3-319-70694-8_3 Search in Google Scholar

[56] Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 733–764. Springer, Heidelberg, August 2019.10.1007/978-3-030-26954-8_24 Search in Google Scholar

[57] Tsz Hon Yuen, Shifeng Sun, Joseph K. Liu, Man Ho Au, Muhammed F. Esgin, Qingzhao Zhang, and Dawu Gu. RingCT 3.0 for blockchain confidential transaction: Shorter size and stronger security. In Joseph Bonneau and Nadia Heninger, editors, FC 2020, volume 12059 of LNCS, pages 464–483. Springer, Heidelberg, February 2020.10.1007/978-3-030-51280-4_25 Search in Google Scholar

[58] Greg Zaverucha. The picnic signature algorithm. Technical report, 2020. https://github.com/microsoft/Picnic/raw/master/spec/spec-v3.0.pdf. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo