密碼學原語如何應用?解析密文同態性的妙用 | 隱私保護週三見第12論

買賣虛擬貨幣

隱私資料在密文形式下是否依舊可以加減乘除?其背後的同態性原理具體指什麼?半同態性和全同態性有什麼區別?單金鑰和多金鑰同態加密有哪些奇妙的應用場景?

隱私保護方案設計,往往需要在密文狀態下,對隱私資料進行特定的業務操作,以此保障資料的機密性。

沿用上一論的電子支付例子,客戶目前擁有一張面額1000元的電子支票,電子支票以密文憑證形式儲存,流轉過程中不會輕易洩露金額。客戶使用這張支票時,消費額可能低於1000元,需要將支票進行拆分找零。假定消費額為200元,這一支票需要被拆分成兩份密文憑證,面額200元的給商戶,面額800元的留給客戶自己作為找零。

這個過程中,存在三個隱私保護相關的主要功能點:

客戶不希望其他人(包括商戶)獲知找零的金額為800元,相當於在消費時能保護客戶自身財產總額相關資訊不洩露。

商戶需要驗證密文支票在本次消費前的餘額不小於200元,但無需知道具體的餘額。

簽發密文支票的銀行需要驗證,客戶和商戶在交易後,沒有憑空造出更多的錢,即消費額與找零額相加等於拆分前的電子支票中的餘額。

以上功能點涉及如何在不解密的限制下,對隱私資料的密文形式進行計算和驗證。而解決問題的關鍵,就在於密文同態性的使用。

在資料業務中,密文同態性在需要隱私保護的相關場景方案中應用十分廣泛,可以實現隱私資料可信跨域協作、聯合資料發掘等高價值需求,在多方資料協作、機器學習、雲端計算等熱門領域皆有用武之地。密碼學同態究竟有何奇妙之處?且隨本文一探究竟。

同態性

同態(Homomorphism)的概念起源於抽象代數,具體是指兩個代數結構(例如群、環、向量空間等)之間保持結構不變的對映。

對應地,密碼學意義中的同態,多指一類代數結構能夠滿足在指定運算下結構不變的性質。例如,函式f(x)=3x對應的代數結構滿足加法同態性,函式f(x)=x^3對應的代數結構滿足乘法同態性。

同態性在密碼學中最常見的應用之一,就是用來構造同態加密演算法。

同態加密允許在不解密的條件下,直接對密文形式下的隱私資料進行特定形式的代數運算,運算效果等同於將隱私資料明文直接計算後再加密所獲的效果。

這項技術試圖實現隱私資料協同計算中的資料密文可計算,但明文不可見的效果。

同態加密一直是密碼學研究領域的一個重要課題,經典的演算法有RSA、ElGamal、Paillier加密演算法。2009年9月,Craig Gentry從理論上取得了重大突破,提出了全同態加密的構造方法,即可以在不解密的條件下,對隱私資料的密文形式進行任意形式的運算,並使得運算之後的結果密文滿足同態性。

除了同態加密外,其他密碼學原語,如上一論中提及的密碼學承諾,也可能具有同態性。

同態加密與具有同態性的密碼學承諾在功能上的區別在於:

同態加密重在計算,即對多方提供的隱私資料的密文形式進行一定計算後,對結果密文解密後得到的值,等同於對明文資料進行對應運算得到的結果。這個過程不會洩露隱私資料明文,但解密之前無法獲知結果。

具有同態性的密碼學承諾重在驗證,即透過密碼學承諾密文形式的同態性,對於已知的結果,構造相應的零知識證明,用以證明多個承諾滿足一定的約束條件。密碼學承諾難以支援計算結果未知、且需要從多方收集隱私資料的密文計算過程。

同態性在不同的密碼學原語中會有不同的功能和限制,本文以同態加密演算法為例,對同態性的特性和應用進行分享,其他相關密碼學原語會在後續專題中展開。

半同態vs全同態

同態加密根據支援的運算型別的限制,可分為半同態加密(SWHE,Somewhat Homomorphic Encryption或PHE,Partially Homomorphic Encryption)和全同態加密(FHE,Fully Homomorphic Encryption)。

對於一個半同態加密演算法,其密文形式僅僅對部分運算方式滿足同態性,有代表性的密碼學演算法體系如下:

加法運算同態性:Unpadded RSA,ElGamal,Benaloh,Paillier

邏輯運算同態性:Goldwasser-Micali

半同態加密演算法的優點在於構造相對簡單,工程實現效率高,目前已經可以達到商用的效能要求。

對於引言中密文支票電子支付的例子,使用一個具備加法運算同態性演算法便可以構造出滿足相關的隱私保護需求的密碼學協議。除了支付之外,對於日常業務中的大多數場景,如投票、選舉、競拍等,半同態加密演算法一般都可以滿足對應的隱私保護需求。

對於一個全同態加密演算法,其密文形式在理論上對任意運算方式都滿足同態性。對於資料密文計算相關同態加密演算法設計,這一要求通常體現為密文對應的代數結構對加法和乘法同時滿足同態性。

對於任意的隱私資料x,y,全同態加密演算法提供了一對加密演算法E和解密演算法D,滿足如下關係:

