32

暗号化で興味深いことが起こっているようです: 最初の準同型暗号化スキームが最近登場しました (説明、HT )。大雑把に言えば、 and を簡単に復元できなくても、簡単に知って計算できるようにエンコードする方法です(およびについてもx同様) 。f(x)f(x+y)f(x)f(y)xyf(x*y)

このタイプのスキームの実用的なアプリケーションは何ですか (セキュリティが確立された後)? 私には、プライベート データを操作するためのアルゴリズムの記述がはるかに簡単になるように思えます。

ここに私の考えがあります：

  1. 電子投票
  2. 個人データの完全性をチェックする
  3. 一般的にプライバシーに役立つ可能性はありますか?

例: 私は銀行 A、B、C に口座を持っています。エンティティ X は、私の合計が $1000 を超えていることを確認したいと考えています。銀行 A、B、C、または D からの明細書を喜んで受け入れますが、残念ながら、どの口座にも十分なお金がありません。銀行 A は、私の 500 ドルに関する情報を私の公開鍵で暗号化します。同様に、銀行 B と銀行 C は、私がそれぞれ 200 ドルと 300 ドル持っているという情報を暗号化します。彼らはこれらのデータを X に送信し、X はそれらをいくつかの番号に追加します。これは、実際に暗号化された $1000 であることを示しています (私の公開鍵で $1000 を暗号化し、結果が同じであることを示すことにより)。X私は、各口座にどれだけのお金があるかを明らかにすることなく、何かを証明しました.

別の例: 善良な市民 X_1, ... , X_n がチームを組み、2 人の候補者のうちの 1 人を選択します。1 人はラテを飲むリベルA l で、もう 1 人は聖書を持った銃愛好家です (すべての名前は架空のものです)。彼らは、投票を非公開で迅速に行うことにしました。彼らは投票を(1, vote_A, vote_B, vote_None)暗号化されたベクトル形式で選挙委員会に送信します。選挙委員会はそれらを公に追加し、形式で結果を取得し(count, count_A, count_B, count_None)ます。それを確認した後count = count_A + count_B + count_None、役人は候補者の1人の勝利を宣言し、その後、電子投票とは関係のない何らかの理由で裁判官によって選挙が無効と宣言され、その後10年間法廷で戦いましたが、ねえ、それは私のものではありませんとにかく問題。

注: - これらの特定の例は、以前から RSA で可能だったと思います。これは、1 回の操作で準同型性が必要なだけだからです。より多くの操作を使用して、根本的により興味深いものを実現できることを願っています。そのため、例を考えてみましょう!

  • SOは理論的なコンピューターサイエンスのディスカッションボードではないため、実際に使用される可能性があるコードおよび/または開発中のフレームワークを含む回答を特に見たいと思います。

  • 以下のコメントで述べたことを繰り返すと、準同型アルゴリズムを使用すると、データを知らなくてもデータを管理するプログラムを作成できます。if (x=0) ...残念ながら、プログラムの種類はいくらか限られています。 は暗号化されているため使用できずx、各ステップは非常に低速です (いくつかのラティスが関係しています)。

4

10 に答える 10

10

これは暗闇の中でのワイルドショットです。

計算を行う人から平文を保護することを考えています。しかし、目的が平文とアルゴリズムの両方を保護することだったとしたらどうでしょうか?

たとえば、MRI 装置を考えてみましょう。MRI 装置の最も高価な部分は、装置が磁気共鳴データを分析するアルゴリズムです。このため、プログラムは、信頼できない当事者 (またはその問題については誰でも) によって調べられる前に、プログラムを破壊するように設計されたハードウェア デバイスによって厳重に保護されています。

MRI メーカーが MRI データ コンピューティングを一元化できれば、アルゴリズムが失われるリスクが大幅に減少します。ただし、法律により、個人の患者データにアクセスすることは禁じられています。

そう！準同型暗号化により、患者データとアルゴリズムの両方が保護されている場合にこれが可能になります。「完全な」準同型暗号化 (つまり、暗号化されたデータに環準同型を誘導する) により、はるかに効率的で堅牢な一連の計算を使用してデータを操作できます。

于 2009-07-03T02:15:13.737 に答える
4

