引言
如今日戈,隱私計(jì)算技術(shù)不僅在政府政策的推動(dòng)下發(fā)展迅猛,也在企業(yè)級(jí)應(yīng)用方面迎來了前所未有的機(jī)遇孙乖。一些領(lǐng)先的科技公司浙炼,如微軟、IBM唯袄、谷歌等弯屈,紛紛加入隱私計(jì)算的領(lǐng)域,并且將其應(yīng)用到各自的產(chǎn)品和服務(wù)中恋拷。例如季俩,微軟公司推出了基于隱私計(jì)算技術(shù)的Azure Confidential Computing,IBM公司則推出了IBM Z和IBM LinuxONE等可信執(zhí)行環(huán)境梅掠,而谷歌則通過聯(lián)邦學(xué)習(xí)技術(shù)實(shí)現(xiàn)了不同設(shè)備之間的數(shù)據(jù)共享和訓(xùn)練酌住。
此外,隱私計(jì)算技術(shù)還被廣泛應(yīng)用于金融阎抒、醫(yī)療酪我、物聯(lián)網(wǎng)等領(lǐng)域。在金融領(lǐng)域且叁,隱私計(jì)算技術(shù)能夠幫助保護(hù)用戶的個(gè)人隱私和交易數(shù)據(jù)都哭,提高數(shù)據(jù)共享的安全性和可信度。在醫(yī)療領(lǐng)域,隱私計(jì)算技術(shù)能夠解決醫(yī)療數(shù)據(jù)隱私保護(hù)的難題欺矫,同時(shí)還能夠促進(jìn)不同醫(yī)療機(jī)構(gòu)之間的數(shù)據(jù)共享和合作纱新。在物聯(lián)網(wǎng)領(lǐng)域,隱私計(jì)算技術(shù)能夠幫助保護(hù)用戶設(shè)備的隱私和安全穆趴,同時(shí)還能夠?qū)崿F(xiàn)設(shè)備之間的安全數(shù)據(jù)共享和聯(lián)合決策脸爱。
綜上所述,隱私計(jì)算技術(shù)在政策未妹、企業(yè)和應(yīng)用等方面均迎來了快速發(fā)展的機(jī)遇簿废,其應(yīng)用前景廣闊,未來將會(huì)在更多的領(lǐng)域得到廣泛的應(yīng)用和推廣络它。
多方安全計(jì)算(Security Multi-party Computation, MPC)是隱私計(jì)算在密碼學(xué)領(lǐng)域的最主流技術(shù)族檬,其核心思想是設(shè)計(jì)特殊的加密算法和協(xié)議,基于密碼學(xué)原理實(shí)現(xiàn)在無可信第三方的情況下化戳,在多個(gè)參與方輸入的加密數(shù)據(jù)之上直接進(jìn)行計(jì)算单料。
秘密共享(Secret Sharing,SS)是1979年由Shamir和Blakey提出的点楼,并在此之后40多年秘密共享被廣泛認(rèn)識(shí)和深入研究看尼。?秘密分享是隱私加密計(jì)算中常用的密碼學(xué)工具。本章將詳細(xì)介紹與秘密共享相關(guān)的問題模型及定義盟步、剖析秘密共享的主流方案及技術(shù)原理,并結(jié)合代碼給出示例躏结。
問題模型
秘密共享經(jīng)典的(t, n)閾值方案如圖所示却盘,秘密分享的問題可描述為將一個(gè)秘密S拆分成n份S1,S2...,St, ...Sn, 分發(fā)給不同的參與方P1, P2,...Pn管理。只有至少t個(gè)參與方合作才能恢復(fù)秘密媳拴。問題限定:? 1. 單方無法自己恢復(fù)秘密黄橘;2. 不需要所有參與方合作就能恢復(fù)(1 < t < n);3. t個(gè)參與方為隨機(jī)挑選屈溉,且隨機(jī)選出t個(gè)參與方必須能夠恢復(fù)秘密
概念
秘密共享(Secret Sharing)是一種密碼學(xué)技術(shù)塞关,它通過將一個(gè)秘密數(shù)據(jù)分割成多個(gè)部分,分配給不同的參與者子巾,以確保數(shù)據(jù)的安全性帆赢。只有當(dāng)多個(gè)部分同時(shí)合并時(shí),才能恢復(fù)原始的秘密數(shù)據(jù)线梗。因此椰于,在秘密共享方案中,任何單個(gè)參與者無法看到完整的秘密數(shù)據(jù)仪搔。
原理與實(shí)現(xiàn)
秘密共享最早由著名的密碼學(xué)家Shamir和Blakley在1979年提出瘾婿,兩個(gè)人給出了各自的實(shí)現(xiàn)方案。之后又陸續(xù)出現(xiàn)了很多秘密共享的方案。其中較為經(jīng)典的方案包括:Shamir秘密共享方案偏陪、Brickell秘密共享方案抢呆、Blakley秘密共享方案及基于"中國剩余定理"的秘密共享方案
Shamir秘密共享方案
Shamir's Secret Sharing 是一種秘密共享方案,用于將一個(gè)秘密信息(例如一個(gè)密碼)分割成多個(gè)部分笛谦,分配給多個(gè)參與方抱虐,只有當(dāng)一定數(shù)量的參與方合作才能夠重構(gòu)出原始秘密信息。這種方法可以增強(qiáng)數(shù)據(jù)安全性揪罕,保護(hù)個(gè)人隱私梯码。
具體來說,假設(shè) Alice 有一個(gè)秘密信息 S好啰,她希望將其分割成 n 份轩娶,分配給 n 個(gè)參與方,但要求只有當(dāng) k(k ≤ n)個(gè)參與方合作時(shí)才能夠重構(gòu)出原始秘密信息框往。Shamir's Secret Sharing 就可以實(shí)現(xiàn)這樣的要求鳄抒。
具體過程如下:
選擇一個(gè)質(zhì)數(shù) p,使得 p > S椰弊,然后選擇一個(gè) k-1 次的隨機(jī)多項(xiàng)式 f(x)许溅,滿足 f(0) = S。這里的 k-1 次多項(xiàng)式表示的是 k-1 個(gè)隨機(jī)系數(shù)確定的多項(xiàng)式秉版,其中 f(0) = S 表示該多項(xiàng)式在 x = 0 時(shí)的取值等于 S贤重。
選擇 n 個(gè)不同的參與方,為每個(gè)參與方分配一個(gè)獨(dú)立的 x 坐標(biāo)值(稱之為 xi)清焕,其中 0 ≤ xi < p并蝗。這些參與方可以是 Alice 選擇的特定人員,也可以是隨機(jī)選擇的秸妥。
對(duì)于每個(gè)參與方 i滚停,計(jì)算出對(duì)應(yīng)的 y 坐標(biāo)值(稱之為 yi),其中 yi = f(xi) mod p粥惧。這里的 mod p 表示對(duì) p 取模键畴,保證 yi 的范圍在 0 到 p-1 之間。
將所有的 (xi, yi) 對(duì)分配給對(duì)應(yīng)的參與方突雪,每個(gè)參與方只能獲得自己對(duì)應(yīng)的 (xi, yi) 對(duì)起惕。這樣,所有的參與方都知道了自己的 (xi, yi) 值咏删,但并不知道其他參與方的值疤祭。
當(dāng)需要恢復(fù)原始秘密信息時(shí),只需要任意 k 個(gè)參與方合作饵婆,使用拉格朗日插值法計(jì)算出 f(0) = S 即可勺馆。
需要注意的是戏售,Shamir's Secret Sharing 通過選取隨機(jī)多項(xiàng)式和隨機(jī) x 坐標(biāo)值,保證了秘密信息的安全性草穆。只有同時(shí)掌握 k 個(gè)參與方的信息才能夠恢復(fù)出原始秘密信息灌灾,這大大增加了秘密信息的保護(hù)程度。
Shamir's Secret Sharing 的安全性基于離散對(duì)數(shù)問題悲柱,即沒有足夠的信息可以用來推導(dǎo)出多項(xiàng)式的系數(shù)和秘密數(shù)據(jù)锋喜。只有當(dāng)至少 k 個(gè)參與者合作時(shí),才能重構(gòu)出原始的秘密數(shù)據(jù)豌鸡。因此嘿般,它可以用于各種需要秘密共享的場(chǎng)景,例如安全多方計(jì)算涯冠、密鑰管理炉奴、數(shù)字簽名等。
如下是基于Syft框架的代碼實(shí)現(xiàn):
1. 首先需要安裝 PySyft:
pip install syft
2. 代碼:
import syft as sy
from syft.frameworks.torch.he.fv.util.operations import random_uint
# 創(chuàng)建本地虛擬工作節(jié)點(diǎn)
hook = sy.TorchHook()local_worker = hook.local_worker
# 設(shè)置參數(shù)
n = 5
# 總共的秘密數(shù)據(jù)份額
k = 3
# 恢復(fù)秘密數(shù)據(jù)需要的最少份額
p = 2**127-1
?# 模數(shù)# 生成秘密數(shù)據(jù)
secret = random_uint(64).item()
print("秘密數(shù)據(jù):", secret)
# 生成多項(xiàng)式并求出數(shù)據(jù)點(diǎn)
coeffs = [secret] + [random_uint(64).item() for i in range(k-1)]points = [(i+1, sum([coeffs[j]*i**j for j in range(k)]) % p) for i in range(n)]
print("數(shù)據(jù)點(diǎn):", points)
# 將數(shù)據(jù)點(diǎn)分配給不同的工作節(jié)點(diǎn)
workers = [sy.VirtualWorker(hook, id=f"worker_{i}") for i in range(n)]
shares = [sy.crypto.encode_shares(point, workers) for point in points]
# 任意 k 個(gè)份額就可以恢復(fù)出原始數(shù)據(jù)
selected_shares = shares[:k]
recovered_secret = sy.crypto.decode_secret(selected_shares, workers[:k])
print("恢復(fù)的秘密數(shù)據(jù):", recovered_secret)
這個(gè)代碼演示了如何使用 PySyft 框架實(shí)現(xiàn) Shamir's Secret Sharing蛇更。在這個(gè)示例中瞻赶,我們使用了 HE 庫中的 random_uint 函數(shù)生成隨機(jī)數(shù),并使用 encode_shares 和 decode_secret 函數(shù)分別對(duì)秘密數(shù)據(jù)進(jìn)行分配和恢復(fù)派任。請(qǐng)注意砸逊,我們將秘密數(shù)據(jù)和多項(xiàng)式系數(shù)都設(shè)置為 64 位的隨機(jī)數(shù),但在實(shí)際應(yīng)用中掌逛,我們可能需要更大的秘密數(shù)據(jù)和更高次數(shù)的多項(xiàng)式來確保安全性师逸。
Brickell秘密共享方案
Brickell秘密共享方案是一種基于多項(xiàng)式插值的秘密共享方案,類似于Shamir的秘密共享方案豆混,但采用了不同的多項(xiàng)式插值方法篓像,其主要優(yōu)點(diǎn)是可以支持更高的參與方數(shù)目,并具有更高的效率和更強(qiáng)的安全性崖叫。
具體來說,Brickell秘密共享方案的實(shí)現(xiàn)步驟如下:
選擇一個(gè)大質(zhì)數(shù)p拍柒,并選擇一個(gè)正整數(shù)n心傀,表示參與方的數(shù)量。
選擇一個(gè)k次多項(xiàng)式f(x)拆讯,滿足f(0) = s脂男,其中s為要秘密共享的值。
選擇n個(gè)互不相同的隨機(jī)數(shù)a1, a2, ..., an种呐,并計(jì)算f(ai)對(duì)p取模后的值yi宰翅。
將秘密值s和所有的yi發(fā)送給參與方。
任意k個(gè)參與方可以使用拉格朗日插值法來重構(gòu)多項(xiàng)式f(x)爽室,并計(jì)算出f(0)的值汁讼,即秘密值s。
Brickell秘密共享方案與Shamir秘密共享方案相比,主要的不同在于選擇多項(xiàng)式時(shí)的插值方法不同嘿架。Shamir方案采用拉格朗日插值法瓶珊,而Brickell方案則采用了差分插值法。差分插值法的優(yōu)勢(shì)在于支持更高次數(shù)的多項(xiàng)式耸彪,并且具有更高的效率和更強(qiáng)的安全性伞芹。
Brickell秘密共享方案已經(jīng)在很多應(yīng)用場(chǎng)景中得到了應(yīng)用,例如分布式數(shù)據(jù)庫和云計(jì)算等領(lǐng)域蝉娜。同時(shí)唱较,Brickell方案也常常與其他隱私計(jì)算技術(shù)結(jié)合使用,如同態(tài)加密召川、安全多方計(jì)算等南缓,以進(jìn)一步提高數(shù)據(jù)隱私和安全性。
如下是基于Python的Brickell秘密共享方案的代碼實(shí)現(xiàn):
import syft as sy
from syft.frameworks.torch.crypto
import utils as cryptoutils
from syft.frameworks.torch.crypto
import brickell as brickell
?# 創(chuàng)建兩個(gè)本地工作節(jié)點(diǎn)
bob = sy.VirtualWorker(hook, id="bob")
alice = sy.VirtualWorker(hook, id="alice")
?# 定義秘密值
secret = cryptoutils.random_mpz(1024)
# 生成共享密鑰
key = brickell.generate_shares(secret, n=2, k=2, field_order=brickell.PRIME)
# 將共享密鑰發(fā)送給兩個(gè)本地工作節(jié)點(diǎn)
bob_key = key[0].send(bob)
alice_key = key[1].send(alice)
?# 從本地工作節(jié)點(diǎn)接收共享密鑰
bob_key = bob_key.get()
alice_key = alice_key.get()
# 將共享密鑰合并
merged_key = brickell.merge_shares([bob_key, alice_key])
# 使用共享密鑰進(jìn)行加密和解密
encrypted = cryptoutils.encrypt(secret, merged_key)
decrypted = cryptoutils.decrypt(encrypted, merged_key)
# 打印加密和解密結(jié)果
print("Secret: ", secret)
print("Encrypted: ", encrypted)
print("Decrypted: ", decrypted)
Blakley秘密共享方案
Blakley秘密共享方案是一種比較早期的秘密共享方案扮宠,它最初是由Blakley在1979年提出的西乖。與Shamir's Secret Sharing方案類似,Blakley秘密共享方案也是基于多項(xiàng)式插值原理實(shí)現(xiàn)的坛增。
假設(shè)有一份秘密S需要共享給n個(gè)人获雕,Blakley秘密共享方案的實(shí)現(xiàn)步驟如下:
隨機(jī)選擇n個(gè)線性無關(guān)的向量作為公共密鑰。這n個(gè)向量可以組成一個(gè)矩陣P收捣,即 P=[p1, p2, ..., pn]届案,其中每個(gè)向量pi的維度均為m。
將秘密S表示為向量形式罢艾,并與矩陣P相乘楣颠,即:
V = S × P
其中V為一個(gè)長度為m的向量。
將V拆分成n個(gè)部分咐蚯,并分別分配給n個(gè)人童漩,每個(gè)人獲得一個(gè)長度為m的向量vi。
要恢復(fù)秘密S春锋,需要至少有n個(gè)人合作矫膨,每個(gè)人將自己擁有的向量vi與公共密鑰矩陣P進(jìn)行線性組合,得到一個(gè)長度為m的向量W期奔,即:
W = a1 × p1 + a2 × p2 + ... + an × pn
其中a1, a2, ..., an為任意實(shí)數(shù)侧馅。因?yàn)閚個(gè)向量p1, p2, ..., pn線性無關(guān),所以可以通過求解線性方程組來得到向量W呐萌。然后將W與公共密鑰矩陣P的逆矩陣相乘馁痴,即可得到原始的秘密向量S。
與Shamir's Secret Sharing方案相比肺孤,Blakley秘密共享方案的優(yōu)點(diǎn)在于實(shí)現(xiàn)較為簡單罗晕,且不需要進(jìn)行多項(xiàng)式插值運(yùn)算琳彩。但是汛兜,它的缺點(diǎn)也比較明顯,即需要在選擇公共密鑰矩陣P時(shí)保證n個(gè)向量的線性無關(guān)性,這在實(shí)踐中可能比較困難酣藻。此外斋扰,Blakley秘密共享方案也不支持任意的門限t鞋怀,只能保證需要n個(gè)人合作才能恢復(fù)秘密屋休。
以下是使用SecretSharing庫實(shí)現(xiàn)Blakley方案的示例代碼:
from secretsharing import BlakleySecretSharing
# 分享一個(gè)長度為10的秘密,需要至少3個(gè)分享才能恢復(fù)秘密
sss = BlakleySecretSharing(minimum=3, shares=10)
# 生成秘密并分發(fā)給10個(gè)參與者
secret = sss.generate_secret()
shares = sss.split_secret(secret)
# 選擇任意3個(gè)參與者梆惯,使用他們的分享恢復(fù)秘密
recovered_secret = sss.recover_secret(shares[:3])
assert secret == recovered_secret
在這個(gè)例子中酱鸭,我們使用BlakleySecretSharing類創(chuàng)建了一個(gè)秘密共享實(shí)例,設(shè)置了至少需要3個(gè)分享才能恢復(fù)秘密垛吗,并且生成了10個(gè)分享凹髓。然后我們隨機(jī)生成了一個(gè)秘密并將其分發(fā)給10個(gè)參與者,最后使用其中的3個(gè)分享成功恢復(fù)了秘密怯屉。
優(yōu)缺點(diǎn)
相對(duì)于其他隱私計(jì)算技術(shù)蔚舀,秘密共享的優(yōu)點(diǎn)是:
? ? ? ? 1. 安全性較高:秘密共享方案能夠保證秘密數(shù)據(jù)的安全,只有多個(gè)參與方一起才能夠獲取原始秘密數(shù)據(jù)锨络,保證了隱私的安全性赌躺。
? ? ? ? 2. 靈活性較高:秘密共享方案可以適用于多種計(jì)算場(chǎng)景,不需要像差分隱私技術(shù)那樣需要針對(duì)不同的查詢場(chǎng)景進(jìn)行設(shè)計(jì)和調(diào)整羡儿。
秘密共享的缺點(diǎn)是:
? ? ? ? 1. 計(jì)算代價(jià)較高:秘密共享需要在多個(gè)參與方之間進(jìn)行數(shù)據(jù)通信和計(jì)算礼患,因此需要消耗更多的計(jì)算資源和帶寬資源。
? ? ? ? 2. 實(shí)現(xiàn)復(fù)雜性較高:秘密共享方案需要對(duì)多項(xiàng)式運(yùn)算掠归、加密算法等進(jìn)行深入的理解和掌握缅叠,實(shí)現(xiàn)難度較高。
????????因此虏冻,在實(shí)際應(yīng)用中肤粱,需要權(quán)衡秘密共享方案的優(yōu)缺點(diǎn),并根據(jù)實(shí)際需求選擇最合適的隱私計(jì)算技術(shù)厨相。
Shamir's Secret Sharing, Brickell's Secret Sharing, 和 Blakley's Secret Sharing都是秘密共享方案领曼,用于將一個(gè)秘密分割成多份,然后分配給多個(gè)參與者领铐,使得只有在滿足一定條件下悯森,參與者才能重建出原來的秘密宋舷。這三個(gè)方案各有優(yōu)缺點(diǎn)绪撵,下面做一個(gè)簡單的對(duì)比:
Shamir's Secret Sharing:
優(yōu)點(diǎn):
? ? 1. 在加密和解密過程中,計(jì)算開銷小祝蝠,效率高音诈。
? ? 2. 可以適用于不同的分布式系統(tǒng)場(chǎng)景幻碱。
缺點(diǎn):
? ? 1. 需要事先知道參與者的個(gè)數(shù)和重建秘密所需的最小閾值。
? ? 2. 不支持動(dòng)態(tài)增減參與者细溅。
Brickell's Secret Sharing:
優(yōu)點(diǎn):
? ? 1. 在數(shù)據(jù)安全方面具有較好的保護(hù)性能褥傍。
? ? 2. 可以在不泄露重建秘密的情況下,檢查參與者的行為是否一致喇聊。
? ? 3. 支持動(dòng)態(tài)增減參與者恍风,即使不知道最終參與者的個(gè)數(shù)。
缺點(diǎn):
? ? 1. 在加密和解密過程中誓篱,計(jì)算開銷相對(duì)較大朋贬,效率較低。
Blakley方案的優(yōu)點(diǎn)和缺點(diǎn)如下:
優(yōu)點(diǎn):
????1. Blakley方案只需要一個(gè)密鑰窜骄,不需要進(jìn)行多次計(jì)算锦募,因此在密鑰管理方面比較簡單。
? ? 2. Blakley方案在計(jì)算上相對(duì)簡單邻遏,只需要進(jìn)行一次矩陣乘法運(yùn)算即可糠亩。
? ? 3. Blakley方案的安全性較高,由于它使用了線性代數(shù)的方法准验,因此在一定程度上可以抵御已知明文攻擊赎线。
缺點(diǎn):
? ? 1. Blakley方案的存儲(chǔ)需求較高,需要存儲(chǔ)一個(gè)矩陣和一個(gè)向量沟娱,這會(huì)占用較多的存儲(chǔ)空間氛驮。
? ? 2. Blakley方案的加密效率較低,需要進(jìn)行一次矩陣乘法運(yùn)算济似,因此計(jì)算效率較低矫废。
? ? 3. Blakley方案在參與方的數(shù)量較多時(shí),需要進(jìn)行多次矩陣乘法運(yùn)算砰蠢,因此運(yùn)算時(shí)間會(huì)變得更長蓖扑,效率更低。
綜上所述台舱,Blakley方案在一些特定場(chǎng)景下可能會(huì)更適合使用律杠,例如只有少數(shù)幾個(gè)參與方的情況下,但在大多數(shù)情況下竞惋,Shamir's和Brickell方案更為流行和實(shí)用柜去。
應(yīng)用場(chǎng)景
秘密共享(secret sharing)是一個(gè)非常有用的密碼學(xué)技術(shù),它已經(jīng)被廣泛應(yīng)用于許多領(lǐng)域拆宛。以下是一些成功的秘密共享應(yīng)用案例:
? ? 1. 多方安全計(jì)算(multi-party secure computation):秘密共享允許多個(gè)參與者將他們的私人數(shù)據(jù)共享嗓奢,并以一種安全的方式進(jìn)行計(jì)算,從而保護(hù)他們的隱私浑厚。例如股耽,在醫(yī)療保健領(lǐng)域根盒,醫(yī)院可以使用秘密共享計(jì)算技術(shù)來分析病人的數(shù)據(jù),同時(shí)保護(hù)他們的隱私物蝙。
? ? 2. 數(shù)字簽名(digital signature):秘密共享可以用于數(shù)字簽名炎滞,以確保簽名是由多個(gè)參與者共同生成的。例如诬乞,在法律文件或金融交易中册赛,多個(gè)簽名者可以使用秘密共享技術(shù)來生成數(shù)字簽名,從而增加簽名的安全性震嫉。
? ? 3. 加密密鑰管理(encryption key management):秘密共享可以用于管理加密密鑰击奶,以確保密鑰只能被授權(quán)的人訪問。例如责掏,在網(wǎng)絡(luò)安全中柜砾,企業(yè)可以使用秘密共享來管理其加密密鑰,以確保敏感數(shù)據(jù)的安全性换衬。
? ? 4. 密碼恢復(fù)(password recovery):秘密共享可以用于密碼恢復(fù)痰驱,允許用戶在忘記密碼的情況下恢復(fù)其賬戶。例如瞳浦,在社交媒體或電子郵件賬戶中担映,用戶可以使用秘密共享技術(shù)來生成密碼恢復(fù)密鑰,以便在需要時(shí)恢復(fù)其賬戶叫潦。
總之蝇完,秘密共享技術(shù)在許多領(lǐng)域都有成功的應(yīng)用,它提供了一種非常有用的工具矗蕊,可以幫助保護(hù)隱私和確保安全短蜕。
總結(jié)
隱私計(jì)算秘密共享方案是一種保護(hù)隱私的技術(shù),能讓多個(gè)人在不暴露私密數(shù)據(jù)的情況下完成特定計(jì)算任務(wù)傻咖。參與者把私密數(shù)據(jù)分成多份朋魔,加密后分發(fā)給其他參與者,只有擁有所有分片的參與者才能解密數(shù)據(jù)并進(jìn)行計(jì)算卿操,保護(hù)每個(gè)參與者的隱私警检。這種方案可應(yīng)用于各種需要多方參與計(jì)算的場(chǎng)景,比如金融風(fēng)險(xiǎn)評(píng)估和醫(yī)療數(shù)據(jù)分析害淤。
參考資料
-?知乎 - 禿頂?shù)拇a農(nóng) - 隱私計(jì)算加密技術(shù)-秘密分享
-《隱私計(jì)算白皮書2022》?
- 《隱私計(jì)算》 陳凱扇雕,楊強(qiáng)