Ring/Module Learning with Errors Under Linear Leakage – Hardness and Applications

This paper studies the hardness of decision Module Learning with Errors ( \(\textsf{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 \(\textsf{LWE}\)  setting, it was unknown whether this problem remains provably hard in the module/ring setting. This work shows a reduction from the standard search \(\textsf{MLWE}\)  to decision \(\textsf{MLWE}\)  with linear leakage. Thus, the main problem remains hard asymptotically as long as the non-leakage version of \(\textsf{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.