返信
期待されているようなので, Gentryの暗号 (STOC 2009) については簡単な解説を後日書きます. 今のところフルヴァージョンは公開されていないので, 詳しいテクニックはぼかして書く方向で.
乗法的準同型性, 加法的準同型性, 制限付き加法的準同型性, 制限付き環準同型性, 制限無し環準同型性辺りといった歴史を押さえて書いた方が良いか. 30年来の未解決問題でもあったことだし.
ものすごい大雑把に言うとNTRUとGGHの拡張みたいなもんです. アイデアはそっちに近い.
ただこれだけだとANDやORの素子を評価するたびにエラーが溜まっていくので, 一旦内部で復号してエラーをキャンセルします. そのために最近流行のKDM安全性を仮定して, 秘密鍵を暗号化してそれを公開鍵に含めておく. すると, 復号回路をエミュレート出来るというアイデアです.
あと取り急ぎ指摘しておくと,
- Applebaum, Cash, Peikert, and Sahai (CRYPTO 2009) のは関連あるっちゃありますけど, 直接的では無いです.
- Cloud(SaaS)に任せられる仕事とは何か - kgbu?
正しいアブストラクトの訳は以下.
アブスト和訳
完全な環準同型性を持つ公開鍵暗号方式 -- すなわち、 復号することなく、データの暗号文のみから、データを回路に入力したときの出力の暗号文を得ることが出来る方式 -- を提案する。解決策は3段階に分かれる。まず、一般的な結果を示す。任意の回路の評価を許す暗号化方式を構成するためには、（多少拡張した形の）自身の復号回路を評価できれば十分であることを示す。このように（拡張）復号回路を評価可能な暗号化方式のことを「ブートストラップ可能である」と呼ぶ。
We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable.
次に、ほぼブートストラップ可能である、イデアル格子を用いた公開鍵暗号方式について説明する。
Next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable.
格子ベースの暗号方式は、復号の回路計算量が低い。大抵の場合、NC1*1に含まれる内積の計算が主である。また、イデアル格子を用いることで加法的準同型性と乗法的準同型性が導入される。これらの準同型性は、多項式環中の格子として表現された公開鍵として用いられるイデアルを法に取る。また、これらの準同型性は一般の回路を評価する際に必要である。
Lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. Also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits.
残念ながら、最初の方式はブートストラップ可能ではない。格子の次元のログオーダーの深さで表現される回路のみ正しく評価可能である。復号回路の深さも格子の次元のログオーダーであるが、これは評価可能な回路の深さよりは大きい。従って、最終ステップでは、評価出来る回路の深さを減らすことなく、復号回路の深さを減らすためにいかに方式を変更するかを示す。抽象的に言えば、復号化の計算量を減らすために暗号化の際に復号の一部を行う。これはserver-aided暗号方式 *2 で、 サーバが復号化の一部を行うことと非常に似ている。
Unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. In the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.
*1:2入力AND, OR, NOTからなる多項式サイズかつ深さがO(log n)の回路で判定可能な計算量クラス. 参考:Complexity Zoo:N - NC1
*2:これの定訳なんだっけ?
