山田 麟太郎
耐量子計算機暗号の候補の一つに格子問題に基づく暗号方式がある. 格子問題の中でも, 米国標準技術研究所 (NIST) によって標準規格化済みの 3 方式のうち 2 方式で使用されている MLWE(Module Learning with Errors) 問題は重要である. MLWE 問題の一種として, 代数体の整数環上で誤差付き多元連立一次方程式を解く Ring-LWE(RLWE) 問題が存在する. RLWE 問題に基づく, Torus Fully Homomorphic Encryption(TFHE) 方式や Cheon-Kim-Kim-Song(CKKS) 方式は, 準同型性を有する. 準同型暗号では，暗号化された
平文を復号することなく加算や乗算を行うことが可能であり，機械学習やプライバシー保護計算などの分野において注目されている．RLWE 問題に基づく準同型暗号方式では, 平文に僅かな誤差を加えることで暗号化を行うが, 準同型演算を繰り返すことで暗号文中の誤差が増加し, 閾値を超えると復号不能となる問題がある. 既存研究では, 平文 m の暗号文 Enc(m) を入力として誤差を閾値以下に低減した暗号文 Enc(m) として出力する Bootstrapping (BT) が提案されている. さらに, BT の拡張版として, 入力暗号文を Enc(m)として, 関数 f に対して Enc(f (m)) を出力する Functional Bootstrapping (FBT) が提案されている. また, TFHE 暗号方式では, 多段の FBT を合成する際に, 計算量のボトルネックになる FBT の適用回数を線形に抑制する構造として Chaining 手法が提案されている. 既存の Chaining 手法の課題として, TFHE 暗号方式は高速な FBT 処理に優れる一方で, 単一の暗号文に複数の平文値を格納し同時に演算を行う Single Instruction Multiple Data (SIMD) 並列性を持たないことが挙げられる. 本研究の目的は, RLWE 暗号文空間における多倍長整数の桁上げ加算と多倍長比較演算という 2 つの演算に対して, SIMD 並列性に優れた Chaining 手法を構築することである. 本研究では, SIMD 並列性に優れた RLWE 暗号として CKKS 方式に着目した. 多倍長整数を表す RLWE サンプルを CKKS 暗号文と解釈した上で, CKKS 暗号文空間で逐次的な FBT を合成する Chaining 構造を構成する. さらに, FBT 処理後の CKKS 暗号文を再び RLWE サンプルへと解釈を戻した際に, 正しい Enc(f (m)) が得られることを確認する. また, D 桁の多倍長整数に対して, 提案した Chaining 手法における FBT の適用回数が O(D) であることを理論的に示した. 実験評価では, 提案手法と TFHE 暗号方式における Chaining 手法を比較して, SIMD 並列性処理スロットあたりにおいて, 多倍長桁上げ加算で 52.9～55.5 倍, 多倍長比較演算で 36.0～42.0 倍の高速化を達成した. Chaining 手法は任意の関数に対して一般に構成可能なものではないため，本研究ではその適用可能性を検証する第一段階として，多倍長整数の桁上げ加算および多倍長比較演算に焦点を当てた．本研究は，SIMD 並列性を有する RLWE ベース暗号において, より多様な関数に対して Chaining 手法を構成する際の基礎的知見を与えるものである．