相比半同態加密演算法,全同態加密演算法功能更強大、設計更復雜,整體效能遠不及半同態加密演算法。例如可能面臨密文資料膨脹困擾。相關研究報告顯示,在一次使用全同態加密開源庫為敏感醫療資料構建密文線性回顧模型的嘗試中,需要將隱私資料進行編碼轉換,對映到密文的向量空間中。

此過程,1M的明文資料編碼後可能膨脹至約10G密文資料;同時,針對值域範圍為512位的明文資料,單次密文乘法運算,在普通個人計算機實測耗時約5秒左右,通常一個需要全同態計算的場景涉及的密文乘法次數很多,總體耗時較高。

由此可見,全同態加密演算法的願景雖美,但目前還處於理論探索層面,離工程實用化、支援高頻次和大資料量的業務需求尚有一定距離。

單金鑰vs多金鑰

同態加密根據資料控制方的數量,可分為單金鑰同態加密(Single Key Homomorphic Encryption)和多金鑰同態加密(Multi-key Homomorphic Encryption)。

早期的同態加密演算法都是單金鑰演算法,主要應用於外包計算(Outsourced Computation)場景。資料控制方對自身的資料進行加密,然後傳送到雲端計算服務平臺,在密文的形式下完成一系列運算,最後下載結果密文,本地解密之後獲得最後的計算結果。

上一節提到的ElGamal、Paillier等加密演算法都是單金鑰同態加密,即對於隱私資料只能使用同一對的金鑰進行加解密。

單金鑰同態加密優點在於構造相對簡單、效能高,可用於有一定信任基礎或強監管環境下的聯合計算場景。

由於涉及到可信初始化和金鑰選用的問題,單金鑰同態加密在多方參與的協作場景中,會遇到不少挑戰,例如:

如何決定使用哪一方提供的金鑰?資料由誰來解密?

如何平衡單金鑰所代表的單一資料控制權?如何確保資料提供方的敏感資料輸入不被解密?如何防範資料控制方惡意提前終止協議?

如何讓所有參與方都能驗證最終結果正確性?

實際業務流程中,隱私資料可以由多方提供,在可信初始化之後使用同一個公鑰加密資料,並彙總密文資料進行計算,計算結束之後,需要委託可信方或者使用分散式解密協議,對最終結果進行解密。

相比單金鑰同態加密演算法,多金鑰同態加密較好地解決了信任相關的問題。

一個多金鑰同態加密演算法,允許不同參與方使用各自不同的金鑰對加密,加密後的密文可以透過各個參與方的公鑰進行密文擴充套件,擴充套件後的密文對於指定的運算方式依舊滿足同態性。解密過程可以透過分散式解密協議,在不洩露各自資料私鑰的前提下,對約定的結果密文進行解密。

典型的多金鑰同態加密演算法可以參考Clear and McGoldrick (CRYPTO 2015)、Mukherjee and Wichs (EUROCRYPT 2016)相關的論文。

目前多金鑰同態加密方案,隨著參與方個數的增加,系統效能會急劇降低。對於一些需求比較明確的多方協作場景,相較於多金鑰同態加密方案,定製構造的安全多方計算協議或許更有效。

總體而言,密文同態性可以為業務場景中,常見的隱私資料的計算和驗證需求,提供有效解決方案,根據具體的業務需求,基本技術選型可以參考下圖:

正是:隱私資料密文亦無妨,計算驗證同態兩相宜!

具有同態性的密碼學原語提供了一系列直觀、便捷的金鑰學協議構造利器,在保障隱私資料機密性的同時,允許多個協作方對隱私資料的密文形式進行直接運算和驗證操作,以此適配多樣化的隱私保護需求。

除計算和驗證需求外,多方授權也是常見的業務需求之一,如對多方共有的業務資料進行授權使用,此時需要用到門限密碼學相關技術,欲知詳情,敬請關注下文分解。

---END---

《隱私保護週三見》

“科技聚焦人性,隱私迴歸屬主”,這是微眾銀行區塊鏈團隊聯合零壹財經推出《隱私保護週三見》深度欄目的願景與初衷。每週三晚8點,專家團隊將透過欄目,圍繞即時可用場景式隱私保護高效解決方案WeDPR的核心技術點,和各位一起探尋隱私保護的發展之道。

欄目內容含括以下五大模組:關鍵概念、法律法規、理論基礎、技術剖析和案例分享,如您有好的建議或者想學習的內容,歡迎隨時提出。

往期集錦

第1論|隱私和效用不可兼得?隱私保護開闢商業新境地

第2論|隱私合規風險知幾何?資料合規商用需過九重關

第3論|密碼學技術何以為信?深究背後的計算困難性理論

第4論|密碼學技術如何選型?初探理論能力邊界的安全模型

第5論|密碼學技術如何選型?再探工程能力邊界的安全模型

第6論|密碼學技術如何選型?終探量子計算通訊的安全模型

第7論|密碼金鑰傻傻分不清?認識密碼學中的最高機密

第8論|金鑰繁多難記難管理?認識高效金鑰管理體系

第9論|密碼學原語如何應用?解析單向雜湊的妙用

第10論|密碼學原語如何應用?解析密碼學特有的資料編解碼

第11論|密碼學原語如何應用?解析密碼學承諾的妙用

上下滑動檢視更多

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;