密碼學的未來:對加密資料進行計算

第三方雲服務為企業降低了複雜性,提供了靈活性。然而,組織需要能夠將其資料和客戶資料委託給雲服務提供商(CSP),這些提供商通常被激勵將這些資料貨幣化。與此同時,美國加利福尼亞州的《加利福尼亞消費者隱私法案(CCPA)》、《美國消費者線上隱私權法案(COPRA)》、《歐盟通用資料保護條例(GDPR)》和《中華人民共和國個人資訊保護法(PIPL)》等法規旨在保護消費者的隱私,不合規的組織將受到嚴重罰款以及名譽損害。這導致了組織在資料隱私和實用性之間的權衡。然而,全同態加密(FHE)允許組織確保其客戶的隱私,而不損害他們從資料中獲取見解的能力。

同態加密允許計算加密資料而無需解密。相反,計算結果保存在加密域中(將明文視為未加密域,密文視為加密域)。當解密時,其結果與在未加密域上執行的操作相同。FHE可用於私有儲存和計算,允許加密資料,並將其外包給商業雲環境,以便在加密時處理。

儘管FHE有很多應用,但請考慮兩個用例:私有聯繫人發現和日誌異常檢測。例如,要將好友添加到訊息服務中,使用者必須將他們的聯繫人號碼或電子郵件上傳到應用程序的伺服器上。儘管使用者的聯繫人資訊可以加密以防在傳輸到應用伺服器期間被竊聽,但是必須在伺服器上對聯繫人資訊解密以計算哈希值並檢測與已經使用該服務的其他人是否匹配。未加密的資料可以以任何方式使用,使用者被迫將其資料信任給應用程序。另一個用例是從日誌資料中檢測洩露事件(IoC)。第三方安全工具,如安全資訊和事件管理(SIEM)系統和擴展檢測和響應(XDR)工具,需要訪問未加密的日誌以檢測異常。使用FHE,可以對加密資料執行這些操作,而不會損害使用者資料的隱私。

全同態加密

全同態加密

FHE計劃最初設想於1978年,即RSA計劃發佈一年內。支持加法或乘法的部分同態加密方案已經存在,包括:

  • RSA,一種用於線上資料傳輸的非對稱加密,基於將兩個大素數的因式分解的實際困難

  • ElGamal(乘法同態),一種基於Diffie-Hellman金鑰交換的非對稱金鑰加密演算法,用於公鑰加密,提供了一種共享金鑰的方法,但不允許安全通訊

  • Paillier(加法同態),一種基於計算n個餘類的大計算量公鑰密碼學概率的非對稱演算法

美國電腦科學家Craig Gentry於2009年首次提出了基於格的FHE方案。格L(B)是n個線性獨立向量的基B={b1,…,bn}的所有整陣列合的集合。也就是說,格定義為:

L(B)={ B ‧ z : z ϵ Zn}

FHE方案支持加法和乘法(無限)操作,如下所示:

HE(a+b)=HE(a)+HE(b) and HE(a*b)=HE(a)*HE(b)

同態加密方案有三種類型:

  1. 部分同態加密(PHE)——僅允許對加密資料執行一組有限的操作

  2. 些許同態加密(SHE)——允許在一定複雜度下執行有限數量的操作

  3. 全同態加密(FHE)——允許無限次執行任何數學運算

用例

FHE可以在許多場景中實現隱私保護計算,包括應用私有資訊檢索(PIR)協議、私有搜尋、私有聯繫人發現、安全多方計算(MPC)以及SIEM或XDR中的日誌異常檢測。例如,PIR協議允許從伺服器檢索條目而不顯示檢索到的內容。MPC為相關使用者創建了安全演算法以在共同輸入計算函數(過程資料)的同時保持這些輸入的隱私。實際上,Microsoft Edge將FHE應用於密碼監控。

如圖1所示,傳統的(流行的)雲端運算和儲存解決方案要求在執行操作(例如發現使用者的聯繫人中有多少人正在使用訊息服務)或從系統日誌中檢測任何異常之前,解密客戶資料(通過對稱或非對稱加密方案)。這將潛在的敏感客戶資料暴露給雲供應商。客戶必須信任提供商的資料隱私訪問控制策略。

FHE利用了嚴格的數學證明,客戶資料隱私通過加密技術得到保證。因此,CSP將無法訪問未加密的客戶資料以進行儲存或計算。

同態計算

一些FHE(加法和乘法)包括Brakerski-Entry-Vaikuntanathan(BGV)、Fan-Vercauteren(FV)或Brakerski-Fan-Vercuteren(BFV),以及Cheon-Kim-Kim-Song(CKKS)。所有這些方案都基於環上容錯學習問題(RLWE)的難易程度,在加密和金鑰生成過程中添加噪聲以實現難易屬性。為了理解如何允許對加密資料進行計算,探索用於在RSA、ElGamal和Paillier中執行部分同態以及在BFV方案中執行全同態的底層數學很有幫助。

RSA密碼系統(無界模乘法)

如果RSA公鑰的模量為n,加密指數為e,則訊息m的加密值為Ɛ(m)=me mod n。RSA中兩條加密訊息的乘法為:

Ɛ(m1) ‧ Ɛ(m2)=m1em2emod n

=(m1m2)emod n

=Ɛ(m1‧ m2)

如圖2所示,背景較深(橙色)的單元格表示正確結果,只有當兩個整數的相加為零或將任何正整數與零相加時,才會產生準確的結果。在所有其他情況下,它會生成一個不正確的和。

圖3顯示了RSA的乘法性質,如果乘法是非負的,則產生正確的結果,如果乘法為負,則產生不準確的結果。

ElGamal密碼系統(無界模乘法)

