The Middle Product Learning With Errors ( \(\textsf{MP}\text {-}\textsf{LWE}\) ) problem was introduced in 2017 by Rosca, Sakzad, Steinfeld, and Stehlé (Crypto 2017). In their work and in a follow up work by Rosca, Stehlé, and Wallet (Eurocrypt 2018), the authors proved that \(\textsf{MP}\text {-}\textsf{LWE}\) is at least as hard as the Ring \(\textsf{LWE}\) problem over the field \(\mathbb {Q}[x]/f(x)\) , for an exponentially large class of polynomials f (with fixed degree and bounded coefficients). A few years later, Peikert and Pepin gave a new reduction from Ring \(\textsf{LWE}\) to \(\textsf{MP}\text {-}\textsf{LWE}\) (Journal of Cryptology 2024). This new reduction improved the results of Rosca et al. by increasing the set of polynomials f for which the reduction holds. However, even though the sets of polynomials covered by both reductions have exponential size, they remain negligible among the set of all polynomials of fixed degree and bounded coefficients. In this work, we provide a refined analysis of the reduction of Rosca et al. Our new analysis shows that the reduction of Rosca et al. actually covers a much larger class of polynomials than what was known before, containing (experimentally) at least \(90\%\) of all polynomials of fixed degree and bounded coefficients.

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

Improved Reduction from  \(\textsf{RLWE}\) to  \(\textsf{MP}\text {-}\textsf{LWE}\)

  • Rahinatou Yuh Njah Epouse Nchiwo,
  • Alice Pellet-Mary

摘要

The Middle Product Learning With Errors ( \(\textsf{MP}\text {-}\textsf{LWE}\) ) problem was introduced in 2017 by Rosca, Sakzad, Steinfeld, and Stehlé (Crypto 2017). In their work and in a follow up work by Rosca, Stehlé, and Wallet (Eurocrypt 2018), the authors proved that \(\textsf{MP}\text {-}\textsf{LWE}\) is at least as hard as the Ring \(\textsf{LWE}\) problem over the field \(\mathbb {Q}[x]/f(x)\) , for an exponentially large class of polynomials f (with fixed degree and bounded coefficients). A few years later, Peikert and Pepin gave a new reduction from Ring \(\textsf{LWE}\) to \(\textsf{MP}\text {-}\textsf{LWE}\) (Journal of Cryptology 2024). This new reduction improved the results of Rosca et al. by increasing the set of polynomials f for which the reduction holds. However, even though the sets of polynomials covered by both reductions have exponential size, they remain negligible among the set of all polynomials of fixed degree and bounded coefficients. In this work, we provide a refined analysis of the reduction of Rosca et al. Our new analysis shows that the reduction of Rosca et al. actually covers a much larger class of polynomials than what was known before, containing (experimentally) at least \(90\%\) of all polynomials of fixed degree and bounded coefficients.