CRYSTALS-Dilithium is a digital signature scheme selected by the NIST standardization for post-quantum cryptography. Greconici et al. (at TCHES 2021) proposed several implementation strategies based on the trade-off between computation time and stack size, i.e., time-memory trade-off, of CRYSTALS-Dilithium for IoT devices, but a suitable design for the IoT devices is still unknown due to lack of experiments. In this paper, we provide a detailed analysis and parameterize of the trade-off between computation time and stack size for the signing algorithm of CRYSTALS-Dilithium. We first conduct systematic evaluations of the strategies by Greconici et al. to understand their impact on the trade-off described above. Next, we propose a new implementation method of CRYSTALS-Dilithium, which parameterizes the trade-off by generalizing the systematic evaluation. We also conduct experiments by implementing the proposed method on a hardware board for IoT devices. The most remarkable result is that the trade-off between the computation time and the stack size is non-linear: notably, reducing the stack size also indicates an improvement in the computation time with respect to an implementation for minimizing the stack size.

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

Parameterizing Time-Memory Trade-Off for Flexible Implementation of CRYSTALS-Dilithium

  • Yasushi Takahashi,
  • Naohisa Nishida,
  • Yuji Unagami,
  • Saburo Toyonaga,
  • Naoto Yanai,
  • Yasuhiko Ikematsu,
  • Koji Nuida,
  • Masaya Yasuda

摘要

CRYSTALS-Dilithium is a digital signature scheme selected by the NIST standardization for post-quantum cryptography. Greconici et al. (at TCHES 2021) proposed several implementation strategies based on the trade-off between computation time and stack size, i.e., time-memory trade-off, of CRYSTALS-Dilithium for IoT devices, but a suitable design for the IoT devices is still unknown due to lack of experiments. In this paper, we provide a detailed analysis and parameterize of the trade-off between computation time and stack size for the signing algorithm of CRYSTALS-Dilithium. We first conduct systematic evaluations of the strategies by Greconici et al. to understand their impact on the trade-off described above. Next, we propose a new implementation method of CRYSTALS-Dilithium, which parameterizes the trade-off by generalizing the systematic evaluation. We also conduct experiments by implementing the proposed method on a hardware board for IoT devices. The most remarkable result is that the trade-off between the computation time and the stack size is non-linear: notably, reducing the stack size also indicates an improvement in the computation time with respect to an implementation for minimizing the stack size.