Paper 2021/1704

Verifiable Encryption from MPC-in-the-Head

Akira Takahashi, J.P. Morgan AI Research & AlgoCRYPT CoE
Greg Zaverucha, Microsoft Research

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.

Note: Full version of the paper published in IACR CiC Volume 1, Issue 1, 2024.

Available format(s)
Publication info
A major revision of an IACR publication in CIC 2024
verifiable encryptionzero knowledge proofMPC-in-the-head
Contact author(s)
takahashi akira 58s @ gmail com
gregz @ microsoft com
2024-04-26: last of 2 revisions
2021-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akira Takahashi and Greg Zaverucha},
      title = {Verifiable Encryption from {MPC}-in-the-Head},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1704},
      year = {2021},
      doi = {10.62056/a3wa3zl7s},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.