これは何ですか
完全準同型暗号化は、コンピュータサイエンスの若くて活気に満ちた分野である暗号化において、長い間最も明るい発見でした。 つまり、このタイプの暗号化により、暗号化されたデータを解読せずに任意の計算を行うことができます。 たとえば、Googleはリクエストが何であるかを知らずにリクエストで検索したり、メールを読んだりせずにスパムをフィルタリングしたり、投票で封筒を開けたりせずに票を数えたり、DNAを読まずにDNAテストを行ったりすることができます。
つまり、計算を実行する人/マシン/サーバーは、暗号を使用して機械的な操作を実行し、独自のアルゴリズム（データベース検索、スパム分析など）を実行しますが、内部で暗号化された情報については何も知りません。 データを暗号化したユーザーのみが計算結果を解読できます。
いいですね そして、これは空想の領域からではありません-これはすでに「理論的に」実装できるものです。
しかし、理論から実践まで、常に手元にあるとは限りません。時には数十年かかることもあります。 現代の準同型暗号化スキームの操作は通常よりもはるかに遅く、ムーアの法則によれば、40年後には今日の計算速度に匹敵するようになります。しかし、毎年、スキームはよりシンプルかつ高速になり、新しいマイルストーンがすぐそこにあるかもしれません。 ITテクノロジー。
創造の歴史
最初のスキームの歴史はかなり珍しいです。スタンフォード大学のダン・ボネ教授は、新しく到着したすべての大学院生が「自動博士号問題」を提供することを規則にしました。 原則として、これは非常に難しい（しかし重大ではない）暗号化タスクであり、科学者たちは少なくとも10年以上闘ってきました。 2006年に、ダンは新入生のCraig GentryにFull Homomorphic Encryptionの設計を提案しました。 2年後、クレイグはそれを決定しました。 ダンは約束を守り、クレイグは博士号をすぐに取得した最初の学生の一人でした。 数学に対する長年の情熱を持って、クレイグは最初の法律の学位を取得し、しばらくの間弁護士として働いていましたが、かなり意識的な年齢で数学に戻り、スタンフォード大学の大学院に入ることを決めました。
シンプルなアイデア
完全準同型暗号化のスキームは、最初は数論の専門家のみが理解していましたが、過去5年間で基本概念が学生に説明できるように単純化されました。
したがって、数字xを暗号化することを想像してください（これはデータのほんの一部であり、小さな自然数かもしれません）。 任意のベクトルvを選択します（これは秘密鍵になります）。 Av〜= xvのような行列Aを見つけることができます。 vによるAの積は、xの約v倍のベクトルを与えます（少し代数を覚えている人にとっては、vは「近似」固有ベクトル、xはAの「近似」固有値です）。 新しい数yを暗号化する場合は、Bv〜= yvであるような行列Bを再度見つけることができます。 したがって、秘密鍵vを1つだけ持つことで、必要な数の数字を暗号化できます。各数字のマトリックスはマトリックスです。 数値を解読するには、行列に秘密ベクトルvを掛けます。
格子内の短いベクトルを見つけるという古風な問題の複雑さを仮定すると証明できますが、これは行列AとBを持ち、それらが暗号化する数値xとyを（もちろん、秘密のベクトルを知らずに）かなりの確率で（ランダムな推測と区別できます） v）。
したがって、これは実際には暗号化スキームですが、準同型です！ つまり、行列AとBを操作、つまり、乗算と加算を行い、暗号化する数値を乗算と加算します。 確かに、AとBの積の復号化によって得られるものを見てみましょう。
（AB）v = A（Bv）〜= A xv = x（Av）〜=（xy）v、xとyの積を与えます！
AとBの合計を復号化すると、
（A + B）v = Av + Bv〜= xv + yv〜=（x + y）v、xとyの合計！
もちろん、ここでは、より正確な分析が必要です。 また、暗号化マトリックスを見つけることは完全に簡単な作業ではありませんが、次のようないくつかの優れた記事に簡単に飛び込むと、これらすべてを把握することができます。
[GSW'13]「エラーを伴う学習からの準同型暗号化：概念的に単純で、漸近的に高速で、属性ベース」（ pdf ）
新しい世界への窓
クレイグは、ある種の新しい世界への扉を開きました。 現在、準同型暗号化には非常に多くのバリエーションがありますが、最も興味深いのは、バリエーションの1つがプログラムを難読化するための可能な限り最高の、理論的に最も安定した方法を提供できることです。これにより、想像力のさらなる可能性が開かれます！ しかし、その別の時間については。 現在のタスクに興味がある場合、Danが自動的にPhDを提供するソリューションについては、コメントを記入してください;）