Paper 2022/142

Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications

Muhammed F. Esgin, Ron Steinfeld, and Raymond K. Zhao

Abstract

We introduce verifiable partially-decryptable commitments (VPDC), as a building block for constructing efficient privacy-preserving protocols supporting auditability by a trusted party. A VPDC is an extension of a commitment along with an accompanying proof, convincing a verifier that (i) the given commitment is well-formed and (ii) a certain part of the committed message can be decrypted using a (secret) trapdoor known to a trusted party. We first formalize VPDCs and then introduce a general decryption feasibility result that overcomes the challenges in relaxed proofs arising in the lattice setting. Our general result can be applied to a wide class of Fiat-Shamir based protocols and may be of independent interest. Next, we show how to extend the commonly used lattice-based `Hashed-Message Commitment' (HMC) scheme into a succinct and efficient VPDC. In particular, we devise a novel `gadget'-based Regev-style (partial) decryption method, compatible with efficient relaxed lattice-based zero-knowledge proofs. We prove the soundness of our VPDC in the setting of adversarial proofs, where a prover tries to create a valid VPDC output that fails in decryption. To demonstrate the effectiveness of our results, we extend a private blockchain payment protocol, MatRiCT, by Esgin et al. (ACM CCS '19) into a formally auditable construction, which we call MatRiCT-Au, with very low communication and computation overheads over MatRiCT.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2022
Keywords
LatticeZero KnowledgeVerifiable Partially-Decryptable CommitmentAuditable RingCTAccountable Ring Signature
Contact author(s)
muhammed esgin @ monash edu
ron steinfeld @ monash edu
raymond zhao @ monash edu
History
2022-02-09: received
Short URL
https://ia.cr/2022/142
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/142,
      author = {Muhammed F.  Esgin and Ron Steinfeld and Raymond K.  Zhao},
      title = {Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/142},
      year = {2022},
      url = {https://eprint.iacr.org/2022/142}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.