閱讀論文（Foundation of Garbled Circuits）
文章目錄
- 一、往期回顧
- 二、代碼游戲
- 三、隱私性、不經意性、認證性之間的關系
- 1.隱私性
- 1.1、不可區分隱私性
- 1.2、模擬隱私性
- 2、不經意性（obliviousness有的博客把這個翻譯為茫然性）
- 2.1、不可區分不經意性
- 2.2、模擬不經意性
- 3.認證性
- 4、邊際資訊函式
- 1、常見的集中邊際資訊函式
- 2、邊際資訊函式 Φ \varPhi Φ的逆，
- 4、相互關系（證明見論文）
- 1、包含關系
- 2、不包含關系
一、往期回顧
混淆電路論文學習筆記——part1
part1已經簡單介紹了混淆方案，電路，邊際資訊函式以及混淆方案的三個安全性質，接下來進一步介紹三個安全性質以及三個安全性之間的關系，
二、代碼游戲
密碼學安全性證明大多都是通過游戲歸約的方式來進行證明的，因此這里先介紹一下代碼游戲
游戲中一般包括三個可選程式，分別是初始化程式，互動程式，最終程式，
一般初始化程式最先執行，進行一系列初始化操作，并且它的輸出（如果有輸出的話）就是敵手
A
\mathcal{A}
A的輸入（這個時候敵手可能正在和其他程式進行互動），敵手可以進行產生問詢，每次產生問詢，互動程式就會啟動，然后對敵手的問詢進行答復，最終敵手給出一個輸出，由最終程式來判斷敵手是否在游戲中獲勝，
三、隱私性、不經意性、認證性之間的關系
我們接下來從編碼游戲的角度來理解這三個性質，下面所有游戲的初始化程式都是初始化一個挑戰位元 b b b，最終程式都是檢驗敵手猜測的位元 b ′ b' b′和初始化的挑戰位元是否一致，接下來我們詳細說明其中的互動程式，
1.隱私性
關于隱私性，我們一共有兩種定義方式，一個是不可區分角度（indistinguish）,一個是模擬器角度（simulation），
1.1、不可區分隱私性
我們首先說不可區分角度的互動程式
- proc p r v i n d ( f 0 , f 1 , x 0 , x 1 ) : prv_{ind}(f_0,f_1,x_0,x_1): prvind?(f0?,f1?,x0?,x1?):
- if Φ ( f 0 ) ≠ Φ ( f 1 ) \varPhi(f_0)\neq\varPhi(f_1) Φ(f0?)?=Φ(f1?) then return false
- if f 0 ( x 0 ) ≠ f 1 ( x 1 ) f_0(x_0) \neq f_1(x_1) f0?(x0?)?=f1?(x1?) then return false
- if x 0 . l e n g t h ( ) ≠ f 0 . n x_0.length() \neq f_0.n x0?.length()?=f0?.n then retuen false
- ( F , e , d ) ← G b ( 1 k , f b ) (F,e,d) \leftarrow Gb(1^k,f_b) (F,e,d)←Gb(1k,fb?)， X ← E n ( e , x b ) X \leftarrow En(e,x_b) X←En(e,xb?)
- retuen ( F , X , d ) (F,X,d) (F,X,d)
代碼解釋： 這個不可區分角度隱私性游戲要求輸入兩對
f
0
,
x
0
,
f
1
,
x
1
f_0,x_0,f_1,x_1
f0?,x0?,f1?,x1?,并且要求
f
0
(
x
0
)
=
f
1
(
x
1
)
f_0(x_0) = f_1(x_1)
f0?(x0?)=f1?(x1?)，第5行中下標b就是初始化程式選擇的挑戰位元，為0或者1，
程式理解： 這個游戲就是判斷敵手是否能夠通過回傳的
(
F
,
X
,
d
)
(F,X,d)
(F,X,d)來判斷該輸出來自于哪一個
f
,
x
f,x
f,x，
1.2、模擬隱私性
在模擬隱私性游戲中，有一個模擬器 ( S ) \mathcal(S) (S),模擬器的功能就是通過安全引數 k k k， f f f泄露的資訊 Φ ( f ) \varPhi(f) Φ(f)，和計算結果 y y y來獲得一個假的 ( F , X , d ) (F,X,d) (F,X,d).
- proc p r v s i m ( f ， x ) : prv_{sim}(f，x): prvsim?(f，x):
- if x . l e n g t h ( ) ≠ f . n x.length() \neq f.n x.length()?=f.n,then return false.
- if b=1 then ( F , e , d ) ← G b ( 1 k , f ) (F,e,d)\leftarrow Gb(1^k,f) (F,e,d)←Gb(1k,f) X ← E n ( e , x ) X\leftarrow En(e,x) X←En(e,x)
- else ( F , X , d ) ← S ( 1 k , X , d ) (F,X,d)\leftarrow S(1^k,X,d) (F,X,d)←S(1k,X,d)
- return (F,X,d).
程式理解： 該程式表示敵手輸入 f , x f,x f,x,然后獲得一個三元組 ( F , X , d ) (F,X,d) (F,X,d)，敵手能不能猜出結果是不是對應輸入的 f , x f,x f,x，
2、不經意性（obliviousness有的博客把這個翻譯為茫然性）
2.1、不可區分不經意性
- proc o b v i n d ( f 0 , f 1 , x 0 , x 1 ) : obv_{ind}(f_0,f_1,x_0,x_1): obvind?(f0?,f1?,x0?,x1?):
- if Φ ( f 0 ) ≠ Φ ( f 1 ) \varPhi(f_0)\neq\varPhi(f_1) Φ(f0?)?=Φ(f1?) then return false
- if f 0 ( x 0 ) ≠ f 1 ( x 1 ) f_0(x_0) \neq f_1(x_1) f0?(x0?)?=f1?(x1?) then return false
- ( F , e , d ) ← G b ( 1 k , f b ) (F,e,d) \leftarrow Gb(1^k,f_b) (F,e,d)←Gb(1k,fb?)， X ← E n ( e , x b ) X \leftarrow En(e,x_b) X←En(e,xb?)
- retuen
(
F
,
X
)
(F,X)
(F,X)
程式理解： 不可區分不經意性和不可區分隱私性類似，不同之處在于輸入的 f 0 ( x 0 ) 與 f 1 ( x 1 ) f_0(x_0)與f_1(x_1) f0?(x0?)與f1?(x1?)并不要求一定相等了，回傳結果少了解碼函式d，
2.2、模擬不經意性
- proc o b v s i m ( f ， x ) : obv_{sim}(f，x): obvsim?(f，x):
- if x . l e n g t h ( ) ≠ f . n x.length() \neq f.n x.length()?=f.n,then return false.
- if b=1 then ( F , e , d ) ← G b ( 1 k , f ) (F,e,d)\leftarrow Gb(1^k,f) (F,e,d)←Gb(1k,f) X ← E n ( e , x ) X\leftarrow En(e,x) X←En(e,x)
- else ( F , X ) ← S ( 1 k , X , d ) (F,X)\leftarrow S(1^k,X,d) (F,X)←S(1k,X,d)
- return (F,X).
程式理解： 模擬不經意性相比于模擬隱私性來說，少回傳了解碼函式d，
3.認證性
- proc aut(f,x):
- if x . l e n g t h ( ) ≠ f . n x.length() \neq f.n x.length()?=f.n,then return false
- ( F , e , d ) ← G b ( 1 k , f ) (F,e,d)\leftarrow Gb(1^k,f) (F,e,d)←Gb(1k,f) X ← E n ( e , x ) X\leftarrow En(e,x) X←En(e,x)
- return (F,X)
認證性的最終程式和上面兩個少許不同，這里我們直接給出， - proc finalize(Y):
- if D e ( d , Y ) = v a l i d De(d,Y) = valid De(d,Y)=valid and Y ≠ E v ( F , X ) Y \neq Ev(F,X) Y?=Ev(F,X)*,then return ture
- *else return false
**代碼理解：**認證性就是判斷敵手在獲得F，X的前提下能不能得到一個新的不同于F（X）的合法的Y，
4、邊際資訊函式
1、常見的集中邊際資訊函式
Φ
c
i
r
c
(
f
)
\varPhi_{circ}(f)
Φcirc?(f)表示泄露電路
f
f
f的全部資訊
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f)表示泄露電路
f
f
f的
(
n
,
m
,
q
)
(n,m,q)
(n,m,q)
Φ
t
o
p
o
(
f
)
\varPhi_{topo}(f)
Φtopo?(f)表示泄露電路
f
f
f的拓撲結構
2、邊際資訊函式 Φ \varPhi Φ的逆，
定義：邊際函式
Φ
(
f
)
\varPhi(f)
Φ(f)的逆函式
Φ
?
i
n
v
e
r
t
e
r
(
)
\varPhi-inverter()
Φ?inverter()的輸入是
?
\phi
?，輸出是
Φ
\varPhi
Φ函式的原項
f
f
f，即
Φ
(
f
)
=
?
\varPhi(f) = \phi
Φ(f)=?，
定義：如果對于特定的求值函式
e
v
ev
ev,我們也可以定義
(
Φ
，
e
v
)
?
i
n
v
e
r
t
e
r
(
)
(\varPhi，ev)-inverter()
(Φ，ev)?inverter().該函式輸入是
(
?
,
y
)
(\phi,y)
(?,y),輸出是
(
f
,
x
)
(f,x)
(f,x)，即滿足
Φ
(
f
)
=
?
\varPhi(f) = \phi
Φ(f)=?,
e
v
(
f
,
x
)
=
y
ev(f,x) = y
ev(f,x)=y，
定理1：對于
Φ
c
i
r
c
(
f
)
\varPhi_{circ}(f)
Φcirc?(f),
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f),
Φ
t
o
p
o
(
f
)
\varPhi_{topo}(f)
Φtopo?(f)都存在多項式時間下的
Φ
?
i
n
v
e
r
t
e
r
(
)
\varPhi-inverter()
Φ?inverter()函式，
定理2:對于,
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f),
Φ
t
o
p
o
(
f
)
\varPhi_{topo}(f)
Φtopo?(f)都存在多項式時間下的
(
Φ
，
e
v
)
?
i
n
v
e
r
t
e
r
(
)
(\varPhi，ev)-inverter()
(Φ，ev)?inverter()函式，
定理理解
對于定理1來說，
Φ
c
i
r
c
\varPhi_{circ}
Φcirc?泄露了電路的所有資訊，因此很容易恢復線路，
Φ
t
o
p
o
(
f
)
\varPhi_{topo}(f)
Φtopo?(f)泄露了電路
f
f
f的拓撲結構，因此我們可以對電路門進行隨意賦值操作，比如，我們把所有的門電路都賦值為與門，得到的電路就是輸出電路，
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f)，我們可以進行隨意的連線操作，比如，我們把所有門電路的輸入線都連接電路輸入線1和2，那么我們就得到了拓撲電路，然后我們由前面可知，我們可以得到原項，
對定理二來說，,
Φ
t
o
p
o
(
f
)
\varPhi_{topo}(f)
Φtopo?(f)泄露了電路
f
f
f的拓撲結構，已知結果
y
y
y,那么我們把所有輸出為電路輸出的門電路設定為常量電路，常量就是
y
i
y_i
yi?，前面的門電路我們隨意設定即可，例如：我們可以設定為與門，對于
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f)，我們前面已經描述了由size資訊怎么構造拓撲電路的方法，則我們就可以找到
Φ
s
i
z
e
(
f
)
\varPhi_{size}(f)
Φsize?(f)的逆，
4、相互關系（證明見論文）
1、包含關系
- 若一個混淆方案具有模仿隱私性，則它一定具有不可區分隱私性，
- 若一個混淆方案具有不可區分隱私性，且要求 e v ( f , x ) ev(f,x) ev(f,x)對于 Φ \varPhi Φ是可逆的（如果不可逆，則不一定），則該混淆方案也具有模仿隱私性，
- 若一個混淆方案具有模仿不經意性，則它一定具有不可區分隱私性，
- 若一個混淆方案具有不可區分不經意性，且要求
e
v
(
f
,
x
)
ev(f,x)
ev(f,x)在
Φ
\varPhi
Φ是可逆的（如果不可逆，則不一定），則該混淆方案也具有模仿隱私性，
關于證明部分相對繁瑣，我們這里就不直接給出，如有感興趣可以私聊我，我可以把論文原文分享一下，
2、不包含關系
1.一個混淆方案具有不可區分隱私性，該方案不一定具有模擬不可區分不經意性，
2.一個混淆方案具有不可區分不經意性，該方案不一定具有模擬不可區分隱私性，
3.一個混淆方案具有模擬隱私性和模擬不經意性，該方案不一定具有認證性，
4.一個混淆方案具有認證性，該方案不一定具有模擬隱私性或者模擬不經意性，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342112.html
標籤：其他
上一篇：bugku game1