參考自 Ivan Damgård BRICS (Århus University) 的主題演講,Ivan Damgård是丹麥著名的密碼學家,SPDZ協議的主要開創者。這應該是20年前的一次演講文稿,但可以從中學習一些思想。有興趣的朋友可以讀一下。

作者:六三

日期:2021年4月

摘要:本篇文章帶來的是MPC的入門級介紹。

零、寫在前面

我們的OpenMPC(開放隱私計算)社群已初具規模, 如有想加入我們的小夥伴, 可以私信我或OpenMPC的創始人@開放隱私計算 ,我們拉您進群。

如果心揣夢想, 想更在這個領域進一步做點事情, 那麼請聯絡我們, 我們將會熱烈歡迎您成為我們的一份子。

一、MPC

problem

1。1 前提與目標

前提:

假設有

n

個參與方

P_1,P_2,...,P_n

P_i

持有輸入

x_i

目標:

對於一些有

n

個輸入和

n

個輸出的給定函式

f

,安全地計算

f(x_1,...,x_n)=(y_1,...,y_n)

,也就是說,我們想要一個這樣的協議:

P_i

學習

y_i

的正確值

除了從

x_i

y_i

中得到的資訊外,沒有任何關於輸入的資訊被洩露給

P_i

我們希望以上能夠保持,甚至當(部分)參與方的行為是對抗性的。

1。2

例子

姚院士的百萬富翁問題

兩個百萬富翁

A、B

在街上相遇,他們能否在不透露任何進一步資訊的情況下比較誰更富有。我們對以上問題形式化表示:

計算安全函式

f(x,y)

,接受輸入整數

x,y

,如果

x>y

x

百萬,結果是1,他知道

B

的錢少於

x

百萬,但他不應該進一步瞭解任何資訊。

問題:假設參與方都遵循指令,函式

f(x,y)=x+y

很容易安全計算。你會怎麼做?如果參與方可能偏離協議,你的解決方案還能用嗎?

帶著疑問我們往下看

1。3

通用性

MPC具有足夠通用性: 一個解決方案原則上意味著任何加密協議問題的解決方案。但請注意,並非所有問題都可以透過安全計算單個函式來建模。例如,安全電子支付,它更像是幾個函式的安全計算,跟蹤之間的一些狀態資訊。

然而,這不是一個問題,我們將看到的定義是完全通用的,我們描述的協議實際上也是完全通用的,儘管為了簡單起見,它們被稱為計算單個函式的解決方案。

1。4

建模對抗行為

假設一個敵手

\mathcal {ADV}

\mathcal {ADV}

可能會腐蝕一些參與方並使用它來學習他不應該知道的資訊,或者破壞結果。當

P_i

被腐蝕時,

\mathcal {ADV}

學習

P_i

的完整歷史記錄。

\mathcal {ADV}

按照屬性可分類為:

被動或主動: 只需監控腐壞的參與方,或者對其進行完全控制。

靜態或自適應: 所有腐蝕都發生在協議啟動之前,或者在協議期間動態發生。

無界限或機率多項式時間。

透過對抗行為的描述,我們將得到一個更精確的 MPC 目標:希望協議工作時,就好像我們有一個值得信賴的一方

T

,它從參與方那裡獲取輸入,計算結果並將其返回給參與方一樣,因此,

\mathcal {ADV}

可以決定腐壞參與方的輸入,但誠實的參與方可以獲得正確的結果,協議只告訴

\mathcal {ADV}

被腐蝕參與方的輸入/輸出。

1。5

腐壞的界限

如果

\mathcal {ADV}

可以破壞參與方的任意子集,那麼在大多數情況下問題無法解決,例如,如果每個參與方都被腐蝕,那麼何談安全性呢?

因此需要定義一些可以腐壞子集的界限:

敵手結構

\Gamma

P=\{P_1,…,P_n\}

的子集族,

\mathcal {ADV}

是一個

\Gamma

