Efficient verifiable partially-decryptable commitments from lattices and applications

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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.

Original languageEnglish
Title of host publication25th IACR International Conference on Practice and Theory of Public-Key Cryptography Virtual Event, March 8–11, 2022 Proceedings, Part I
EditorsGoichiro Hanaoka, Junji Shikata, Yohei Watanabe
Place of PublicationCham Switzerland
Number of pages32
ISBN (Electronic)9783030971212
ISBN (Print)9783030971205
Publication statusPublished - 2022
EventInternational Conference/Workshop on Practice and Theory in Public Key Cryptography 2022 - Virtual
Duration: 8 Mar 202211 Mar 2022
Conference number: 25th
https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/978-3-030-97121-2 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference/Workshop on Practice and Theory in Public Key Cryptography 2022
Abbreviated titlePKC 2022
Internet address


  • Accountable Ring Signature
  • Auditable RingCT
  • Lattice
  • Verifiable Partially-Decryptable Commitment
  • Zero Knowledge

Cite this