Paper 2021/1704

Verifiable Encryption from MPC-in-the-Head

Akira Takahashi, University of Edinburgh
Greg Zaverucha, Microsoft Research
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.

Note: Added implementation results and analyses of non-interactive VE schemes

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
verifiable encryptionzero knowledge proofMPC-in-the-head
Contact author(s)
takahashi akira 58s @ gmail com
gregz @ microsoft com
History
2023-10-16: revised
2021-12-31: received
See all versions
Short URL
https://ia.cr/2021/1704
License
Creative Commons Attribution
CC BY

BibTeX

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