Previous slide
Next slide
Toggle fullscreen
Open presenter view
Garbled Circuit
松岡 航太郎
Garbled Circuitとは
GCと略されることが多いがGarbage Collectionではない
主にはAESなどの普通の暗号を使って秘密計算をやる仕組み
準同型暗号と並べて扱われることも多い
名前の通り論理演算を行う
Garbled Circuitの基本的発想
AESなどでは暗号文と鍵とがほぼ同じ形式になっている
AESだとブロック長が128bitで鍵が256bitなので２ブロックと対応
ということは暗号文を秘密鍵として解釈し直すことができる
出力を入力の暗号文を鍵として暗号化してやれば正しい組のときだけ復号できる
Garbled Table
前のスライドのアイデアをNANDを例として具体的に書くと下の図のようになる
実際はこの表(Garbled Table)はどういう論理ゲートかを隠すためにランダムに並び替える
E
n
c
(
p
,
s
k
,
r
)
\rm{Enc}(p,sk,r)
Enc
(
p
,
sk
,
r
)
は
p
p
p
が平文、
s
k
sk
s
k
が秘密鍵、
r
r
r
がある乱数の暗号文
A
1
:
=
E
n
c
(
1
,
s
k
,
a
1
)
A_1:=\rm{Enc}(1,sk,a_1)
A
1
:=
Enc
(
1
,
sk
,
a
1
)
のように定義する
A
1
A_1
A
1
A
0
A_0
A
0
B
1
B_1
B
1
E
n
c
(
E
n
c
(
C
0
,
B
1
,
b
11
)
,
A
1
,
a
11
)
\rm{Enc}(\rm{Enc}(C_0,B_1,b_{11}),A_1,a_{11})
Enc
(
Enc
(
C
0
,
B
1
,
b
11
)
,
A
1
,
a
11
)
E
n
c
(
E
n
c
(
C
1
,
B
1
,
b
10
)
,
A
0
,
a
10
)
\rm{Enc}(\rm{Enc}(C_1,B_1,b_{10}),A_0,a_{10})
Enc
(
Enc
(
C
1
,
B
1
,
b
10
)
,
A
0
,
a
10
)
B
0
B_0
B
0
E
n
c
(
E
n
c
(
C
1
,
B
0
,
b
01
)
,
A
1
,
a
01
)
\rm{Enc}(\rm{Enc}(C_1,B_0,b_{01}),A_1,a_{01})
Enc
(
Enc
(
C
1
,
B
0
,
b
01
)
,
A
1
,
a
01
)
E
n
c
(
E
n
c
(
C
1
,
B
0
,
b
00
)
,
A
0
,
a
00
)
\rm{Enc}(\rm{Enc}(C_1,B_0,b_{00}),A_0,a_{00})
Enc
(
Enc
(
C
1
,
B
0
,
b
00
)
,
A
0
,
a
00
)
Garbled Circuit の高速化
よく使われるのはFreeXORとHalfAND
FreeXOR
はその名の通り暗号文同士をXORするだけでXORゲートの処理をできるようにする
HalfAND
は暗号文の表を2項目だけに減らす
これらは関数を隠さない場合に適用できる
復号が成功したか失敗したかを判定するのは難しいので
暗号文の1bitをランダムなフラグにしてどの暗号文なら成功するかを埋め込む
こともできる
Garbled Circuitの問題点
もしあり得る入力すべてにアクセスできると関数と平文がバレる
それを避けるのに紛失通信が使われる
複数回評価することができない
参考文献
Wikipedia
ARM2GC(MIPSプロセッサを動かす話が含まれてる)
ARM2GC(GCの上でARMプロセッサを動かす)
page_number: true