完全準同型暗号
完全準同型暗号(Fully-Homomorphic-Encryption：FHE)
概要
2009年にGentryが初めて実現した
絶賛研究中
計算コストが高いが他者とのコミュニケーションコストがない
FHEの段階別分類
table:FHEの比較表
名称 乗算回数 計算速度
Somewhat HE 2、3回 高速
Leveled HE 事前に決定した回数 中速
FHE 理論上無限 遅い
Somewhat HE(SHE)
計算可能な乗算の回数を限定している
一般的に2、3回
Leveled-FHEやFHEよりも高速に計算することができる
Leveled FHE
事前に乗算可能な回数を決めて暗号化する手法
SHEよりも計算可能な乗算の回数を多く設定できる
計算速度はSHEよりは遅い
FHE
乗算の回数に制限がない
Bootstrapという処理を行なってノイズを除去している
この処理自体の時間が長い
30秒〜30分
計算時間が現実的ではない
→使用する暗号技術の選択方法は乗算の回数によって決める
2、3回だけ乗算する
SHE
事前に何回乗算するがわかっている
Leveled-FHE
何回乗算するか分からない
FHE
実現手法
FHE
2009年のGentryの手法
イデアル格子暗号
LWE(Learning-with-Errors)問題の困難性が暗号の源
計算を繰り返すたびにノイズがのる
LWEはノイズをのせることで解読困難性を実現しているため
特に、乗算ではものすごい勢いでノイズが大きくなり、復号不可能になる
Bootstrapという処理を施して解決している
蓄積されるノイズを除去する方法
計算コストが大きい
30秒ー30分
Bootstrap回数を減らすための研究が進行中
GSW方式
2013年にGentryらによって提案された
乗算時に必要だったパラメタを排除した
時間計算量は増えるが、空間計算量を減らした
IDベースFHEと属性ベースFHEを構築することができる
FHEW方式
上記のGSW方式を実装したもの
2015年にDucasらが実装
Leveled-FHE
BGV(Brakerski-Gentry-Vaikuntanathan)方式
Leveled-HE(完全準同型暗号ではないが、ある程度までは乗法ができる)
Ring-Learning-with-Errors(RLWE)問題を解読困難性としている
HElibというオープンソースライブラリで実装されている
IBM製
Bootstrapを実装しているためFHEにもできる
多項式環を用いた方法
暗号化空間を事前に複数用意しておく
乗算が行われるごとに空間のレベルを下げることで、ノイズを低減させることができる
これをModulus Switchingという
最初に用意する空間のレベルの数が乗算可能な回数になる(Leveled-HEの由来)
FV方式
ノイズ増加が小さい
MS Researchがライブラリを公開している
SEAL
YASHE方式
計算が高速
上記のFV方式と同様にMS Researchがライブラリを公開している
SEAL
Somewhat HE
SV方式
2010年にSmartらが開発
Bootstrapを使用していないためFHEではない
完全準同型暗号の実装まとめ
BGV方式
FV方式
YASHE方式
bootstrap処理を1秒未満で実現
上記のFHEWを超える性能
bootstrap処理を0.1秒未満で実現
参考文献