Garbled Circuit
アンドリュー・チーチー・ヤオが考案し1986年にIEEEの学会で発表したYao's Garbled circuitは、暗号プロトコルを設計する際の強力なフレームワークであり、暗号理論において今も中心的役割を担っている。ただし,このフレームワークを基礎に作った方式は効率が悪いことが知られている。
関数 f : { 0 , 1 } ∗ × { 0 , 1 } ∗ → { 0 , 1 } {\displaystyle f:\{0,1\}^{*}\times \{0,1\}^{*}\rightarrow \{0,1\}} を任意の(確率的多項式時間計算可能)関数とする。
また、二人のユーザAliceとBobがそれぞれ入力 x , y ∈ { 0 , 1 } ∗ {\displaystyle x,y\in \{0,1\}^{*}} をもっており、 f ( x , y ) {\displaystyle f(x,y)} をお互いの入力を漏らすことなく計算したいものとする。
関数として例えば、 > {\displaystyle >} であるならば、どちらの入力値が大きいかを検証できる。
信頼できる第三者Tedがいる場合を考える。この場合は簡単で、AliceとBobがそれぞれの入力をTedに送り、Tedが f ( x , y ) {\displaystyle f(x,y)} を計算して、Bobに送り返せばよい。ここでYaoのGarbled Circuitを利用すると, 第三者の介入なしで、AliceとBobが協力して、お互いの入力値を全く漏らさずに、 f ( x , y ) {\displaystyle f(x,y)} を計算できる。
この方式は、紛失通信プロトコルと擬似ランダム関数があれば実現できる。
表示
編集