Cloud(SaaS)に任せられる仕事とは何か(修正、追記あり)

信頼できない相手に仕事を任せられるのか？について、以下、思いついたことをならべてみた。思いつきが拡散していったら、追記するかもしれない。望み薄だけど。

(2009/6/30追記：Gentry暗号の件で検索で来られた方には、Gentry暗号の簡単な解説 - 186 @ hatenablogをご覧になることをお薦めいたします。
これまで、それで成功した例ってあるのだろうか？

SETI@Home
暗号cracking

冗長化と検算による整合性の検証は成されてきたに違いない。でも、仕事の目的・内容を秘匿してはいなかった。そして、データそのものを秘匿する必要も無かった。
これが、SaaSを利用する上では丸投げになってしまう可能性がある。（相手がcloudである必然性はないが、サービスを運営する側からは、flexibilityやscalability,robustness,設備投資のrisk managementの面から言って、cloud computingを利用する可能性は高い）
事実上、企業内の業務に関して、個人情報や企業秘密の取り扱いが絡まないケースの方が少ないだろうから、企業統治の面からして、普通のアプリケーションのAPIをそのまま利用するというのはペケだろう。しかし、アプリケーションのAPIを自前でいじるなんて、それこそoutsourcingの流れに逆行するものだ。そこで、private cloudという発想が出てくるんだろうと思う。要するに物理的にサービスを社内にリースしてもらう入れ物だ。

案１：そこで、openな仕様を持つ情報秘匿可能なSaaSのAPIを考えてみたい。

この場合、ストレージとCPUの機能を果たすcloudと利用者の間に、サービスを提供するレイヤ（これは企業内に設置するproxy上で稼動するとする）を考える。このレイヤが余りにも重ければ、それがscalabilityの足枷になる可能性はあるけれど、その影響は企業利用者単位に限定されて、cloudサービス全体のscalabilityの制限に直結しない。
例えばこのレイヤの仕事として考えられるのは

ストレージに格納するデータの暗号化、ダミーの作成、saltの挿入
問い合わせ(query)の暗号化
問い合わせの結果の検証（冗長な処理を行って、一致するかどうかの検証。ダミーの問い合わせに対してのエラーの安定度の判定と、ダミーデータに関する処理結果の無視etc.）
- 結果として、信用できるかどうかはゼロ知識証明に準じた手順を踏むことが必要になり、ステップが進むにつれて漸進的に信用度が上がるので、そのランク付けとexpirationを管理する必要がある

一方、暗号化されたデータをcloud内で処理する場合、アルゴリズムも対応が必要である。

暗号化された状態でのパターンマッチを行うか、問い合わせに備えてインデックス化された状態でのみストレージに保管する
秘匿されるべきオブジェクトと数値データなどの直接演算可能なデータの紐付けはcloud上では実施せず、識別のためのtemporalなid（sequence #とか)のみが渡される
ストレージはhashとして扱われ、（もし複数のnodeで処理されるならば）特定のnodeに全体の情報が集中しずらい構造とする
処理がRESTfulであれば、冗長化によって検算が可能になることもあるだろう
処理はnothing to shareであるべき。
transactionはcloudに持ち込まない

(2009/6/26追記)まさにコレだという技術がIBMから発表あり

リリースとその邦訳は意味不明だけど
あとで読む。
IBM's Blindfolded Calculator - Forbesより一部引用（と、適当な訳）、、（2009/6/30追記：以下を読むよりはGentry暗号の簡単な解説 - 186 @ hatenablogをどうぞ。）

Gentry's fully homomorphic revelation came to him as he sat in a New York City cafe that summer.
(2008年IBMにインターンできていたとき)夏、NYのカフェで思いついた。
The encryption method that intrigued him allows a few multiplications or additions of encrypted data.
暗号化されたデータに対する掛け算と足し算ができる暗号化方法をだ。
But it suffers from an interesting handicap.
しかしその手法にはある興味深い欠点がある。
Every arithmetic step unavoidably introduces small amounts of error into the encrypted data.
算術演算をすると、暗号化されたデータの一部がどうしても壊れてしまう。
Performing just a dozen or so computations corrupts the data to the degree that it can no longer be accurately decrypted.
そのため、10回ほど演算を施すと、もう元のデータに戻すことは不可能なくらいに壊れてしまう。
Gentry's insight was to double-encrypt the data in such a way that the errors could be removed, so to speak, in the dark.
Gentryのひらめきは、完全に復号化せずとも誤りの訂正ができるように2重にデータを暗号化するというものだった。
By periodically unlocking the inner layer of encryption underneath an outer layer of scrambling, the cloud computer would clean up its messes as it went along, without ever seeing the secret data.
定期的に内部の暗号化を解除して、データの修復を行いつつも、外部の暗号化は外さないことによって、データの処理を行うcloudのサーバコンピュータは生のデータに触れることなく演算処理を継続できる。
It took Gentry another 15 minutes to realize that he'd just solved an epic cryptographic problem.
全てのアイデアをまとめ、長年の暗号化の大問題を解決できたことに気づくまで、15分しかかからなかった。
Gentry's elegant solution has a catch: It requires immense computational effort.
しかし、Gentryのエレガントな解決方法にも問題点はある。とてつもない計算量が必要なのだ。
In the case of a Google ( GOOG - news - people ) search, for instance, performing the process with encrypted keywords would multiply the necessary computing time by around 1 trillion, Gentry estimates.
たとえば、Googleの検索を例にとると、暗号化されたキーワードによる検索の計算量はおよそ10の18乗倍になってしまう。(※MapReduceのプロセスまで含めての話かどうかまるで不明なので、あまり意味の無い数字。単なるサイクル数であれば、今のGoogleの計算機資源を持ってすれば非現実的な数字ではないかもしれない)
But now that Gentry has broken the theoretical barrier to fully homomorphic encryption, the steps to make it practical won't be far behind, predicts professor Rivest.
しかし、Gentryは理論的障壁を取り払ってしまったのだ、実用化へのステップはそう遠くないとRivest教授は言う。
"There's a lot of engineering work to be done," he says. "But until now we've thought this might not be possible. Now we know it is."
技術的課題は多い。しかし、これまで我々はそれを可能だとすら思っていなかったが、今はそれが可能であることを知っている。

Craig Gentryって何者？
論文：Fully homomorphic encryption using ideal lattices
fully homomorphic encryptionって、、、30年越しの夢*1がかなうのかしら？
以下、上記論文のAbstractをちょっと読んでみた。（全文は、非会員の場合、ACMに$10払わないといけない)

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.
完全にhomomorphicな暗号化手法を提案する。すなわち、暗号化されたデータに関して、復号せずに直接演算回路を適用できる手法である。
手法は３つのステップからなる。
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.
まず、一般的な理論的帰結を示す。
すなわち、任意の演算操作ができる暗号化手法を構築するには、その暗号化手法がそれ自身の（多少機能が付け足された形の）復号化装置(アルゴリズム:プログラム)を評価（eval）実行できることが必要である。
このような暗号化手法のことを「ブートストラップ可能である」と呼ぶことにする。
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.
次に、イデアルの束格子*2(Lattice)を用いた公開鍵暗号化手法がほとんどブートストラップ可能であることを示す。
イデアル格子に基づいた暗号化システムは、復号化のための演算回路が単純(NC1 = O(log n) poly-sized circuits of bounded fan-in AND and OR gates.)であるという特徴がある。
また、イデアル格子は加算と積に関してhomomorphism(同型)である。加算と積があれば、一般的な演算装置が構成できる。
公開鍵のイデアルを法とする多項式環を束(Lattice)とすると、加算と積の２つの演算について双対性が成り立つ。（c.f.１つの演算について双対正が成り立つのが群である）
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.
残念なことに、ここで紹介する初期の手法は実は完全にはブートストラップ可能とはいえない。
というのは、暗号化手法が正しくevalできるのは束の次元でいうとlog(n)までであるが、それは復号化の次元と同じであるが、後者のほうが多少大きい。（ということは、復号化が正しくできないで、失敗することがある）
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.
最後に、初期の手法の欠点を修正すべく、手法のevalの機能を低下させずに復号化装置の複雑さの次元を減らすことで、手法全体をブートストラップ可能とする。
これを実現するために、暗号化装置の内部で復号化のプロセスを開始させておくことで、復号化装置の負担を減らした。
これはサーバ側で暗号化システムを実装する際にクライアント側の復号化の負担を減らすのに似ている。