準同型暗号化の最大の用途は、データマイニングであるIMHOです。このアルゴを使用すると、プライバシーとトレンド発見の両方の問題を同時に解決できます。たとえば、会社がSASプロバイダーの販売情報をホストしているとします。現在、そのプロバイダーは、実際に実際の情報を公開しなくても、高度なデータマイニングサービスを提供できます。基本的に、あなたはあなたのデータを計算プロバイダーに送り、彼に彼のCPUサイクルを利用してあなたに代わって計算させ、そしてあなたに暗号化されたデータを送り返すことができるでしょう。これは、クラウドベースのシステムへの移行を検討しているが、プライバシーやIPの問題により移行が妨げられている企業にとっては本当に素晴らしいことです。

より低く、より個人的なレベルでの別の潜在的なアプリケーションは、あらゆる種類の財務データの処理です。拡張されたilyaの例は、実際に財務情報やクレジットカードの処理などを確認せずに、会計士による確定申告に適用できます。

ただし、スキームが厳密にテストされ、安全であると見なされるまで、私は興奮を保ちます。暗号化アルゴには、最初のテストに失敗し、改訂を行い、政府当局によって「認定」されるまでこのサイクルを繰り返すという悪名高い習慣があります。

于 2009-07-04T04:48:36.480 に答える
3

Bruce Schneier の準同型暗号化に対するかなり否定的な見方に興味があるかもしれません:

http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html?nc=11

于 2009-07-09T13:06:22.113 に答える
3

PKI オタクとして、準同型暗号関数が非対称鍵システムでもあるとすれば、署名の世界には非常に興味深い可能性がいくつかあります。署名者はメッセージに署名する可能性があり、受信者はメッセージの一部と暗号文の対応する部分を第三者に再送信する可能性があります。

関数表記では、次のようになります。

ユーザーサイン:

署名 (平文、秘密鍵) = 暗号文

そして送信します：

send(平文、暗号文、証明書)

アプリケーションはセグメントを取得します:

平文 = 希望する平文 + その他の平文

次のようなものを使用して、暗号文の同じ変換を計算します。

if ciphertext::plaintext then ??::desiredPlaintext

目的の暗号文を見つける

アプリケーションは、目的のコンテンツのみを外部サービスに転送します。

send(desiredPlaintext、desiredCiphertext、証明書)

また、サービスは、ユーザーが直接送信したかのように、このメッセージを検証できます。

これは、平文の圧縮に使用されるハッシュ アルゴリズムが準同型であることに依存します。そうでない場合、これは機能しません... または、ハッシュアルゴリズムが適用されていません。

これは、署名されたユーザー要求に応じて外部サービスに何かを実行させたいが、ユーザーがその外部サービスに送信したすべてを公開したくない場合に非常に役立ちます。

1 つの例は、単純なパッケージ注文システムです。アイテムのコレクションを購入するリクエストを Web アプリに送信します。非常に安全にするために、特定の場所、特定の日付、特定の支払い情報で出荷されるいくつかのアイテムが欲しい（そして支払うことを約束する）ことを確認する注文書に署名します。さて..ウェブアプリはいくつかのことをしたいと思うでしょう：

  • 財務部門が私のアカウントに請求し、私からの支払いを開始する必要があります
  • 在庫は、在庫から商品を引き出すか、在庫切れの問題に対処する必要があります
  • 配送は在庫から受け取り、商品を私の住所に移動する必要があります

請求書の支払い方法について、Inventory または Shipping が知る必要はありません。そして、財務部門が私の配送先住所を知る理由はないかもしれません... いずれの場合も、受信者が誰であるかに応じて、desiredPlaintext と desiredCiphertext が変わります。これは、Amazon.com の古本のようなシステムでは、私が購入したエンティティ (Amazon) と、アイテムを提供するエンティティ (古本の販売者) が異なる場合に、さらに強力になります。

格子暗号に関する論文を読むと、対称鍵システムのように聞こえます...これは、メッセージの署名にはあまり役立ちません。

「ネバーセイネバー」のコンセプトからすれば、プライバシー用途に使うのも無理はないと思います。しかし、暗号文から平文に変換する方法が複数あることは、明らかに面倒に思えます。

于 2009-06-23T21:12:50.307 に答える
2

これにより、制限された深さの任意の非再帰回路を実行できるため、対数キーの長さが与えられた場合、NC1 アルゴリズム (基本的にフィードフォワードブール回路) を実行できます。

では、これをどのように使用できますか？

