前置き

これは準同型暗号の最前線1（入門編)のUpdate版(補足という方が正確な気がするが)を書いておくのは公益性が高そうだ、ということで書いた記事。
入門編ということで最初に言っておくが、英語版のwikipediaはよく書かれている。
また、私は格子暗号をベースとした完全準同型暗号を主に扱っているので、楕円曲線をベースとしたものはほとんど扱わない。
気が向いたら書き足していく感じで行こうと考えている。

準同型暗号(Homomorphic Encryption)とは

準同型暗号とは、暗号文を復号することなしに演算を行うことを許すような暗号のことである。
RSA暗号といえば、公開鍵暗号として著名であるが、完全準同型暗号が最初に提案されたのはRSAが提案された翌年、1978年のことである。(ちなみにRSAはその名前を冠した学会があったりする)
RSAは公開鍵暗号であると同時に、乗算をサポートするPHEでもあることから着想を得たのだと思われる。

他の秘密計算手法との違い

準同型暗号以外の代表的な秘密計算手法として、Garbled Circuit(GC)、Secret Sharing(秘密分散)とTrusted Execution Environment(TEE)が挙げられるだろう。
TEEはそもそもチップメーカなどを信頼しなければならないという点で暗号学だけに依拠する他の手法とは異なる。
GCは秘密鍵を持つパーティが一番多くの演算しなければならないので計算処理のオフロードができないという点で準同型暗号とは異なる。
秘密分散は計算の過程でパーティ同士が頻繁に通信する必要があり、その点で準同型暗号と異なる。

準同型暗号が解決しないこと

準同型暗号の代表的な問題点は、malleability と呼ばれるものである。
これは、「準同型暗号によって他者に暗号文を操作させることを許す場合、その操作が本当に暗号を生成したパーティが許す範囲の演算であるかを保証することが出来ない」というものである。(これは厳密な定義を参照して訳したわけではないのでラフな定義であることは申し添えておく。厳密な良い言い回しがあったら教えていただきたい。)
これはTEEでも同様の問題があり、GCはこの問題がない。(これはGCの特筆すべき点である)
秘密分散に関しては私は把握していないので詳しい方が居たらお教えいただきたい。(なにかの拍子に調べたら追記するだろうけれど)
これを解決するにはVerifiable Computationなどの他の概念と統合するか、Keyedと呼ばれるタイプのHEを使うことなどを検討する必要がある。

格子暗号とは

耐量子コンピュータ暗号の有力な候補の一つとされている暗号形式である。代数ではなくベクトルを基本的な概念とする暗号であるのだが、細かい話は理論編においておく。

準同型暗号の分類

準同型暗号には、その性質によって4つの種類がある。楕円曲線など代数的構造をベースとしたものはPHEかSHEに入る。

PHE (Partial Homomorphic Encryption;部分準同型暗号)

GHE(Group Homomorphic Encryption)と呼ばれていたこともあった。剰余環上の加算か乗算の片方ができるという意味であることが多い。著名なのはRSA暗号、ElGamal暗号、Paillier暗号など代数ベースのものである。格子暗号はそれ単体でも一般的に加法をサポートするPHEであるが、PHEとして使われることはまずない。
どういう原理でRSA暗号がPHEになるかは英語版のwikipediaに書いてあるので省略する。ElGamal暗号の場合についてはクラウドを支えるこれからの暗号技術に日本語での説明がある。もしくは、準同型暗号の最前線2（原理編）を見てもよいだろう。

SHE (Somewhat Homomorphic Encryption)

演算回数に制限があるが、加算と乗算の両方ができるような暗号である。準同型暗号の最前線2（原理編）で説明されているのもSHEである。一般に乗算の方の制限のほうが厳しい。乗算できる回数がn回の場合、n-level SHEというらしい。ちなみに、n-level SHEを2n-level SHEにする手法としてCatalano-Fiore変換がある。

LHE (Leveled Homomorphic Encryption)

演算回数に制限があるが、その制限が定数値ではなく変更可能なパラメータになっているような暗号。比較的新しい分類なためか、FHEといいつつLHEであることがたまにある。最初の論文ではLHEという言葉は導入されていないのも影響しているか。残念ながら初出は知らない。
LHE以上は格子暗号ベースのものしか私は知らない。また、少なくともこの記事における分類の第二世代以降のFHEはすべてLHEでもある。
演算回数に制限があるとはいってもSHEよりは評価可能な関数の種類が多く、またFHEよりはずっと高速であるので、最近(2020年頃)の準同型暗号を実用的な処理をやろうという試みはLHEで構成されていることが多い印象である。

FHE (Fully Homomorphic Encryption;完全準同型暗号)

FHEは加算も乗算も好きなだけ行うことができる準同型暗号である。現時点で存在するものはすべて2009年にGentryさんが博士論文で提案したBootstrappingという概念をその構成の根幹としている。Bootstrappingとは、準同型暗号上で復号と等価な処理を行うことで演算可能回数をリセットする演算である。
英語版Wikipediaにならって、ここでもFHEを世代わけして紹介する。

