[發(fā)明專利]用于使輸入同態(tài)隨機化的方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201380039463.2
• 申請日: 2013-07-25
• 公開（公告）號: CN104509024B
• 公開（公告）日: 2018-02-27
• 發(fā)明（設(shè)計）人: 艾維爾德·杰尼斯;以利沙·希布蘇什
• 申請（專利權(quán)）人: NDS有限公司
• 主分類號: H04L9/00
• 分類號: H04L9/00;H04L9/30
• 代理公司: 北京博浩百睿知識產(chǎn)權(quán)代理有限責(zé)任公司11134
• 代理人: 宋子良

1.一種使輸入隨機化的全同態(tài)方法，其中，在下文中表示為CR的交換環(huán)上執(zhí)行所有計算，所述方法包括：

接收包括CR中的k個輸入元素的序列的輸入，所述輸入表示為INP；

執(zhí)行(a)和(b)中的任一個：

(a)隨機選擇在下文中表示為S的CR中的秘密n×n矩陣，S用作對稱隨機化密鑰，其中，S包括在CR上的可逆矩陣；

確定S^-1；

為包括INP的k個元素之中的m個不同的輸入元素的每個集合i，在CR中選擇n-m(n減去m)個隨機數(shù)Y₁,Y₂,...,Y_n-m，其中，0<m<k+1以及m<n，從INP中選擇要被共同隨機化的所述m個不同的輸入元素并且所述m個不同的輸入元素在下文中表示為X₁,X₂,...,X_m，其中，輸入元素為X₁,X₂,...,X_m；在所述隨機數(shù)Y₁,Y₂,...,Y_n-m的集合之中選擇至少一個隨機數(shù)；并且可選地，一個或多個常數(shù)放在表示為M的n×n對角矩陣的對角線中，其中，除了所述對角線以外，矩陣M僅由0填充；并且

通過使用在下文中表示為MRHT的基于矩陣的隨機化和同態(tài)變換函數(shù)，確定表示為{X_im}＝X₁，X₂，...，X_m的集合i中的m個輸入元素的隨機輸出A_im，其中：

從而產(chǎn)生與m個輸入元素的所述集合i{X_im}＝X₁，X₂，...，X_m對應(yīng)的隨機輸出A_im；

以及

(b)在CR中選擇n個隨機數(shù)，所述n個隨機數(shù)在下文中表示為v₁,v₂,...,v_n；

確定公共多項式其中，C_j表示公共多項式P(v)的公共系數(shù)；

選擇在下文中表示為PRHT(X_im)的基于多項式的隨機化和同態(tài)變換函數(shù)，包括以v為變量的形式為的任何函數(shù)，所述函數(shù)滿足以下方程：

Σj=0n-1aij·v1j=X1,Σj=0n-1aij·v2j=X2,...,Σj=0n-1aij·vmj=Xm;]]>

在CR中為a_i，m，a_i，m+1...，a_i，n-1選擇將產(chǎn)生a_i，0，a_i，1...，a_i，m-1的以上方程的解的n-m個隨機值，并且

執(zhí)行(c)和(d)中的任一個：

(c)產(chǎn)生與包括集合(a_i0，a_i1，...，a_in-1)以及P(v)的公共系數(shù)集合(C₀，C₁，...，C_n-1，C_n)的輸入元素X₁,X₂,...,X_m對應(yīng)的隨機輸出A_im，其中，需要公共系數(shù)集合(C₀，C₁，...，C_n-1，C_n)以用于利用輸入元素來執(zhí)行運算的算術(shù)；并且

(d)在CR中為給定的輸入元素X₁,X₂,...,X_m選擇將解出以下關(guān)于未知數(shù)a_i0，a_i1，...，a_in-1的n個聯(lián)立方程的n-m個隨機值R₁,R₂,...,R_n-m：

從而為X₁,X₂,...,X_m產(chǎn)生包括所述集合(a_i0，a_i1，...，a_in-1)以及P(v)的公共集合(C₀，C₁，...，C_n-1，C_n)的隨機文本。