Acompany 技術ブログ/others/Yao's Garbled Circuitとは

Yao's Garbled Circuitとは

Created
2021/10/12 6:47
Tags

はじめに

　この記事では、最古のMulti-Party Computation（以下MPC）プロトコルである、「Yao's Garbled Circuit」の仕組みを紹介していきます。
 
notion image
 

Yao's Garbled Circuit 概要

　Yao's Garbled Circuit は1982年にAndrew Yao 氏が発表した、2者間での初めてのMPCプロトコルです。 2人の参加者が提供する秘密データx, y をお互いに知られることなく、関数f(x, y) の実行結果を得ることができます。関数f(x, y) は次節に説明するGarbled Boolean Circuit によって構成されます。また、その特徴をまとめると以下になります。

特徴

  • ブール回路
  • Semi-Honest Security
  • 2 Party Computation
ブール回路とは、関数の構成に論理ゲートを用いる場合を指しています。また、Semi-Honest Security とは、参加者がプロトコルから逸脱しない場合においてセキュアであることを示しています。最後に、2 Party Computation とは、参加者が2人である場合のMPCであることを示しています。

Garbled Boolean Gate

　関数f(x, y) を構成する論理ゲートは、2つの入力ビットx, y を知られずに、計算結果z を出力することを目指します。このような論理ゲートのことをGarbled Boolean Gate(GBG) と定義します。以後は論理ゲートとして以下のようなANDゲートを想定します。
P1とP2は参加者、x, y はそれぞれの参加者が入力する1ビットの秘密情報、z はAND ゲートの出力ビットを表しています。
notion image

Garbled Computation Table

　上記のGBGを実現するために、Garbled Computation Table(GCT)という表を導入します。Yao's Garbled Circuit では論理ゲートの計算を表によって実現することで、入力値x, y を秘密にしたまま計算結果を出力します。以下にAND ゲートのGCTを示します。
notion image
ここで、Enc()は添字の鍵によって暗号化する関数を示しています。また、k はx, y の値に対応する鍵であり、添字がx, y のそれぞれの入力ビットの値に対応しています。つまり、P1とP2の入力ビットそれぞれに対応した鍵であることを示しています。この時GCTは、AND ゲートの出力結果であるz の値を、それぞれに対応するx, y の鍵k で暗号化したものを表しています。
　ANDゲートの計算結果は、x, y それぞれの対応する鍵を用いてGCTを復号することで得られます。例えば、x = 0, y = 1 に対応する鍵k_x=0, k_y=1 を獲得した場合は、z = 0 を復号することができます。以下にプロトコルの手順を示します。

手順

  1. P1 が全ての鍵k を生成しAND ゲートに対応するGCTを作成する
  1. P1はGCTの行の並びをシャッフルする
  1. P1 はP2 に作成したGCT を送信する
  1. P1 はP2 に自身の入力ビットに対応した鍵k_x を送信する（P2 にはどちらのビットに対応した鍵であるかは分からない）
  1. P1 はP2 にOblivious Transfer を用いてk_y=0, k_y=1 を送信する（Oblivious Transfer は後述する）
  1. P2 はGCT, k_x, k_y を用いて計算結果z を復号する
  1. P2 はP1 に計算結果z を送信する
ここで、Oblivious Transfer は受信者の受け取った値が送信者には分からない通信方法です。また、受信者は受け取った値しか知ることができません。したがって、P1はk_y=0, k_y=1 のどちらをP2 が受け取ったのかを知ることがなく、P2 は受け取った鍵の値しか知ることはできません。また、GCTをシャッフルすることで、どの行がどの入力に対応しているのかをP2は知ることができません(garbled は「シャッフルされた」という意味です)。結果的に、P2 はP1 からk_x, k_y の2つの鍵を入手することができたため、GCTの適切な行を復号しz の値を得ることができました。
　上記のプロトコルにより、P1, P2 の入力ビットx, y の値が相手に知られることなく、AND ゲートの計算結果を得ることができました。さらに、GCTはAND ゲート以外の任意の論理ゲートに適用できるため、任意の関数f(x, y) をブール回路を用いて実現することができます。

まとめ

　Yao’s Garbled Circuit は最古のMPCプロトコルであり、Semi-Honest Security 、2 Party Computation 、ブール回路という特徴を持っています。そして任意の関数f(x, y) をx, y を秘密にしたまま計算可能であり、Garbled Boolean Gate とGarbled Circuit Table を用いて参加者P1 とP2 の間でMPCを実現しています。