Scholarlink

In modern cryptography, structured lattices from ring-based LWE and NTRUNTRU are useful to construct efficient and compact cryptosystems. Search problems of ring-based LWE and NTRU can be reduced to particular cases of the shortest vector problemShortest vector problem (SVP) on Kannan’s embedding and the NTRU lattices, respectively. In this paper, we expand Kannan’s embedding and the NTRU lattices for solving the ring-based LWE and the NTRU problems, respectively. Both expanded lattices include many short vectors that are amplified by using rotations of secret short vectors. Since many target short vectors are embedded in our expanded lattices, it could increase the success probability for solving the ring-based LWE and the NTRU problems by using the block Korkine–Zolotarev (BKZ) reduction algorithm. We demonstrate by experiments the efficacy of our expansions from viewpoints of the success probability and the running time.

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

Expanded Lattices for Solving Ring-Based LWE and NTRU Problems

  • 章节

  • 出版模式：

    开放获取

  • 发表日期：

    2026年

查看全文
  • Satoshi Nakamura,
  • Masaya Yasuda

摘要

In modern cryptography, structured lattices from ring-based LWE and NTRUNTRU are useful to construct efficient and compact cryptosystems. Search problems of ring-based LWE and NTRU can be reduced to particular cases of the shortest vector problemShortest vector problem (SVP) on Kannan’s embedding and the NTRU lattices, respectively. In this paper, we expand Kannan’s embedding and the NTRU lattices for solving the ring-based LWE and the NTRU problems, respectively. Both expanded lattices include many short vectors that are amplified by using rotations of secret short vectors. Since many target short vectors are embedded in our expanded lattices, it could increase the success probability for solving the ring-based LWE and the NTRU problems by using the block Korkine–Zolotarev (BKZ) reduction algorithm. We demonstrate by experiments the efficacy of our expansions from viewpoints of the success probability and the running time.