密碼學的未來：對加密數據進行計算
責編：gltian ｜2023-03-29 14:16:51第三方云服務為企業降低了復雜性，提供了靈活性。然而，組織需要能夠將其數據和客戶數據委托給云服務提供商（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)
同態加密方案有三種類型：
- 部分同態加密（PHE）——僅允許對加密數據執行一組有限的操作
- 些許同態加密（SHE）——允許在一定復雜度下執行有限數量的操作
- 全同態加密（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)=m1e?m2e?mod?n
=(m1?m2)e?mod?n
=?(m1???m2)
如圖2所示，背景較深（橙色）的單元格表示正確結果，只有當兩個整數的相加為零或將任何正整數與零相加時，才會產生準確的結果。在所有其他情況下，它會生成一個不正確的和。
圖3顯示了RSA的乘法性質，如果乘法是非負的，則產生正確的結果，如果乘法為負，則產生不準確的結果。
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密碼系統中，如果公鑰是模n和基g，則對于某個隨機r?｛0，…，n-1｝，消息m的加密為?（m）＝gm rn mod n2。在Pallier中添加了兩條加密消息：
?(m1) ???(m2)=(gm1r1n)(gm2r2n) mod?n2
=gm1+m2?(r1?r2)n?mod?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的障礙。