用於使輸入同態隨機化的方法和系統的製作方法

2023-10-05 02:27:44 2

用於使輸入同態隨機化的方法和系統的製作方法
【專利摘要】描述了一種使輸入隨機化的全同態方法和系統，其中，在交換環上執行所有計算。詳細說明使用矩陣和多項式執行隨機化的等效方法以及混合矩陣和多項式函數的方式。進一步描述了矩陣和多項式函數的加法、乘法以及除法。通過在環ZN上執行函數模數N的計算，函數可用作加密函數。該方法和系統還可用於驗證由第三方執行的計算的返回結果對於在本文中描述的任何計算是有效的。還描述了相關方法、系統以及設備。
【專利說明】用於使輸入同態隨機化的方法和系統
[0001] 相關申請
[0002] 本申請要求NDS公司的於2012年7月26日提交的未公布以色列申請IL 221152 以及於2013年1月24日提交的IL 224400的優先權權益。

【技術領域】
[0003] 本發明涉及同態隨機化和加密的系統和方法。

【背景技術】
[0004] Kristin Lauter、Michael Naehrig、Vinod Vaikuntanathan 的 2011 年 7 月的 Can Homomorphic Encryption be Practical描述了越來越多的數據儲存和管理外包給雲服務 的發展對個人和生意等增加了很多新的隱私憂慮。如果用戶將發送給雲的數據加密，則可 以令人滿意地解決隱私憂慮。如果加密方案是同態，則即使加密，雲也可以依然在數據上進 行有意義的計算。
[0005] 政府、工業以及社團追求實際的同態加密的承諾。IBM和微軟朝著其潛在的承諾積 極地進行研究，這是因為（例如）通過公共（公開）雲伺服器時限'安全的加密搜索'（或 者'隱私保護信息傳遞'）；例如，伺服器在加密的醫療資料庫中搜索（不了解該查詢或結 果），並且由安全客戶端遞送加密的結果以進行解密。'安全函數評估'的又一個應用在於， 公開的不受信任的伺服器為輸入執行秘密算法，而不了解算法或結果的性能。因此，假設獲 得了公共雲伺服器的公開訪問的黑客（甚至是惡意的雲服務員工）未呈現危害信息或交易 的任何威脅。這種同態加密的應用很多，並且能夠廣泛地使用雲計算，例如，允許注重安全 性的政府和金融業通過將其資料庫加密來將其業務移動到公共雲，並且使其能夠用於雲計 算，不必擔心受到雲服務或外部黑客的安全侵害。而且，這種隱私保護技術幫助社團處理對 機密數據的不斷增加的攻擊，更不必說隱私雲。要注意的是，以上內容的安全性並非運動目 標範例（moving-target paradigm)(例如，為了阻礙黑客的分析而快速更新的軟體）或者 清晰的軟體混淆的結果，而是同態密碼系統的數學性質所固有的。
[0006] 迄今為止，發現同態系統不切實際；僅受限的特例約束使用顯示對實際用途具有 某種可能性。
[0007] Gentry 等人在 ST0C' 09，Proceedings of the 41st Annual ACM Symposium on Theory ofComputing的第169-178頁中提出了全同態加密方案-即，允許人們通過加密的 數據（不需要能夠解密）評估電路的方案。
[0008] Xiao 等人在 www. utdallas. edu/?ilyen/techrep/HPbound. pdf 中可獲得的題為 An Efficient Homomorphic Encryption Protocol for Multi-User Systems 的文章中提 出了針對同態加密問題的解決方案。
[0009] 還認為以下專利參考文獻反應了現有技術的狀況：
[0010] Chen 等人的 US 7, 254, 586 ;
[0011] INTRINSIC ID B. V?的 W0/2010/100015 ;
[0012] Takashima 的 US 20100329454 ;
[0013] Juels 的 US 7,472,093 ;以及
[0014] Gentry 的 US 20110110525。


【發明內容】

[0015] 在本發明的某些實施方式中，本發明試圖提供一種用於計劃用於加密應用的ZN (ZN是殘數模數N的環；N由兩個質數（p和q)進行因子分解）中的特定數據的改進的實用全 同態加密系統。對於某些應用，在ZN中期望使用隨機的大數目，其中，例如，根據先有技術 的當前水平，出於實際考慮，大數目是1Kbit。
[0016] 同態加密是如下一種加密形式：允許在密文（cipher text)上執行特定類型的計 算並且獲得加密結果，該結果是對明文（plain text)執行的運算結果的密文。例如，一個 人可將兩個加密數相加，並且然後，另一個人可將結果進行解密，這兩個人都不能找出各個 數的值。同態加密方案通過設計具有可塑性（malleable，延展性）。各種密碼系統的同態 性能可用於創建安全表決系統、抗衝突的散列函數、私有信息檢索方案，並且通過確保處理 數據的機密性，能夠廣泛地使用雲計算。
[0017] 在本文中提出了用於數據的實際隨機化（通過交換環）的高性能非確定性全同態 方法，並且在環ZN上的模N數據（mod-N data)的對稱加密非常適合於加密應用。例如，本 發明的實施方式確保多變量輸入（multivariate input)或公共多項式函數的係數以在公 開的不受信任的環境中運行。所使用的方法還可為某些現有的密碼算法提供抵抗某些攻擊 的增強保護，例如，保護0SS公共密鑰籤名抵抗Pollard攻擊。而且，這些方法的有效性質 (每個加密具有一個大數乘法，並且兩個加密值的乘積為六個）激勵並且能夠使用低成本 協同安全平臺以用於諸如密鑰散列或私有密鑰推導算法的應用。這種平臺包括由運行同態 算法的不受信任的高性能伺服器支持的低成本（低性能）安全元件。已經表明，隨機明文 數據是同態加密的安全性的證明的充分條件。在交換環上的數據的同態隨機化提供了抵抗 例如在AES密鑰上的側信道（side-channel)攻擊（DPA)的保護。而且，這些方法具有提供 故障檢測和計算數據完整性的驗證的平行的並且不可分離的計算的固有耦合。
[0018] 期望所提出的加密方案為很多應用和客戶/伺服器模型提供安全性解決方案，其 包括：
[0019] 1、低成本安全平臺；以及
[0020] 2、作為上述公共雲伺服器的公開的不受信任的平臺。
[0021] 低成本安全平臺由提供協同安全性的兩個元素組成：
[0022] a)執行同態計算同時隱藏其秘密的低安全性高性能元件（例如，PC(個人電腦）、 STB (機頂盒）或移動計算裝置），以及
[0023] b)安全地長期保密並且使用它們來在可信環境中執行一些基礎計算的高安全性 低性能元件（例如，低成本SC(智慧卡）、RFID (射頻識別）、SIM(用戶識別模塊）、或者服 務安全的執行環境的安全0TP ( -次性可編程存儲器））。
[0024] 該平臺標記為（LHHL)或（LH)2平臺。這種平臺可限定由STB和SC構成的安全客 戶端、具有SM的智慧型電話或者具有Arm TrustZone (或者其他安全的執行環境）的連接電 視。
[0025] 例如，並且不限制上文的普遍性，公開平臺是存在於假設為不受信任的公共網絡 (雲）中的PC (或在PC上運行的處理）。
[0026] 通過舉例，應用程式可使用數據的同態加密以：
[0027] 使用同態修改的OSS(HoMoSS)的有效的基於PK(公共/私有密鑰）的籤名。與 RSA籤名操作相比，在該新的方案之下，使0SS免於Pollard攻擊（如下面所述）並且基本 上保持其效率。在這種應用中，保持私有密鑰的籤名者是（LH)2平臺。可以在公開平臺內 進行PK籤名的驗證。
[0028] 隱藏對稱密鑰，例如，並且不限制上文的普遍性，通過（LH)2客戶端驗證密鑰散列 (例如，安全HMAC驗證），具有SC的STB-其中，STB執行大部分驗證操作的同態計算，而SC 使用秘密對稱密鑰執行需要加密的最終步驟。
[0029] 因此，根據本發明的實施方式，提供了一種使輸入隨機化的全同態方法，其中，在 下文中表示為CR的交換環（commutative)上進行所有計算，所述方法包括：接收包括CR中 的k個輸入兀素的序列的輸入（表不為INP);執行（a)或（a)中的任一個：（a)在CR中隨 機地選擇秘密（seCret)nXn矩陣（在下文中表示為S)，S用作對稱隨機化密鑰，其中，S包 括CR上的可逆矩陣；確定S、對於包括INP的k個元素之中的m個不同的輸入元素的每個 集合i，其中，0 < m < k+1並且m < n，從INP中選擇要被共同隨機化的m個不同的輸入元 素，並且m個不同的輸入元素在下文中表示為Xi，X2,. . .，Xm，在CR中選擇n-m(n減去m)個 隨機數Yp Y2, . . .，Yn_m，其中，輸入元素為Xp X2, . . .，乂";在隨機數Y ^ Y2,. . .，Yn_m的集合之 中選擇至少一個隨機數；並且可選地，一個或多個常數放置在表示為M的nXn對角矩陣的 對角線上，其中，除了對角線以外，矩陣M僅由0填充；並且通過使用在下文中表示為MRHT 的基於矩陣的隨機化和同態變換函數，為在表示為{Xim} = Xi，X2，. . .，Xm的集合i中的m個 輸入兀素，確定隨機輸出Aim，其中：
[0030]

