International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Duhyeong Kim , Intel Labs
Dongwon Lee , Seoul National University
Jinyeong Seo , Seoul National University
Yongsoo Song , Seoul National University
DOI: 10.1007/978-3-031-38554-4_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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.
  title={Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE},
  author={Duhyeong Kim and Dongwon Lee and Jinyeong Seo and Yongsoo Song},