Module Learning with Errors with Truncated Matrices
摘要
The Module Learning with Errors ( \(\textsf{MLWE}\) ) problem is one of the most commonly used hardness assumption in lattice-based cryptography. In its standard version, a matrix \(\textbf{A}\) is sampled uniformly at random over a quotient ring \(R_q\) , as well as noisy linear equations in the form of \(\textbf{A}\textbf{s}+ \textbf{e}\bmod q\) , where \(\textbf{s}\) is the secret, sampled uniformly at random over \(R_q\) , and \(\textbf{e}\) is the error, coming from a Gaussian distribution. Many previous works have focused on variants of \(\textsf{MLWE}\) , where the secret and/or the error are sampled from different distributions. Only few works have focused on different distributions for the matrix \(\textbf{A}\) . One variant proposed in the literature is to consider matrix distributions, where the low-order bits of a uniform \(\textbf{A}\) are deleted. This seems a natural approach in order to save in bandwidth. We call it truncated \(\textsf{MLWE}\) . In this work, we show that the hardness of standard \(\textsf{MLWE}\) implies the hardness of truncated \(\textsf{MLWE}\) , both for search and decision versions. Prior works only covered the search variant and relied on the (module) \(\textsf{NTRU}\) assumption, limitations which we are able to overcome. Overall, we provide two approaches, offering different advantages. The first uses a general Rényi divergence argument, applicable to a wide range of secret/error distributions, but which only works for the search variants of (truncated) \(\textsf{MLWE}\) . The second applies to the decision versions, by going through an intermediate variant of \(\textsf{MLWE}\) , where additional hints on the secret are given to the adversary. However, the reduction makes use of discrete Gaussian distributions.