【權利要求】
1. 一種使輸入隨機化的全同態方法，其中，在下文中表示為CR的交換環上執行所有計 算，所述方法包括： 接收包括CR中的k個輸入元素的序列的輸入，所述輸入表示為INP; 執行（a)和（b)中的任一個： (a) 隨機選擇在下文中表示為S的CR中的秘密nXn矩陣，S用作對稱隨機化密鑰，其 中，S包括在CR上的可逆矩陣； 確定 為包括INP的k個元素之中的m個不同的輸入元素的每個集合i，在CR中選擇n-m(n減去m)個隨機數Y1,Y2,. . .，Yn_m，其中，0〈m〈k+l以及m〈n，從INP中選擇要被共同隨機化的 所述m個不同的輸入元素並且所述m個不同的輸入元素在下文中表示為X1,X2, ...，Xm，其 中，輸入元素為X1,X2, ...，Xm;在所述隨機數YpY2, ...，￥_的集合之中選擇至少一個隨機 數；並且可選地，一個或多個常數放在表示為M的nXn對角矩陣的對角線中，其中，除了所 述對角線以外，矩陣M僅由O填充；並且 通過使用在下文中表示為MRHT的基於矩陣的隨機化和同態變換函數，確定表示為 {Xim} =X1,X2，…，Xm的集合i中的m個輸入元素的隨機輸出Aim，其中：
從而產生與m個輸入元素的所述集合i{Xim} =X1,X2，…，應的隨機輸出Aim; 以及 (b) 在CR中選擇n個隨機數，所述n個隨機數在下文中表示為Vl，v2, ...，vn; 確定公共多項式Plv[If=,(y- 1?：> = 〇c.) .WIc>=I] 選擇在下文中表示為PRHT(Xim)的基於多項式的隨機化和同態變換函數，包括以V為變 量的形式為X?-#的任何函數，所述函數滿足以下方程：
在CR中為a^，a。Jri選擇將產生ai,。，Bi^ai,M的以上方程的解的n-m個隨 機值，並且 執行（c)和（d)中的任一個： (c) 產生與包括集合（aiCI，an，…，aiIri)以及P(V)的公共係數集合（Ctl,C1，…，Clri,Cn)的輸入元素X1,X2, ...，應的隨機輸出Aim，其中，需要公共係數集合（Ctl,C1，…，Cn+ Cn)以用於利用輸入元素來執行運算的算術；並且 (d) 在CR中為給定的輸入元素X1,X2，...，Xm選擇將解出以下關於未知數ai(l，an，…，ain_j^n個聯立方程的n-m個隨機值Ri，R2,. . .，Ri^:
包括所述集合（aiCI，an，…，aiIri)以及P(V)的公共集合（Cci,C1，…，Cn+Cn)的隨機文本。
2. 根據權利要求1所述的方法，其中，隨機化所述輸入INP包括連續應用函數PRHT(XJ 和MRHT(Xi)的組合，其中，Xi表示INP的m個不同的輸入元素的集合，並且其中：
3. -種用於將權利要求1的所述隨機化輸入去隨機化的方法，所述方法包括： 執行（a)和（b)中的任一個： (a)在CR上接收在下文中表示為Aim的輸出，所述輸出包括為nXn對角矩陣的隨機化Xim輸入，其中：
4. 一種用於將隨機化的Xi和隨機化的X2相加的方法，XJPX2根據權利要求1所述的 使輸入隨機化的全同態方法來隨機化，所述方法包括： 對於Xi，包括MRHT(Xi) =Ai; 接收AJPA2;並且 MRHT(X1)+MRHT(X2) =AfA2;並且 對於父1，包括卩冊1'%)=&^|，&11，?，&化_1: 接收PRHT(X1) =a10,an，…，aln_J[IPRHT(X2) =a20,a21，…，以及PM +.'! > 的CQ，C1，…Clri,Cn;並且 PRHT(X1)+PRHT(X2) =a10+a20,an+a21, ...,am-i+a；^。
5. -種用於將隨機化的Xi和隨機化的X2相乘的方法，X:和X2根據權利要求1所述的 使輸入隨機化的全同態方法來隨機化，所述方法包括： 對於Xi，包括MRHT(Xi) =Ai; 接收AJPA2;並且
7. 根據權利要求1-6中任一項所述的方法，其中，所述至少一個隨機化輸入包括加密 密鑰。
8. 根據權利要求7所述的方法，其中，所述加密密鑰包括AES密鑰。
9. 根據權利要求1-6中任一項所述的方法，其中，所述至少一個隨機化輸入包括模數N 多項式係數。
10. 根據權利要求9所述的方法，其中，所述模數N多項式係數用於私有函數密鑰生成。
11. 根據權利要求9所述的方法，其中，所述模數N多項式係數用於私有的基於散列的 消息認證碼。
12. 根據權利要求9所述的方法，其中，所述模數N多項式係數用於生成OSS籤名。
13. 根據權利要求1所述的方法，其中，所述輸入包括密文，所述輸出包括密文，並且在 環Zn上執行模數N的所有計算，其中，N是兩個質數的乘積，並且矩陣S包括對稱加密密鑰， 其中，所述加密函數表示為分別與MRHT和PRHT對應的MEnc和PEnc。
14. 根據權利要求13所述的方法，其中，加密所述明文包括連續應用加密函數PEnc= PRHT(Xi)和MEnc=MRHT(Xi)的組合，其中：
15. 根據權利要求3所述的方法，其中，所接收的輸出包括表示為C的密文，根據權利要 求13所述的方法產生所述密文C，並且所述去隨機化輸入包括明文，並且在環Z1J:執行模 數N的所有計算，其中，N是兩個質數的乘積，並且矩陣S包括對稱加密密鑰。
16. -種用於將一對密文輸出Ci和Cj相加的方法，Ci和Cj是根據權利要求13所述 的方法產生的密文，所述方法包括根據權利要求4所述的方法將Ci和Cj相加，其中，在環 Zn上執行模數N的所有計算，其中，N是兩個質數的乘積，並且矩陣S包括對稱加密密鑰。
17. -種用於將一對密文輸出Ci和Cj相乘的方法，Ci和Cj包括根據權利要求13所 述的方法產生的密文，所述方法包括根據權利要求5所述的方法將Ci和Cj相乘，其中，在 環Zn上執行模數N的所有計算，其中，N是兩個質數的乘積，並且矩陣S包括對稱加密密鑰。
18. -種用於將一對密文輸出Ci和Cj相除的方法，Ci和Cj包括根據權利要求13所 述的方法產生的密文，所述方法包括根據權利要求6所述的方法將Ci和Cj相除，其中，在 環Zn上執行模數N的所有計算，其中，N是兩個質數的乘積，並且矩陣S包括對稱加密密鑰。
19. 一種驗證由第三方執行的計算的返回結果為有效的方法，所述結果由根據權利要 求1-18中任一項所述的方法執行，對於使用表示為M的MRHT或MEnc函數返回的結果，所述 結果表示為1，並且對於使用表示為P的PRHT或PEnc函數返回的結果，所述結果表示為 扣，，所述結果包括對A1,A2，…，Ak執行的表示為f的同態計算的結果，其中，Ai等於M(XJ和P(Xi)中的一個；f%，A2，…，Ak)等於以下中的一個：M(f(Xi，X2，…，Xk)) =HM(X1)， M(X2), ...,M(Xk))以及Paft1,X2，…，Xk)) =MP(X1)J(X2), ...，P(Xk))，所述方法包括： 接收為以下形式的其中一個的f(A1,A2，…，Ak)的結果：
在所述結果為I?;丨的形式的情況下： 對於任何m,m= 1,2,…，n-1,計算表示為Q的f(Yml,Ym2，Ymk),其中，Ymj包括在 加密和隨機化\的一個中使用的第m個隨機值； 執行解密和去隨機化1?*"中的一個，從而從所產生的m+1行的矩陣對角線確定表示為E的f(Yml，Ym2，…?，Ymk);並且 如果E等於Q，則將f(Xi)的所述計算的所述結果視為有效；並且 在所述結果為R*P形式的情況下： 對於任何m,m= 1,2,…，n-1,計算表示為Q的f(Yml,Ym2，Ymk),其中，Ymj包括在 加密和隨機化\的一個中使用的第m個隨機值； 執行解密和去隨機化R*P中的一個，從而確定：
如果E等於Q，則將f(X1,X2，…?，Xk)的所述計算所述結果視為有效。
【文檔編號】H04L9/30GK104509024SQ201380039463
【公開日】2015年4月8日 申請日期:2013年7月25日 優先權日:2012年7月26日
【發明者】艾維爾德·傑尼斯, 以利沙·希布蘇什 申請人:Nds有限公司