第一世代

Gentryさんの博士論文で提案された最初の構成はここに含まれる。実際に実装すると必要なストレージが1TBとかを超えると言われており、非現実的ではあったが、Bootstrappingを提案したという点でまさしくseminal workである。
比較的現実的に使える手法としてはSmart-Vercauteren(SV)がある。SVの実装にはたとえばlibScarabがある。

第二世代

代表的なのはBrakerski-Gentry-Vaikuntanathan(BGV)とBrakerski/Fan-Vercauteren(BFV)である。この世代の特徴はLHEとしての機能が導入されたことと、SV packingなどと呼ばれるSIMD的な演算が可能であることである。実装としてはHElibやMicerosoft SEALがある。
英語版wikipediaだとYASHEも挙げられているが、この攻撃のせいで実用的でなくなったため最近みなくなった模様。

第三世代

代表的なのはGentry-Sahai-Waters(GSW)、FHEW、TFHEである。この世代の特徴はGSWで導入されたDecompositionという操作で、これによって乗算によって生じるノイズ(格子暗号ではノイズが大きな役割を果たすのだがそれは理論編で)をべき乗から対数に落とすことができること、第二世代までの整数の演算ではなく論理演算を準同型暗号上で評価する基本的な演算とすること、Bootstrappingが他の世代に比して圧倒的に速いことである。(TFHEで10ms程度、他の世代は現状(2020年頃)分単位はかかると思って良い)GSWの実装はぱっとは思いつかないが、FHEWは公式実装を、TFHEは私の実装(公式実装より速いし機能が多い)を挙げておこう。

第四世代

第四世代に相当するのは現状Cheon-Kim-Kim-Song(CKKS)のみである。第四世代と言っているが、第三世代とはほぼ関連がなく、第二世代の発展形なので第二世代に分類しても良いといえばよい。この世代の特徴は固定小数点数(より厳密には実数ではなく複素数)を評価することに向いていることである。この特徴から、準同型暗号上で深層学習をするのに使いやすいということで今一番流行っている感じがある。FHEとしては(速度ももちろん問題ではあるのだが)Bootstrappingをする際に保持できる精度が少ないことが特有の問題になっていて2020年もそれを改善したと主張する論文が出ている。実装としては、Micerosoft SEAL、Palisade、HEAANとLattigoあたりが挙げられるだろう。

応用例

準同型暗号の応用先を準同型暗号の最前線1（入門編)に追加して挙げておこう。

計算処理のオフロード

ようはクラウドコンピューティングを準同型暗号上でやろうという話である。なんでこれを最初に持ってくるかというとこれで論文を書いたからである。
2020年現在のクラウドコンピューティングはGCPがAMDのTEEに基づいた保護を、AzureがIntel SGXが使えるインタンスを提供している程度で、基本的にはクラウドベンダにはクライアントがどんな処理をしているかは筒抜けである。(TEEにしたって悪意ある人間がハードウェアに常時アクセス可能な状態では保護が十分であるかは疑わしい)準同型暗号を用いれば、クラウドベンダに何をやっているかを教えずに計算のオフロードをすることが理論的に可能である。
未踏の成果発表会のビデオが一番わかり易いだろうか。

Federated Learning

端的に言えば、深層学習を準同型暗号上でしたいよねという話である。(別に他の機械学習手法でもいいのだが、流行りもあって大体深層学習が念頭に置かれる)わかりやすいのは心臓の画像みたいな医療データを扱う場合の深層学習である。推論だけをサービスとして提供するのはまだなんとかなるのだが、学習の方をやるのは暗号学的課題(セキュリティ敵のほうがいいのだろうか)が山積みなので、今現在も盛んに研究が行われているところである。他の秘密計算手法とミックスするような形の手法も存在するし、必ずしも準同型暗号でなければいけないアプリではないことは注意が必要である。秘密計算全体としては電子投票とこれがキラーアプリだと個人的には思っている。
このIACRの発表動画が知っている中ではわかりやすいか。
機械学習でHEを使うためのフレームワークとしてはHE Transformer for nGraph、TF EncryptedやPySyftあたりを挙げておくが、私個人は機械学習に詳しくないため使ったことも比較したこともないので紹介に留めさせていただきたい。

次回

Update版ということで同じ感じの構成にしようと思うのだが原理編でしゃべるなら講義資料がを下敷きにTFHEについて触れるか、OpenMindの解説記事をベースにCKKSに触れるかなのだが、どっちも重そうで気分次第という感じである。(2021年5月追記目次見ればわかるとおり結局TFHEをやっている。BFVもやりたい気持ちはある)TFHEの解説は英語版も書きたいし。理論編は格子暗号とノイズの話をすればいいんだとは思うが。まぁ義務ではなく思いつきなので気が向けば書くという感じがある。

(完全)準同型暗号の最前線1（入門編）

目次

前置き