返信

ものすごい大雑把に言うとNTRUとGGHの拡張みたいなもんです. アイデアはそっちに近い.
ただこれだけだとANDやORの素子を評価するたびにエラーが溜まっていくので, 一旦内部で復号してエラーをキャンセルします. そのために最近流行のKDM安全性を仮定して, 秘密鍵を暗号化してそれを公開鍵に含めておく. すると, 復号回路をエミュレート出来るというアイデアです.

あと取り急ぎ指摘しておくと,

• Applebaum, Cash, Peikert, and Sahai (CRYPTO 2009) のは関連あるっちゃありますけど, 直接的では無いです.
• これの主題は, LWE仮定からKDM-secureな公開鍵暗号方式, LPN仮定からKDM-secureな秘密鍵方式, LPN仮定から線形伸長可能な擬似乱数生成器とかです. 計算量が低い点とKDM安全性は共通しています.
• Cloud(SaaS)に任せられる仕事とは何か - kgbu?
• イデアルの束(Lattice)と訳されていますが, これはイデアル格子が正しいです. latticeと言ったときには科学としては二つの訳があり, 束と格子です. この場合は格子が正解.

アブスト和訳

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.

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.

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:これの定訳なんだっけ?