參考自 Ivan Damgård BRICS (Århus University) 的主題演講,Ivan Damgård是丹麥著名的密碼學家,SPDZ協議的主要開創者。這應該是20年前的一次演講文稿,但可以從中學習一些思想。有興趣的朋友可以讀一下。
作者:六三
日期:2021年4月
摘要:本篇文章帶來的是MPC的入門級介紹。
零、寫在前面
我們的OpenMPC(開放隱私計算)社群已初具規模, 如有想加入我們的小夥伴, 可以私信我或OpenMPC的創始人@開放隱私計算 ,我們拉您進群。
如果心揣夢想, 想更在這個領域進一步做點事情, 那麼請聯絡我們, 我們將會熱烈歡迎您成為我們的一份子。
一、MPC
problem
1。1 前提與目標
前提:
假設有
個參與方
。
持有輸入
。
目標:
對於一些有
個輸入和
個輸出的給定函式
,安全地計算
,也就是說,我們想要一個這樣的協議:
學習
的正確值
除了從
和
中得到的資訊外,沒有任何關於輸入的資訊被洩露給
。
我們希望以上能夠保持,甚至當(部分)參與方的行為是對抗性的。
1。2
例子
姚院士的百萬富翁問題
兩個百萬富翁
在街上相遇,他們能否在不透露任何進一步資訊的情況下比較誰更富有。我們對以上問題形式化表示:
計算安全函式
,接受輸入整數
,如果
有
百萬,結果是1,他知道
的錢少於
百萬,但他不應該進一步瞭解任何資訊。
問題:假設參與方都遵循指令,函式
很容易安全計算。你會怎麼做?如果參與方可能偏離協議,你的解決方案還能用嗎?
帶著疑問我們往下看
1。3
通用性
MPC具有足夠通用性: 一個解決方案原則上意味著任何加密協議問題的解決方案。但請注意,並非所有問題都可以透過安全計算單個函式來建模。例如,安全電子支付,它更像是幾個函式的安全計算,跟蹤之間的一些狀態資訊。
然而,這不是一個問題,我們將看到的定義是完全通用的,我們描述的協議實際上也是完全通用的,儘管為了簡單起見,它們被稱為計算單個函式的解決方案。
1。4
建模對抗行為
假設一個敵手
。
可能會腐蝕一些參與方並使用它來學習他不應該知道的資訊,或者破壞結果。當
被腐蝕時,
學習
的完整歷史記錄。
按照屬性可分類為:
被動或主動: 只需監控腐壞的參與方,或者對其進行完全控制。
靜態或自適應: 所有腐蝕都發生在協議啟動之前,或者在協議期間動態發生。
無界限或機率多項式時間。
透過對抗行為的描述,我們將得到一個更精確的 MPC 目標:希望協議工作時,就好像我們有一個值得信賴的一方
,它從參與方那裡獲取輸入,計算結果並將其返回給參與方一樣,因此,
可以決定腐壞參與方的輸入,但誠實的參與方可以獲得正確的結果,協議只告訴
被腐蝕參與方的輸入/輸出。
1。5
腐壞的界限
如果
可以破壞參與方的任意子集,那麼在大多數情況下問題無法解決,例如,如果每個參與方都被腐蝕,那麼何談安全性呢?
因此需要定義一些可以腐壞子集的界限:
敵手結構
:
的子集族,
是一個
-adversary,一組腐壞的參與方在所有時間都在
。
為了使之合理,
必須是單調的。
和
意味著
也就是說,如果
可以破壞集合
,他可以選擇破壞任何較小的集合。
Threshold-T 結構: 包含最多
大小的所有子集。
為
:對於任意
,
小於
。
為
:對於任意
,
小於
。
的 Threshold-T 結構為
。
的 Threshold-T 結構為
。
為什麼使用以上通用訪問結構,而不僅僅是可以腐壞的參與方數量?
門限敵手 (我們只是約束了腐壞的數量) 在一個所有節點都同樣難以侵入的網路中是有意義的。但實際情況往往不是這樣。
透過一般的訪問結構,我們可以表達這樣的意思:敵手可以突破少量的比較安全的節點和大量的不太安全的節點。
1。6
建模通訊
非同步網路,即敵手看到所有訊息,可以無限期地延遲它們。在這種網路上,某些形式的 MP C問題更難或不可能,在任何情況下都會產生額外的複雜性。
同步網路,通訊分回合進行,在每輪中,每個參與方都可以向彼此傳送訊息,所有訊息都是在同一輪中接收的。
兩個主要變體:
資訊理論場景。
沒有看到誠實(未腐壞)參與方之間的通訊,即可以獲得不受限制的
的安全性。
加密場景。
可以看到所有傳送的資訊,但不能改變誠實玩家之間的資訊交換,即只能獲得(多項式時間)約束的
的安全性。
1。7 小結
腐壞可以是被動的: 只需觀察計算和 mess。
腐壞也可以是主動的:即控制所有。
密碼學場景:
能夠看到所有訊息;
資訊理論場景: 沒有關於誠實對誠實的 mess 的資訊。
可以選擇靜態或自適應腐壞哪些參與方,但一組腐壞的參與方必須“不太大”,即它必須在給定的敵手結構中。
資訊理論場景中:
被動的、自適應的、無約束的
:在閾值
的情況下,如果且僅當
為
,
時,任何函式都能以完美的安全性安全地計算 。“僅當” 的含義是,如果
上的條件不滿足,則存在無法安全計算的函式。
被動的、自適應的、無約束的
:在閾值
的情況下,如果且僅當
為
,
時,任何函式都能以完美的安全性安全地計算 。
如果我們假設廣播頻道是免費提供的,並且我們接受非零錯誤機率,那麼更多的可能是帶有廣播和主動的、自適應的、無約束的Γ對抗的場景,即在閾值
的情況下,當且僅當
為
,
時,任何函式都能以較小的錯誤機率安全地計算出來。
參考文獻
[CCD88, BGW88, RB89, HM99,CDDHR00]
密碼學場景中:
被動,自適應,多項式時間敵手:假設存在單向陷門置換,如果腐壞的參與方數量
,則可以透過計算安全性安全地計算任何函式。
主動,自適應,多項式時間:假設存在單向陷門置換,當且僅當
為
,
時,可以使用計算安全性安全地計算任何函式。
參考文獻
[Y86, GMW87,CFGN]
可以接著往下讀哦:安全多方計算入門級介紹二 - 知乎 (zhihu。com)