一連の入力に対する回路のマップ/リダクションとリダクション スキームを見てみましょう。

最初のデータ:

検索するすべてのデータをクライアントが暗号化する必要はおそらくないので、暗号化された 1 と暗号化された 0 をサーバーに提供し、リング構造を使用して任意の暗号化された整数を構築できるようにします。または、それらをビットとして直接使用することもできます。そうすれば、サーバーは検索対象のデータの一部またはすべてを提供できます。整数の場合、農民算術 (double または double と各ビットに 1 を追加) によってそれらを構築できます。ビットの場合は、適切な暗号化されたビットを提供するだけです。

設計でブール値と整数値を組み合わせて一致させ、1 を true として使用し、0 を false として使用して cond * then + (1 - cond) * else を評価することにより、if/then/else (両方のブランチの SIMD スタイルを評価する必要がある) を取得できます。そのため、リングの組み込み演算を使用して回路をより浅くすることができます。

一方、一部のデータも事前に暗号化されている可能性がありますが、それを使用するには同じキーセットをリサイクルし続ける必要があるため、これを正しく行うのは非常に困難です.

これで、サーバー提供のデータができました。ここで、サーバーに知られたくないもの、たとえば探しているものを暗号化し、マップ関数への追加入力として、適切なポイントで回路にそれをフィードさせます。

各入力に任意の NC1 のような回路をマップして、フィールドを抽出し、いくつかの値を乗算し、一般に安価に削減できる形式にマップできるはずです。

次に、適切にサイズ制限された結果を持つ単純なモノイドなど、より小さな回路を使用してこれらのフラグメントを削減します。(つまり、一致が見つかったかどうかを示すビットを取得するためにマップし、小さな加算器回路でそれらのビットをカウントして削減します)

回路を論理的に構築し、準同型リング内のこれらの暗号化されたビットでその実行をシミュレートするだけでよいため、準同型暗号化部分をまっすぐに取得したと仮定すると、小さな DSL、つまり Haskell の Lava のようなものを使用して比較的迅速に実装できます。

また、各ゲートの実行には非常にコストがかかることに注意してください。

要約すると、

  1. サーバーに暗号化された 1 と 0 と、map および reduce 関数の暗号化されたメタ情報を提供します。
  2. 各データ ポイントについて、それを準同型環にエンコードし、マップ回路に入力とメタ情報の両方を供給して、削減に適した値を取得します。
  3. バランスの取れたバイナリ ツリー (またはツリーの高さを最小限に抑えるための他のバランスの取れた配置) では、リダクション操作を回路からの出力と暗号化されたマップ メタ情報に適用します。
  4. 復号化のために結果をクライアントに渡します
于 2009-07-10T14:40:32.810 に答える
2

計算にどれだけのコストがかかるかはわかりませんf(x) + f(x)が、暗号化されたデータベースを実装する方法として使用できるかもしれません。

f(x_1)、、f(x_2)...として暗号化された一部のデータを 100 万行格納できますf(x_n)。あなたができる

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

SUM(f(x))これは、最初に実行してから復号化することで計算できますSUM(x)。

于 2009-07-04T18:25:27.423 に答える
1

電子投票は確かに準同型暗号化の実用的なアプリケーションです。つまりhttp://heliosvoting.org/

于 2010-09-27T14:36:11.847 に答える
1

SETI@Home のような分散コンピューティング、タンパク質フォールディング プロジェクトなどは、何千ものユーザーからの CPU 時間と電力の寄付を活用しているため、かなり人気があります。さらに興味深いのは、これらのリソースを商用プロジェクトに提供することで人々が報酬を得ることができるモデルです。ただし、何千もの匿名のコンピューターにデータを送信して処理することを希望する責任ある企業はありません。暗号化されたデータに効率的にアルゴリズムを適用できれば、信頼関係のない人に処理を委任することが可能になります。

于 2009-07-04T07:33:01.900 に答える
1

既存の準同型暗号化アルゴリズムの問​​題点は、多対数 (NC1) 回路しか実行できないため、アルゴリズム的に興味深いものはほとんどすべて除外されることです。

さらに、エンコーディングの複雑さは、多対数回路を自分で実行する複雑さよりも決して低いようには見えないので、特にトリッキーなことをしない限り、一見しただけでは無料の作業を見つけたことにはなりません。

于 2009-06-25T19:45:42.053 に答える