文章
プライバシー比較とは、両当事者の具体的な価値観を明らかにすることなく、両当事者の大小関係を取得することを指します。大富豪問題の最初の起源は姚志志の「二人の億万長者がどちらが裕福であるかを比較したいと考えていますが、自分たちがどれだけのお金を持っているかを明らかにしたくないのです。信頼できる第三者なしでどうやって比較できるでしょうか?」この疑問は、中国で最初で唯一のチューリング賞受賞者である姚其之氏によって 1980 年代に提起され、中国のコンピュータ サイエンスと教育界の第一人者であり、現代の暗号化に新たな扉を開いた人物です。
前回の記事「エレガントな就活～プライバシー比較アルゴリズム例～」では、就活事例を通じてプライバシー比較の適用シナリオと実装方法を紹介しましたが、本記事では主に現時点で比較的効率の高いプライバシー比較プロトコルを紹介します。
このプロトコルは、[1] CrypTFlow2: Practical 2-Party SecureInference で提案されているサブプロトコルであり、このプロトコルに基づいてニューラルネットワークに DRelu 活性化関数が適用されます。
--関連技術--
このプロトコルは主に、ブール型秘密共有とオブリビアス送信という 2 つのテクノロジーを使用して構築されています。
▲誤送信
オブリビアス転送 (OT、Oblivious Transfer) とは、データ送信者が n 個のデータを持ち、データ受信者がそのうちの 1 つのデータを受信し、データ受信者は他のデータを取得できず、データ送信者は受信者が送信したデータの詳細を知らないことを意味します。受け取ることを選択します。どちらですか。実装スキームについては、前回の記事「Secure Multi-Party Computation (MPC) に基づくプライバシーコンピューティング技術 (1)」で紹介したので、本記事では繰り返しません。
▲ ブール型秘密共有
セキュアなマルチパーティ コンピューティングでは、秘密分散を使用してデータを分割して共有し、各パーティが各データの対応するフラグメントを取得し、元のデータの計算ロジックがフラグメントの計算に変換されます。全体の計算ロジックが完成したら、フラグメントの計算結果を集計して復元し、元のデータの計算結果を取得します。
ブール秘密分散とは、ブール値 b を 2 つのフラグメント b0 と b1 に分割し、2 つのフラグメントを結合して元のデータ b を復元することを指します。
フラグメント生成: ブール値 b0 をランダムに生成し、b と XOR を実行して b1=b0⊕b を計算します。
b=b0⊕b1
シャードの復元: 2 つのシャードに対して XOR 操作を実行します。
a=a0⊕a1，b=b0⊕b1
a⊕b=(a0⊕b0)⊕(a1⊕b1)
XOR 演算: ブール型秘密共有は XOR 演算の準同型特性を満たし、フラグメントに対して XOR 演算をローカルで実行して復元することは、元のデータに対する XOR 演算と同等です。
AND 演算: ブール型秘密共有は AND 演算の準同型特性を満たさず、安全な AND 演算を実現するために無自覚転送テクノロジを使用します。
アリスはフラグメント a0 と b0 を保持し、ボブはフラグメント a1 と b1 を保持します。AND 演算により、アリスは c0 を取得し、ボブは c1 を取得します。c0⊕c1=(a0⊕a1)∧(b0⊕b1)、両方のフラグメントのセキュリティは次のようになります。保証付き。
*アリスは、忘却送信の送信者として、ブール値 r を c0 としてランダムに生成し、以下に示すように忘却送信の入力を生成します。
*ボブは、不用意な送信の受信者として、データ r⊕((a0⊕a1)∧(b0⊕b1)) を c1 として取得するため、不用意な送信のオプションとして、自分のフラグメント a1 と b1 を a1||b1 に接続します。
c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1); であることが確認できます。
要はAND演算の可能性をすべて列挙し、ランダムな項目を追加した上で、相手は自分のデータに従って混乱した計算結果を選択するというものです。
--実装アイデア--
▲平文比較
まず、比較演算のプライバシーに関係なく、通常の状況では 2 つの数値はどのように比較されますか。
a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]
*2 つの数値を同じ長さのデジタル配列に整列させます。長さが十分でない場合は、先頭に 0 を追加します。
*2 つの配列の数値を順番に比較します。対応する桁の数値が等しい場合は、1 つの桁が不等になるまで次の桁の比較を続けます。最も古い等しくない桁の比較結果が 2 つのデータの比較結果になります。すべての桁が等しい場合、2 つの数値は等しいことになります。プロセス全体は次の式に要約できます。
X と Y は両方とも長さ n、1{X のデータです
X=x0||x1||x2||...||x(n-1)、Y=y0||y1||y2||...||y(n-1)、xi、yi を意味します分割後のi番目のデータ
1{X 1{X1 ... 1{X(n-1) Xi=xi||...||x(n-1)、Yi=yi||...||y(n-1)、最初の i-1 ビットを削除した後のデータを表すために使用されます。 ▲ 安全でないプライバシーの比較 上記の比較スキームをプライベート比較に変換したい場合、最も簡単に考えられるのは、以前の記事「エレガントな就活 – プライバシー比較アルゴリズム」で紹介した、最小の 2 つの比較単位の比較をプライベートにすることです。例: 2 つの最小比較単位の比較は、oblivious 転送プロトコルを通じて実行できます。これにより、単一の最小比較単位のセキュリティが確実に保証されますが、場合によっては、データが公開される可能性があります。 a=1230 b=1231、これら 2 つの数値の比較について、b が ot の受信者、つまり最小比較単位のデータ比較結果の取得者であり、比較が上記のスキームに従って実行される場合、さらに 2 つの情報が漏洩します。 1) 最初の数桁が同じ場合: b は、a の最初の 3 桁が 123 であることがわかります。 2) 2 つの最小単位のデータは、最小単位範囲の両端のデータです。b は、a の最後の桁が 0 であることを知っています。 文章 この論文のプライバシー比較プロトコルでは、全体の比較の考え方は上記の安全でないプライバシーの比較と一致していますが、このプロトコルは秘密分散技術を導入しており、不注意な転送を通じて比較結果が得られた場合、送信者は各データの前のものを混同します。ランダムな項目であり、どちらの当事者も最小比較単位データの比較結果を取得せず、比較結果の断片を取得し、その断片を使用して平文比較プロセスに従って再帰的に比較します。比較、比較結果のフラグメントを復元して、データ全体の比較結果を取得します。 --契約手続き-- アリスはデータx、ボブはデータy、データのバイナリ長はl、最小比較単位のバイナリ長はm、最小比較単位の分割数はq=l/m、10進数の最大値最小比較単位は M= 2^m-1 1) 両者はデータを別々に分割します: x=x0||...||x(q-1)、y=y0||...||y(q-1) 2) すべての最小比較単位 xi(0<=i sij= tij= _0、xi が yi 以下かどうかのブール共有フラグメントとして、0<=j<=M の場合、2 つの誤った転送インスタンスの入力はそれぞれ次のように設定されます。 1と _0 を作成し、次のように 2 つの無自覚入力を生成します。 ボブは両方の忘却転送のオプションとして y0 を使用し、次のものを取得します。 3) すべての最小比較単位の比較が完了した後、両当事者は、対応する最小比較単位が互いに以下であるかどうかのブール共有フラグメントを取得し、平文比較プロセスに従い、フラグメント再帰を使用できます。最終的な比較結果のフラグメントを計算します。 フラグメントの XOR 演算の場合、ローカルでフラグメントの XOR を実行するだけで済みます。フラグメントの AND 演算の場合、上で紹介したスキームに従って、計算結果のフラグメントを誤って転送する必要があります。 再帰プロセスでは、主に 2 つの場所で AND 演算を実行する必要があります。 1{x0||x1 = y0||y1 } ∧ 1{x2 < y2 } 前の比較単位がすべて等しく、次の比較単位を比較する必要がある場合: 1{x0||x1 = y0||y1} = 1{x0 = y0 } ∧ 1{x1 = y1 } --要約-- 単一要素の比較の場合、再帰的な計算が必要であり、前後に依存関係があるため、操作の OT インスタンスを OT 拡張によって最適化することはできません。バッチ要素の比較では、同じ位置と操作を持つ OT インスタンスを垂直方向に OT 拡張することで効率を最適化できます。 著者について 著者について 文章 参考文献 参考文献▲ 不安を解消
最小単位の比較結果はすべてフラグメントであるため、比較が完了するまで再帰計算結果は復元されず、最小比較単位の比較結果取得による情報漏洩を回避できる。
先行するすべての比較単位が等しいかどうかを計算する場合:
IOS
Android