Communications in Cryptology IACR CiC

Verifiable Encryption from MPC-in-the-Head

Authors

Akira Takahashi, Greg Zaverucha
Akira Takahashi ORCID
J.P.Morgan AI Research & AlgoCRYPT CoE, New York, USA
takahashi dot akira dot 58s at gmail dot com
Greg Zaverucha
Microsoft Research, Redmond, USA
gregz at microsoft dot com

Abstract

Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations. In this work, we propose a novel framework that realizes VE protocols using zero-knowledge proof systems based on the MPC-in-the-head paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zero-knowledge proofs into secure VE protocols for any secure public-key encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme. Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with post-quantum security, along with an implementation and benchmarks.

References

[AHIV17]
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, 2087–2104. October / November 2017. ACM Press. https://doi.org/10.1145/3133956.3134104.
[AKV22]
Microsoft Azure Key Vault Documentation: Key types, algorithms, and operations. February 2022.
[ASW98]
N. Asokan, Victor Shoup, and Michael Waidner. Optimistic fair exchange of digital signatures (extended abstract). In Kaisa Nyberg, editor, EUROCRYPT'98, volume 1403 of LNCS, 591–606. May / June 1998. Springer, Heidelberg. https://doi.org/10.1007/BFb0054156.
[Ate99]
Giuseppe Ateniese. Efficient verifiable encryption (and fair exchange) of digital signatures. In Juzar Motiwalla and Gene Tsudik, editors, ACM CCS 99, 138–146. November 1999. ACM Press. https://doi.org/10.1145/319709.319728.
[AWS22a]
Amazon Web Services CloudHSM Documentation: Using the command line to manage keys. 2022.
[AWS22b]
Amazon Web Services Key Management Service Documentation: AWS KMS Keys. 2022.
[BBB+18]
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, 315–334. May 2018. IEEE Computer Society Press. https://doi.org/10.1109/SP.2018.00020.
[BDK+21]
Carsten Baum, Cyprien Delpech de Saint Guilhem, Daniel Kales, Emmanuela Orsini, Peter Scholl, and Greg Zaverucha. Banquet: short and fast signatures from AES. In Juan Garay, editor, PKC 2021, Part I, volume 12710 of LNCS, 266–297. May 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-75245-3_11.
[BDK+22]
Ward Beullens, Samuel Dobson, Shuichi Katsumata, Yi-Fu Lai, and Federico Pintore. Group signatures and more from isogenies and lattices: generic, simple, and efficient. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part II, volume 13276 of LNCS, 95–126. May / June 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-07085-3_4.
[Beu20]
Ward Beullens. Sigma protocols for MQ, PKP and SIS, and Fishy signature schemes. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, 183–211. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45727-3_7.
[BFH+20]
Rishabh Bhadauria, Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Tiancheng Xie, and Yupeng Zhang. Ligero++: A new optimized sublinear IOP. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, 2025–2038. November 2020. ACM Press. https://doi.org/10.1145/3372297.3417893.
[BFM88]
Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In 20th ACM STOC, 103–112. May 1988. ACM Press. https://doi.org/10.1145/62212.62222.
[BKM09]
Adam Bender, Jonathan Katz, and Ruggero Morselli. Ring signatures: stronger definitions, and constructions without random oracles. Journal of Cryptology, 22(1):114–138, January 2009. https://doi.org/10.1007/s00145-007-9011-9.
[BN20]
Carsten Baum and Ariel Nof. Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020, Part I, volume 12110 of LNCS, 495–526. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45374-9_17.
[BSZ05]
Mihir Bellare, Haixia Shi, and Chong Zhang. Foundations of group signatures: the case of dynamic groups. In Alfred Menezes, editor, CT-RSA 2005, volume 3376 of LNCS, 136–153. February 2005. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-30574-3_11.
[CCFG16]
Pyrros Chaidos, Véronique Cortier, Georg Fuchsbauer, and David Galindo. BeleniosRF: A non-interactive receipt-free electronic voting scheme. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 1614–1625. October 2016. ACM Press. https://doi.org/10.1145/2976749.2978337.
[CD00]
Jan Camenisch and Ivan Damgård. Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, 331–345. December 2000. Springer, Heidelberg. https://doi.org/10.1007/3-540-44448-3_25.
[CDG+17]
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, 1825–1842. October / November 2017. ACM Press. https://doi.org/10.1145/3133956.3133997.
[CDK+22]
Matteo Campanelli, Bernardo David, Hamidreza Khoshakhlagh, Anders Konring, and Jesper Buus Nielsen. Encryption to the future - A paradigm for sending secret messages to future (anonymous) committees. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part III, volume 13793 of LNCS, 151–180. December 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-22969-5_6.
[CF85]
Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme (extended abstract). In 26th FOCS, 372–382. October 1985. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1985.2.
[CFF+21]
Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaïs Querol, and Hadrián Rodríguez. Lunar: A toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 3–33. December 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-92078-4_1.
[CHM+20]
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, 738–768. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45721-1_26.
[CS03]
Jan Camenisch and Victor Shoup. Practical verifiable encryption and decryption of discrete logarithms. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, 126–144. August 2003. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_8.
[DDOS19]
Cyprien Delpech de Saint Guilhem, Lauren De Meyer, Emmanuela Orsini, and Nigel P. Smart. BBQ: using AES in picnic signatures. In Kenneth G. Paterson and Douglas Stebila, editors, SAC 2019, volume 11959 of LNCS, 669–692. August 2019. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-38471-5_27.
[DFMS22]
Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Online-extractability in the quantum random-oracle model. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part III, volume 13277 of LNCS, 677–706. May / June 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-07082-2_24.
[DHMW23]
Nico Döttling, Lucjan Hanzlik, Bernardo Magri, and Stella Wohnig. Mcfly: verifiable encryption to the future made practical. In Foteini Baldimtsi and Christian Cachin, editors, Financial Cryptography and Data Security - 27th International Conference, FC 2023, Bol, Brač, Croatia, May 1-5, 2023, Revised Selected Papers, Part I, volume 13950 of Lecture Notes in Computer Science, 252–269. Springer, 2023. https://doi.org/10.1007/978-3-031-47754-6_15.
[DOT21]
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, and Titouan Tanguy. Limbo: efficient zero-knowledge MPCitH-based arguments. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021, 3022–3036. November 2021. ACM Press. https://doi.org/10.1145/3460120.3484595.
[EG21]
Electionguard specification. 2021.
[Fel87]
Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th FOCS, 427–437. October 1987. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.1987.4.
[FO99]
Eiichiro Fujisaki and Tatsuaki Okamoto. How to enhance the security of public-key encryption at minimum cost. In Hideki Imai and Yuliang Zheng, editors, PKC'99, volume 1560 of LNCS, 53–68. March 1999. Springer, Heidelberg. https://doi.org/10.1007/3-540-49162-7_5.
[FO13]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1):80–101, January 2013. https://doi.org/10.1007/s00145-011-9114-1.
[FR23]
Thibauld Feneuil and Matthieu Rivain. Threshold linear secret sharing to the rescue of MPC-in-the-head. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part I, volume 14438 of LNCS, 441–473. December 2023. Springer, Heidelberg. https://doi.org/10.1007/978-981-99-8721-4_14.
[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, 186–194. August 1987. Springer, Heidelberg. https://doi.org/10.1007/3-540-47721-7_12.
[GCZ16]
Steven Goldfeder, Melissa Chase, and Greg Zaverucha. Efficient post-quantum zero-knowledge and signatures. 2016.
[GH03]
Yitchak Gertner and Amir Herzberg. Committing encryption and publicly-verifiable signcryption. 2003.
[GHL+22]
Tim Güneysu, Philip W. Hodges, Georg Land, Mike Ounsworth, Douglas Stebila, and Greg Zaverucha. Proof-of-possession for KEM certificates using verifiable generation. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, 1337–1351. November 2022. ACM Press. https://doi.org/10.1145/3548606.3560560.
[GK22]
Google Cloud Key Management Service Documentation: Key purposes and algorithms. February 2022.
[GLOV12]
Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, and Ivan Visconti. Constructing non-malleable commitments: A black-box approach. In 53rd FOCS, 51–60. October 2012. IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2012.47.
[GMO16]
Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. ZKBoo: faster zero-knowledge for Boolean circuits. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016, 1069–1083. August 2016. USENIX Association. https://doi.org/?
[GOS06]
Jens Groth, Rafail Ostrovsky, and Amit Sahai. Perfect non-interactive zero knowledge for NP. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, 339–358. May / June 2006. Springer, Heidelberg. https://doi.org/10.1007/11761679_21.
[Gro16]
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, 305–326. May 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-49896-5_11.
[HHK17]
Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki-Okamoto transformation. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, 341–371. November 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-70500-2_12.
[HLR21]
Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, 750–760. ACM, 2021. https://doi.org/10.1145/3406325.3451116.
[IKOS07]
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, 21–30. June 2007. ACM Press. https://doi.org/10.1145/1250790.1250794.
[Kal22]
Daniel Kales. Implementation of bn++ and helium signatures. 2022.
[Kat21]
Shuichi Katsumata. A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, 580–610. Virtual Event, August 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-84245-1_20.
[Kiy20]
Susumu Kiyoshima. Round-optimal black-box commit-and-prove with succinct communication. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, 533–561. August 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-56880-1_19.
[KKW18]
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, 525–537. October 2018. ACM Press. https://doi.org/10.1145/3243734.3243805.
[KMP16]
Eike Kiltz, Daniel Masny, and Jiaxin Pan. Optimal security proofs for signatures from identification schemes. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, 33–61. August 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-53008-5_2.
[KOS18]
Dakshita Khurana, Rafail Ostrovsky, and Akshayaram Srinivasan. Round optimal black-box “commit-and-prove”. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part I, volume 11239 of LNCS, 286–313. November 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-03807-6_11.
[KSSW22]
Matthias J. Kannwischer, Peter Schwabe, Douglas Stebila, and Thom Wiggers. Improving software quality in cryptography standardization projects. In IEEE European Symposium on Security and Privacy, EuroS&P 2022 - Workshops, Genoa, Italy, June 6-10, 2022, 19–30. IEEE, 2022. https://doi.org/10.1109/EUROSPW55150.2022.00010.
[KZ22]
Daniel Kales and Greg Zaverucha. Efficient lifting for shorter zero-knowledge proofs and post-quantum signatures. 2022.
[LCKO19]
Jiwon Lee, Jaekyoung Choi, Jihye Kim, and Hyunok Oh. SAVER: snark-friendly, additively-homomorphic, and verifiable encryption and decryption with rerandomization. 2019.
[LN17]
Vadim Lyubashevsky and Gregory Neven. One-shot verifiable encryption from lattices. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part I, volume 10210 of LNCS, 293–323. April / May 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-56620-7_11.
[MBKM19]
Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, 2111–2128. November 2019. ACM Press. https://doi.org/10.1145/3319535.3339817.
[Mic00]
Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253–1298, 2000. https://doi.org/?
[NAB+19]
Michael Naehrig, Erdem Alkim, Joppe Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Christopher Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM. Technical Report, National Institute of Standards and Technology, 2019.
[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, 1717–1731. November 2020. ACM Press. https://doi.org/10.1145/3372297.3417236.
[Pas03]
Rafael Pass. On deniability in the common reference string and random oracle model. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, 316–337. August 2003. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_19.
[Ped92]
Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, 129–140. August 1992. Springer, Heidelberg. https://doi.org/10.1007/3-540-46766-1_9.
[PK15]
OASIS Standard: PKCS #11 Cryptographic Token Interface Base Specification Version 2.40. April 2015.
[PK22]
OASIS Standard: PKCS #11 Cryptographic Token Interface Current Mechanisms Specification Version 3.0. 2022.
[PS00]
Guillaume Poupard and Jacques Stern. Fair encryption of RSA keys. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, 172–189. May 2000. Springer, Heidelberg. https://doi.org/10.1007/3-540-45539-6_13.
[SAB+20]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical Report, National Institute of Standards and Technology, 2020.
[Sch91]
Claus-Peter Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, January 1991. https://doi.org/10.1007/BF00196725.
[Set20]
Srinath Setty. Spartan: efficient and general-purpose zkSNARKs without trusted setup. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, 704–737. August 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-56877-1_25.
[Sta96]
Markus Stadler. Publicly verifiable secret sharing. In Ueli M. Maurer, editor, EUROCRYPT'96, volume 1070 of LNCS, 190–199. May 1996. Springer, Heidelberg. https://doi.org/10.1007/3-540-68339-9_17.
[TZ21]
Akira Takahashi and Greg Zaverucha. Verifiable Encryption from MPC-in-the-Head. 2021.
[YC22]
Yubico YubiHSM2 Guide: Backing Up Key Material. 2022.
[YY98]
Adam Young and Moti Yung. Auto-recoverable auto-certifiable cryptosystems. In Kaisa Nyberg, editor, EUROCRYPT'98, volume 1403 of LNCS, 17–31. May / June 1998. Springer, Heidelberg. https://doi.org/10.1007/BFb0054114.
[ZCD+20]
Greg Zaverucha, Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Jonathan Katz, Xiao Wang, Vladmir Kolesnikov, and Daniel Kales. Picnic. Technical Report, National Institute of Standards and Technology, 2020.

PDFPDF Open access

History
Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Akira Takahashi and Greg Zaverucha, "Verifiable Encryption from MPC-in-the-Head," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a3wa3zl7s.

License

Copyright is held by the author(s)

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