ElGamal密碼系統(無界模乘法)

在ElGamal密碼系統中,在具有生成器G的q階循環組G中,如果公鑰為(G,q,G,h),其中h=gx,x為私鑰,則對於某個隨機rƐ{0,…,q-1},訊息m的加密為Ɛ(m)=(gr,m·hr)。ElGamal中兩個密碼的乘法為:

Ɛ(m1) ‧ Ɛ(m2)=(gr1, m1‧ hr1) (gr2, m2‧ hr2)

=(gr1+r2, (m1‧ m2) hr1+r2 )

=Ɛ(m1‧ m2)

如圖4所示,ElGamal無法預測兩個整數相加的正確結果。然而,圖5顯示了ElGamal的乘法性質,它為負乘法和非負乘法生成了準確的結果。

Paillier密碼系統(無界模加法)

Paillier密碼系統(無界模加法)

在Paillier密碼系統中,如果公鑰是模n和基g,則對於某個隨機rƐ{0,…,n-1},訊息m的加密為Ɛ(m)=gm rn mod n2。在Pallier中添加了兩條加密訊息:

Ɛ(m1) ‧ Ɛ(m2)=(gm1r1n)(gm2r2n) mod n2

=gm1+m2 (r1r2)nmod n2

=Ɛ(m1+m2)

圖片來源於公共圖片庫

圖片來源於公共圖片庫

Fan-Vercauteren (FV) 或 Brakerski-FanVercauteren (BFV) 方案

FV/BFV和BGV方案非常相似,計算是在整數上進行的。然而,CKKS可以對精度有限的複數進行計算。這意味著BFV和BGV是獲得準確結果的更好選擇,而CKKS最適合機器學習(ML)任務,因為CKKS中的結果是近似值。

BFV和CKKS允許批處理將明文向量(批處理)放入單個密文中。這些所謂的批處理方案將多個值打包成單個密文(通常為數千個),並以單個同態操作的代價對所有值執行操作。批處理是自FHE發現以來最突出的加速來源之一。CKKS特別適合數字和ML應用,因為所暗示的近似值是可以管理的,並且使用的加密參數比BGV和BFV更快。

加密明文域P中的明文訊息M:

  • 從R_2生成一個隨機多項式u,其中R_2是用於生成整數係數為-1,0或1的多項式的金鑰分佈。

  • 從χ生成兩個小的隨機多項式e1和e2,其中χ是誤差分佈(通常是離散高斯分佈),定義參數為均值μ和標準差σ / R,邊界為整數β。e1和e2被稱為誤差或噪聲項。

  • 訊息M的密文C是一對值C1和C2。加密域C中的C=(C1,C2)可以描述為:

C1=[PK1‧ u+ e1+ ∆M]q

C2=[PK2‧ u+ e2]q

Rq是均勻隨機分佈。符號[·]q表示多項式運算應該對q進行模運算。

作為參考,兩個密文的同態加法H+為:

H+(C(1),C(2))=([C1(1)+C1(2)]q,[C2(1)+C2(2)]q)= (C1(3),C2(3)

=([PK1‧ (u(1)+u(2))+(e1(1)+e1(2))+ ∆(M(1)+M(2)])q,

([PK2‧ (u(1)+u(2))+(e2(1)+e2(2))]q

([PK1‧ u(3)+e1(3)+ ∆(M(1)+M(2))]q, ([PK2‧ u(3)+e2(3)]q

將錯誤添加到密碼中提供了安全性,但隨著密碼的每一次乘法,錯誤都會增加,從而給乘法帶來限制。如果錯誤變得足夠大,則無法再成功解密密碼。

結論

FHE是密碼學的新興倡導者,在PIR、MPC、私有聯繫人發現和隱私保護日誌異常檢測方面具有潛在用例。FHE允許在不解密的情況下對加密資料進行計算,從而可以幫助組織遵守隱私法規。部分同態方案(如RSA、ElGamal和Paillier)和全同態BFV方案的數學運算有助於希望深入FHE並將其納入安全項目的從業者。科技巨頭正在支持全同態加密方案(例如,IBM Security提供全同態加密作為服務)。然而,目前關於允許的操作類型和計算時間的計算限制仍然是立即採用FHE的障礙。

相關文章

【漏洞通告】F5 8月多個安全漏洞

【漏洞通告】F5 8月多個安全漏洞

0x00 漏洞概述 2022年8月3日,F5發佈安全公告,修復了其多個產品中的多個安全漏洞,這些漏洞可能導致資訊洩露、安全繞過、許可權提升和...

CloudSecOps雲安全運營實踐指南

CloudSecOps雲安全運營實踐指南

雲端運算已經獲得了大量企業使用者的青睞,併成為其數字化轉型發展的基礎,但是也面臨著各種各樣的風險,從勒索軟體到供應鏈攻擊,再到雲內部威脅和配...

關於雲端運算應用安全性的5大誤解

關於雲端運算應用安全性的5大誤解

在全球新冠疫情大流行期間,世界各地的企業組織紛紛將數字化建設的重點轉移到為遠端員工和虛擬環境提供支持,因此雲端運算的建設和應用得到了快速發展...

雲安全事件響應的難點、流程與最佳實踐

雲安全事件響應的難點、流程與最佳實踐

雲端運算技術的出現,改變了資料計算和儲存的方式,它解決了在海量資料之下,傳統資料儲存技術的性能瓶頸。鑑於現代企業組織對雲的使用變得越來越普遍...

Go 語言發佈 | 歷史上的今天

Go 語言發佈 | 歷史上的今天

整理 | 王啟隆 透過「歷史上的今天」,從過去看未來,從現在亦可以改變未來。 今天是 2022 年 11 月 10 日,在 1994 年的今...