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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Module Learning with Errors with Truncated Matrices

  • Katharina Boudgoust,
  • Hannah Keller

摘要

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.