-adversary,一組腐壞的參與方在所有時間都在

\Gamma

為了使之合理,

\Gamma

必須是單調的。

B\in Γ

A\subseteq  B

意味著

A\in Γ

也就是說,如果

\mathcal {ADV}

可以破壞集合

B

,他可以選擇破壞任何較小的集合。

Threshold-T 結構: 包含最多

T

大小的所有子集。

Γ

Q3

:對於任意

A_1,A_2,A_3\in Γ

A_1\cup A_2\cup A_3

小於

P

Γ

Q2

:對於任意

A_1,A_2\in Γ

A_1\cup A_2

小於

P

t<n/3

的 Threshold-T 結構為

Q3

t<n/2

的 Threshold-T 結構為

Q2

為什麼使用以上通用訪問結構,而不僅僅是可以腐壞的參與方數量?

門限敵手 (我們只是約束了腐壞的數量) 在一個所有節點都同樣難以侵入的網路中是有意義的。但實際情況往往不是這樣。

透過一般的訪問結構,我們可以表達這樣的意思:敵手可以突破少量的比較安全的節點和大量的不太安全的節點。

1。6

建模通訊

非同步網路,即敵手看到所有訊息,可以無限期地延遲它們。在這種網路上,某些形式的 MP C問題更難或不可能,在任何情況下都會產生額外的複雜性。

同步網路,通訊分回合進行,在每輪中,每個參與方都可以向彼此傳送訊息,所有訊息都是在同一輪中接收的。

兩個主要變體:

資訊理論場景。

\mathcal {ADV}

沒有看到誠實(未腐壞)參與方之間的通訊,即可以獲得不受限制的

\mathcal {ADV}

的安全性。

加密場景。

\mathcal {ADV}

可以看到所有傳送的資訊,但不能改變誠實玩家之間的資訊交換,即只能獲得(多項式時間)約束的

\mathcal {ADV}

的安全性。

1。7 小結

腐壞可以是被動的: 只需觀察計算和 mess。

腐壞也可以是主動的:即控制所有。

密碼學場景:

\mathcal {ADV}

能夠看到所有訊息;

資訊理論場景: 沒有關於誠實對誠實的 mess 的資訊。

\mathcal {ADV}

可以選擇靜態或自適應腐壞哪些參與方,但一組腐壞的參與方必須“不太大”,即它必須在給定的敵手結構中。

安全多方計算入門級介紹一

資訊理論場景中:

被動的、自適應的、無約束的

Γ-\rm adversary

:在閾值

(t,n)

的情況下,如果且僅當

Γ

Q2

t< n/2

時,任何函式都能以完美的安全性安全地計算 。“僅當” 的含義是,如果

Γ(t)

上的條件不滿足,則存在無法安全計算的函式。

被動的、自適應的、無約束的

Γ-\rm adversary

:在閾值

(t,n)

的情況下,如果且僅當

Γ

Q3

t< n/3

時,任何函式都能以完美的安全性安全地計算 。

如果我們假設廣播頻道是免費提供的,並且我們接受非零錯誤機率,那麼更多的可能是帶有廣播和主動的、自適應的、無約束的Γ對抗的場景,即在閾值

(t,n)

的情況下,當且僅當

Γ

Q2

t<n/2

時,任何函式都能以較小的錯誤機率安全地計算出來。

參考文獻

[CCD88, BGW88, RB89, HM99,CDDHR00]

密碼學場景中:

被動,自適應,多項式時間敵手:假設存在單向陷門置換,如果腐壞的參與方數量

<n

,則可以透過計算安全性安全地計算任何函式。

主動,自適應,多項式時間:假設存在單向陷門置換,當且僅當

Γ

Q2

t<n/2

時,可以使用計算安全性安全地計算任何函式。

參考文獻

[Y86, GMW87,CFGN]

可以接著往下讀哦:安全多方計算入門級介紹二 - 知乎 (zhihu。com)