用于使输入同态随机化的方法和系统

摘要

描述了一种使输入随机化的全同态方法和系统，其中，在交换环上执行所有计算。详细说明使用矩阵和多项式执行随机化的等效方法以及混合矩阵和多项式函数的方式。进一步描述了矩阵和多项式函数的加法、乘法以及除法。通过在环ZN上执行函数模数N的计算，函数可用作加密函数。该方法和系统还可用于验证由第三方执行的计算的返回结果对于在本文中描述的任何计算是有效的。还描述了相关方法、系统以及设备。

主权项

一种使输入随机化的全同态方法，其中，在下文中表示为CR的交换环上执行所有计算，所述方法包括：接收包括CR中的k个输入元素的序列的输入，所述输入表示为INP；执行(a)和(b)中的任一个：(a)随机选择在下文中表示为S的CR中的秘密n×n矩阵，S用作对称随机化密钥，其中，S包括在CR上的可逆矩阵；确定S^‑1；为包括INP的k个元素之中的m个不同的输入元素的每个集合i，在CR中选择n‑m(n减去m)个随机数Y₁,Y₂,...,Y_n‑m，其中，0<m<k+1以及m<n，从INP中选择要被共同随机化的所述m个不同的输入元素并且所述m个不同的输入元素在下文中表示为X₁,X₂,...,X_m，其中，输入元素为X₁,X₂,...,X_m；在所述随机数Y₁,Y₂,...,Y_n‑m的集合之中选择至少一个随机数；并且可选地，一个或多个常数放在表示为M的n×n对角矩阵的对角线中，其中，除了所述对角线以外，矩阵M仅由0填充；并且通过使用在下文中表示为MRHT的基于矩阵的随机化和同态变换函数，确定表示为{X_im}＝X₁，X₂，…，X_m的集合i中的m个输入元素的随机输出A_im，其中：从而产生与m个输入元素的所述集合i{X_im}＝X₁，X₂，…，X_m对应的随机输出A_im；以及(b)在CR中选择n个随机数，所述n个随机数在下文中表示为v₁,v₂,...,v_n；确定公共多项式$P\left(v\right)={\Pi }_{i=1}^n(v-v_i)={\Sigma }_{j=0}^n{C}_j·v^j(C_n=1)$选择在下文中表示为PRHT(X_im)的基于多项式的随机化和同态变换函数，包括以v为变量的形式为的任何函数，所述函数满足以下方程：${\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_1}^j=X_1,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_2}^j=X_2,...,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_m}^j=x_m;$在CR中为a_i，m，a_i，m+1…，a_i，n‑1选择将产生a_i，0，a_i，1…a_i，m‑1的以上方程的解的n‑m个随机值，并且执行(c)和(d)中的任一个：(c)产生与包括集合(a_i0，a_i1，…，a_in‑1)以及P(v)的公共系数集合(C₀，C₁，…，C_n‑1，C_n)的输入元素X₁,X₂,...,X_m对应的随机输出A_im，其中，需要公共系数集合(C₀，C₁，…，C_n‑1，C_n)以用于利用输入元素来执行运算的算术；并且(d)在CR中为给定的输入元素X₁,X₂,...,X_m选择将解出以下关于未知数a_i0，a_i1，…，a_in‑1的n个联立方程的n‑m个随机值R₁,R₂,...,R_n‑m：${\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_1}^j=X_1,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_2}^j=X_2,...,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_m}^j=X_m,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_{m+1}}^j=$$R_1,$${\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_{m+2}}^j=R_2,....,{\Sigma }_{j=0}^{n-1}{a}_{\mathrm{ij}}·{v_n}^j=R_{n-m},$从而为X₁,X₂,...,X_m产生包括所述集合(a_i0，a_i1，…，a_in‑1)以及P(v)的公共集合(C₀，C₁，…，C_n‑1，C_n)的随机文本。