Ring-LWE における NTT の並列計算の高速化手法

情報処理学会

書誌事項

タイトル別名
  • Acceleration of Parallel NTT Computation in Ring-LWE

説明

耐量子計算機暗号は，量子コンピュータでも解けないと信じられているより安全な暗号方式として，注目を集めている．耐量子計算機暗号でしばしば用いられる計算問題に Ring-LWE があり，Kyber や NTRU Prime などの様々なアルゴリズムの内部実装に用いられている．暗号システムは様々なデバイスで活用されることを踏まえると，耐量子計算機暗号の実用化にあたっては，計算を高速に行うことが重要であると言える．そこで，本研究では，Ring-LWE において多項式乗算を高速に行う手法として用いられる NTT を高速に実行する手法として，Garner's Algorithm を活用し，NTT の回数を削減できる手法を提案する．この手法により，NTT を独立に計算する従来の計算手法と比較して NTT の回数を最大 25% 削減した．

Post Quantum Cryptography is getting attention as a secure system of cryptography, in place of currently used public key cryptography. One mathematical problem often used in Post Quantum Cryptography is Ring-LWE, which is used in various algorithm (e.g. Kyber and NTRU prime). Since cryptosystem is implemented in various devices, it is important to conduct calculations quickly to realize Post Quantum Cryptography. This research proposes a method of accelerating NTT, which is used in NTT as a method to accelerate polynomial multiplication. This method utilizes Garner’s Algorithm and can reduce the number of times NTT is performed. This method reduces the number of times by up to 25% compared to previous methods that calculate NTT independently.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