ハードウェアセキュリティの最新動向
格子に基づく耐量子計算機暗号では、次数 n = 256 の多項式の掛け算を何度も行う。係数どうしをすべて掛け合わせる素朴な方法では約 n² 回、数論変換(NTT)を使う方法では約 n log₂ n 回の掛け算が必要とすると、NTTを使うことで掛け算の回数がおよそ何分の1になるかとして、最も近いものはどれか。
- A約8分の1
- B約32分の1
- C約256分の1
答えと解説を見る
正解：B. 約32分の1
素朴な方法では n² = 256² = 65,536 回、NTTを使う方法では n log₂ n = 256 × 8 = 2,048 回なので、65,536 ÷ 2,048 = 32 で、約32分の1になります。数論変換は、高速フーリエ変換と同じ考え方を、素数を法とする整数の世界で行う変換で、変換した後は係数ごとの掛け算だけで済みます。ML-KEMは係数を q = 3329 を法として扱い、NTTで計算することを前提に設計されているので、NTTの回路は耐量子計算機暗号の加速器の中心的な部品になります。また、ML-KEMやML-DSAは、行列や乱数を作るのにSHA-3の仲間の関数(SHAKE)を多く使うので、その加速器も効果があります。
- A. log₂ n = log₂ 256 = 8 だけを答えた値です。比は n² ÷ (n log₂ n) = n ÷ log₂ n です。
- B. 正しい。256 ÷ 8 = 32 です。
- C. n² ÷ n = n で、log₂ n で割るのを忘れた値です。