Paper 2023/826 Original: eprint.iacr.org/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
- Preprint.
- History
- 2024-04-07: last updated
- 2023-06-03: published
- Short URL
- https://ia.cr/2023/826
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2023/826}
}