Yao's Garbled Circuit
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2009/09/15 18:45 UTC 版)
「Garbled Circuit」の記事における「Yao's Garbled Circuit」の解説
アンドリュー・チーチー・ヤオが考案し1986年にIEEEの学会で発表したYao's Garbled circuitは、暗号プロトコルを設計する際の強力なフレームワークであり、暗号理論において今も中心的役割を担っている。ただし,このフレームワークを基礎に作った方式は効率が悪いことが知られている。 関数を任意の(確率的多項式時間計算可能)関数とする。 また、二人のユーザAliceとBobがそれぞれ入力をもっており、f(x,y)をお互いの入力を漏らすことなく計算したいものとする。関数として例えば、 > であるならば、どちらの入力値が大きいかを検証できる。 信頼できる第三者Tedがいる場合を考える。この場合は簡単で、AliceとBobがそれぞれの入力をTedに送り、Tedがf(x,y)を計算して、Bobに送り返せばよい。ここでYaoのGarbled Circuitを利用すると, 第三者の介入なしで、AliceとBobが協力して、お互いの入力値を全く漏らさずに、f(x,y)を計算できる。 この方式は、紛失通信プロトコルと擬似ランダム関数があれば実現できる。
※この「Yao's Garbled Circuit」の解説は、「Garbled Circuit」の解説の一部です。
「Yao's Garbled Circuit」を含む「Garbled Circuit」の記事については、「Garbled Circuit」の概要を参照ください。
- Yao's Garbled Circuitのページへのリンク