Paper 2023/623

Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE

Duhyeong Kim, Intel (United States)
Dongwon Lee, Seoul National University
Jinyeong Seo, Seoul National University
Yongsoo Song, Seoul National University

In the last decade, zero-knowledge proof of knowledge protocols have been extensively studied to achieve active security of various cryptographic protocols. However, the existing solutions simply seek zero-knowledge for both message and randomness, which is an overkill in many applications since protocols may remain secure even if some information about randomness is leaked to the adversary. We develop this idea to improve the state-of-the-art proof of knowledge protocols for RLWE-based public-key encryption and BDLOP commitment schemes. In a nutshell, we present new proof of knowledge protocols without using noise flooding or rejection sampling which are provably secure under a computational hardness assumption, called Hint-MLWE. We also show an efficient reduction from Hint-MLWE to the standard MLWE assumption. Our approach enjoys the best of two worlds because it has no computational overhead from repetition (abort) and achieves a polynomial overhead between the honest and proven languages. We prove this claim by demonstrating concrete parameters and compare with previous results. Finally, we explain how our idea can be further applied to other proof of knowledge providing advanced functionality.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Zero-knowledgeProof of Plaintext KnowledgeBDLOPHint-MLWE
Contact author(s)
duhyeong kim @ intel com
dongwonlee95 @ snu ac kr
jinyeong seo @ snu ac kr
y song @ snu ac kr
2023-09-21: last of 2 revisions
2023-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Duhyeong Kim and Dongwon Lee and Jinyeong Seo and Yongsoo Song},
      title = {Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/623},
      year = {2023},
      doi = {10.1007/978-3-031-38554-4_18},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.