Paper 2023/826
Ring/Module Learning with Errors under Linear Leakage -- Hardness and Applications
Abstract
This paper studies the hardness of decision Module Learning with Errors (\MLWE) under linear leakage, which has been used as a foundation to derive more efficient lattice-based zero-knowledge proofs in a recent paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21). Unlike in the plain \LWE~setting, it was unknown whether this problem remains provably hard in the module/ring setting. This work shows a reduction from the search \MLWE~to decision \MLWE~with linear leakage. Thus, the main problem remains hard asymptotically as long as the non-leakage version of \MLWE~is hard. Additionally, we also refine the paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21) by showing a more fine-grained tradeoff between efficiency and leakage. This can lead to further optimizations of lattice proofs under the paradigm.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in PKC 2024
- Keywords
- Ring/Module LWELinear LeakageRejection SamplingMore Efficient NIZK
- Contact author(s)
-
wzdstill @ sjtu edu cn
laiqq @ snnu edu cn
fenghao liu @ fau edu - History
- 2024-04-07: last of 4 revisions
- 2023-06-03: received
- See all versions
- Short URL
- https://ia.cr/2023/826
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/826,
author = {Zhedong Wang and Qiqi Lai and Feng-Hao Liu},
title = {Ring/Module Learning with Errors under Linear Leakage -- Hardness and Applications},
howpublished = {Cryptology ePrint Archive, Paper 2023/826},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/826}},
url = {https://eprint.iacr.org/2023/826}
}
