Paper 2023/623
Toward Practical Lattice-based Proof of Knowledge from Hint-MLWE
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in CRYPTO 2023
- DOI
- 10.1007/978-3-031-38554-4_18
- Keywords
- 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 - History
- 2023-09-21: last of 2 revisions
- 2023-05-01: received
- See all versions
- Short URL
- https://ia.cr/2023/623
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/623,
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},
url = {https://eprint.iacr.org/2023/623}
}