CN118402204B 加密计算方法、计算密文的表示的方法、设备和存储介质 （扎马简易股份有限公司）

2024.06.12PCT/EP2022/0809412022.11.07WO2023/110216EN2023.06.22US2019312728A1,2019.10.10BootstrappingEnablesEffiHomomorphicInferenASSOCIATIONFORCRYPTOLOGICRESEA.2021,1-18.一些实施方案针对一种计算机实施的加密计算方法(500)。所述方法对包括一个或多个随机掩码多项式以及由所述掩码多项式和明文导的掩码多项式和主体多项式乘以相应被乘数多伪随机数生成器的种子和所述主体多项式在数2使用伪随机数生成器来生成所述掩码多项式在所述傅里2.根据权利要求1所述的方法(500)，其中所述方法包括根据自举密钥执行可编程自3.根据权利要求2所述的方法(500)，其中行盲旋转，其中所述盲旋转计算单项式乘以按商多项式取模的测试多项式的GLWE类型加4.根据权利要求1_3中任一项所述的方法(500)，包括计算GGS包括将所述相应基于GLWE的密文的所述掩码多项式和所述主体多项式乘以基于所述基于5.根据权利要求4所述的方法(500)，其中所述方法6.根据权利要求1_3中任一项所述的方法(500)，包应用数论变换将相应被乘数多项式的系数转换到所述傅里叶域，和/或应用逆数论变换将计算出的多项式乘积在所述傅里叶域中的表示转换为计算出的多7.根据权利要求1_3中任一项所述的方法(58.根据权利要求1_3中任一项所述的方法(500)，3获得(610)要加密的明文；通过如下步骤生成(620)所述密文的表示，其中所述密文包括一个或多个掩获得(621)用于伪随机数生成器的种子；一将所述数论变换的逆应用(623)到所述掩码多项式的估值以确定所述掩码多项式的一将所述数论变换应用(625)到所述主体多项式的系数以确定所述主体多项式在所述输出(630)所述密文的表示，其中所述表示包括所述种子以及所述主体多存储器(140)，所述存储器用于存储表示密文的数据，其中所述密文包括一掩码多项式以及一个从所述掩码多项式和明文导出的主所述伪随机数生成器来生成所述掩码多项式在所述傅里叶域中45医学数据。这意味着提供医学模型的一方无法访问与加密医学数据相对应的明文医学数错学习问题的加密难度，特别是基于RLWE的密文的环容错学习(RLWE)问题。这种“基于6I.Chillotti等人的“TFHE:Fastfullyhomomorphicencryptionoverthetorus”，通过对GLWE加密单项式的指数中的LWE解密进行同态评估来减少LWE加密输入值中的噪声，编程的，因为输出值可以是将函数应用于输入值的结果。这种可编程自举的实施例在I.Chillotti等人的“Programmablebootstrappingenablesefficienthomomorphicinferenceofdeepneuralnetworks”,CyberSecurityCryptographyandMachineLearning(CSCML2021),LectureNotesinComputerScience的第12716卷,第1_19页，Springer,2021(通过引用纳入本文)中[0010]TFHE可编程自举依赖于GGSW类型(广义GSW类型，例如(RGSW类型)密文C与基于GLWE的密文c的所谓外积的计算。一般来说，对明文进行加密的GGSW类型密文C(例如在“Programmablebootstrappingenablesefficienthomomorphicinferenceofdeepneuralnetworks”中所描述的)包括多个相应基于GLWE的密文ci，所述密文对基于明文的相应值进行加密。外积的计算涉及将相应基于GLWE的密文ci与基于GLWE的密文c的相应被中1≤j<M。外积产生GGSW类型密文C和基于GLWE的密文c的乘积的加密。可编程自举基于包随机函数以获得掩码多项式的系数，并且将这个表示转换为对执行FFT的复数单位根的掩7以掩码多项式的常规系数表示生成掩码多项式，而是生成掩码多项式在傅里叶域中的表是针对从PRNG获得其系数的掩码多项式而不是像当今的TFHE类方案那样使用复数FFT的傅里叶域。数论变换是一种本身已知的在项式Xn_1以及质数幂模数q，其中n|q_1)，参见例如在J.vonzurGathen和J.Gerhard的的“Multidigitmultiplicationformathematicians”，未发表的手稿(可在https://选地结合使用NTT和/或其逆从该傅里叶域表示转换多项式或将多项式转换为该傅里叶域表示。8有与以随机生成系数的常规方式构造的密文相同的概率分布的密文，而复数FFT则不是这征在于使用可编程自举运算，该可编程自举运算基于对加密单项式的指数的解密进行评以在乘法之前将加法或乘法(乘以常数或另一傅里叶域表示的多项式)在傅里叶域中应用展的存储数据可用于计算掩码多项式和主体多项式与另外的被乘数多项式的另外的多项这可以通过丢弃掩码多项式并仅存储用于生成它们9多项式p(X)取模的多项式。例如，可以通过将多项素，在环R=Z/qz上定义所述多项式。或者，可以通过将多项式定义为(离散的)环面T,=q-1Z/Z(注意T,三Z/q2)上的Tg[X]/(P(X))中的多项式来定义模上的多项式。具体来说，任何多项式f(x)=zifx'eT,[XI/(p(x))(其中)可以与者是严格除以它的低次多项式。多项式定义在其上的集合的被定义为该多项式在M次本原单位根的幂的集合中的估值的集合。所述傅里叶表示可以与对M次本原单位根的相应幂的估值的逐点乘法相乘。为了在系数表示与傅里叶域表示之间,ω3d_1目，使得环Z/qz是元素数目为q≡1mod2N的质数域商多项式XN+1(特别是其中N是2的幂)是有益的，因为许多已知的同态加密方案(例此域中的运算可以在使用32位和/或64位整数算法的计算机处理器上特别磁共振成像(MRI)、超声(US)、正电子发射断层扫描(PET)、单光子发射计算机断层扫描经网络的一方可能会或可能不会以明文方式访问神经网络的训练参数，例如权重和偏差。经网络的效率和/或减少了所用密文或密钥材[0039]图1a示意性地示出了用于执行加密计算和/或计算密文的表示的设备的实施方案s'=(S',…,S)eBW[X]'K,其中B={0,1}并且BW[X]=B[X]/(X"+1).在更一般的情况下，可以在对于环R的R[X]/(p(X))上对密钥s′进行采样，例如参见欧洲专利申请供零的加密作为公钥(例如，加密密钥)，例如使用R.Rothblum的技术，“Homomorphic题的加密难度的意义而言。特殊情况k＝1(例如使用一个掩码多项式)也称为环容错学习明文ueTwn[x]的密文可以包括来自多项式环的k+1个元素(例如k个掩码多项式和一个确地说，Tg[X]/(P(X))的掩码和主体元素可以与来自R[X]/(p(X))的被乘数多项式相乘，环面的元素与对应环R=Z/qz的元素识别出来，这些乘法对应于环R[X]/(p(X))的元1)=zwg[X]=(Z/qz)[X]/(X"+1)以及J[X]/(X"+1)=Twq[X].对于如果f"eTwq[x]并且gEzwq[x],(外部)乘积可以通过令h=fgEzwq[x],其中其中fezwq[x],以及令来限定。因[0059]离散环面经常用于所谓的TFHE类方案，这些方案意指支持可编程自举运算的方案。在这种方案中，可以对基于LWE的密文，例如其中掩码和主体多项式是标量值的基于的密文，如其他地方所描述的。这种可编程自举theconcretehardnessofLearningwithErrors”，JournalofMathematical[0063]在本文的实施方案中，所使用的TFHE类基于LWE和GLWE的密文的参数可以基于期样的密文执行加密计算的设备110的实施方案的实密文可以包括一个或多个随机掩码多项式，以及由掩码多项式和明文导出的主体多项式。密文可以以伪随机数生成器的种子和主体多项式的傅里叶域表示的形式存储在存储器140输出设备和/或一个或多个传感器进行通信。该计算机网络可以是互联网、内联网、LAN、理器系统130可以进一步被配置为根据种子使用伪随机数生成器随机生成掩码多项式，以生成掩码多项式在数论变换的傅里叶域中的表示。处理器系统130可以进一步被配置为将数论变换的逆应用于掩码多项式的估值以确定掩码多项式的系数。处理器系统130可以进下，处理器系统130可以被配置为获得用于与掩码多项式和主体多项式相乘的相应被乘数多项式在傅里叶域中的表示。处理器系统130可以进一步被配置为计算掩码多项式和主体计算的多项式积在傅里叶域中表示。处理器系统130可以进一步被配置为输出计算的的多行计算的大部分或全部数据项用设备110未知的一个密钥(或多个密钥)加密——即设备110可以不被配置为获得与加密数据项(例如，存储在存储器140中)相对应的明文数据项。明文形式的解密密钥对于设备110来说是秘密的，尽管加密/解密密钥可以以加密形式可[0076]此实施例中的系统100包括密钥生成设备111、数据提供商设备160和加密计算设密数据项转换为明文格式的数据的情况下)对加的密钥生成单元131。密钥生成单元131被配置为生成由加密计算设备112使用的自举密钥密钥156的基于GLWE的密文的掩码和主体多项式与相应被乘数多项式相乘。加密计算单元[0080]尽管此图中未示出，但是加密计算系统100可以包括多个加密计算设备，例如两此之间交换中间计算结果(通常被加密)。每个击者能够确定进出一个或多个加密计算设备112的数据内容，或者甚至获得对这些设备的将同态加密运算应用于池中的一个、两个或更多个加密数据项，例如输入值和/或中间值个加密数据项上执行的指示的列表。网络或电路可以向加密计算设备112指示何时进行可编程自举，或者加密计算设备112可以在发现加密值的噪声过大或将变得过大时启动可编式的系数表示241与傅里叶表示242之间存在一一对应关系，但这不是必须的，例如，NTT233可以将系数的集合映射到可能的傅里叶表示242的子乘积。这通常被实现为多项式的估值的逐点乘法。逐点乘法可以对应于对于值n按多项式p(X)取模的给定多项式245的傅里叶域表示246的数目对于每个多项式245ω[0101]其中*表示多项式卷积，·表示向量的逐点乘法，参见“ModernComputerω是，对于任何阶数<M的多项式h∈R[X]都[0109]_如在上述实施例中那样执行Mul238，计算h/fg(modXM_1)的傅里叶表示为ω[0110]_通过如上计算h/的系数表示以及将h＝h/modp作为R[X]/(p)中f和g的乘积返回可以将p(X)＝XM_1视为这种情况的示与按p(X)取模的多项式之间不存在一一映射。然而有趣的是，INTT234中的运算h＝h/modp可以保证按p(X)取模的多项式的每个系数表示245都有相等数目的傅里叶域表示246X)N+1＝_XN+[0118]f"(x)mod(XM-1)=f,+f1wx+…+fw-1w"-1x"-1=fjx[0120]类似地，g'(x)mod(x"-1)=⃞gjx,其中gf=g,wleR.可以注意到ηη*))ηη[0123]令h(x)=hjx9则乘积多项式hfg∈R[X]/(XN+1)由ηηηη[0132]给定f,g∈R[X]/(XN+XN/2+1)，编写f(X)=冶fjx,其中fj∈R，以及g(x)=g;x,其中gj∈R.对于i∈{1,2}，定义f⃞(x)=f(w'x)和并且成立g(x)mod(x"I"-1)=其中可以计算为[0140]其中应用中国余数定理可以得[0148]图3a示意性地示出了用于通过加密给定的明文来计算密文的表示344_345的加密多项式的系数343，使得由掩码多项式341和主体多项式343形成的密文对明文347进行加随机生成掩码多项式的相应系数相同的随机性特性的掩码多项式，如可以常规进行的那[0155]该图还示出了NTT单元333。NTT单元333可以被配置为将数论变换(NTT)应用于主体多项式的系数343以确定主体多项式在傅里叶域中的表示344，例如，如关于图2所讨论随机种子来初始化PRNG335一次，然后可以使用PRNG基于相同的种子345生成相应密文的[0157]现在给出了确定表示344_345的许多详细实施例。这些实施例描述了表示自举密[0162]下面示出了如何可以使用加密单元331来生成TFHE可编程自举的自举密钥。这种自举密钥可以包括密钥的多个部分的GGSW类型密文。GGSW类型密文本身可以由以(i,r)为[0167]以获得对于1≤i≤n以及1srs(k+1)l,n(k+1)l向量342[0170]4.对于1≤i≤n以及1≤r≤(k+1)l:1);(其中1≤i≤n且1≤r≤(k+1)l))，344。式在TW[X]=(q-1Z/Z)[X]/(X"+X"/2+1)上定义，或者使用相关环在(Z/qz)[X]/(X"+X"/2+1)上定义。令R=Z[0177]使用该商多项式的一个优点是它可以与q的偶数值组合使用，特别是当q是2的幂[0184]获得对于1≤i≤n以及1≤r≤(k+1)l形式为[0185]4.对于1≤i≤n以及1≤r≤(k+1)l:[0190]5.通过种子和主体多项式的傅里叶域表示返回自举密钥所述自举密钥包括相应密文的表示σ,Bt7)(其中1≤i≤n以及1≤r≤(k+1)l)，344_域中或在应用NTT之后的傅立叶域中将p(X)的随机倍数添加到b(X)将所获得的傅立叶域表[0194]图3b示意性地示出了加密乘法单元332(例如用于加密计算设备110的加密乘法单[0195]加密乘法单元332可以作用于包括一个或多个随机掩码多项式以及由掩码多项式乘法单元332可以作用于以伪随机数生成器的种子345和数论变换的傅里叶域中的主体多[0196]加密乘法单元332可以用于将密文的掩码多项式和主体多项式与相应的被乘数多密文的掩码多项式和主体多项式相乘的相应被乘数多项式351。例如，相应被乘数多项式[0197]在图中所示的实施例中，以系数表示351获得被乘数多项式，并且数论变换单元元338可用于在傅里叶域中计算掩码多项式342和主体多项式344与相应被乘数多项式352商多项式p(X)|XM_1时，可以通过将商多项式p(X)的随机倍数r出系数域表示353，所述系数域表示不是按p(X)取模进行约简并且因此由按模数XM_1取模[0203]加密乘法单元332可用于对同一加密344_345重复执行多项式乘法。在这种情况除掩码多项式的傅里叶域表示342并根据需[0204]图4a示意性地示出了加密乘法单元432(例如用于加密计算设备110的加密乘法单[0205]一般来说，对明文M(X)进行加密的GGSW类型密文456可以包括相应的基于GLWE的[0208]参见I.CHillotti等人的“CONCRETE:ConcreteOperatesoNCiphertextsRapidlybyExtendingTfhE”(在/wp_content/uploads/2020/12/wahc20_demo_damien.其中阵。整数B≥2是一个系统参数，使得例如B'Iq,或者更一般地，B'sq.在此实施例中，[0214]为TGGSW密文。令表示在C中行#r中0的TGLWE加密。编写r=b+(h-1)l,其中1sb=b(r)≤l且1≤hh(r)≤k+1且h(r)=(r-b(r)+l)/l),C的行#r可被描述为[0220]图中示出了GGSW类型密文的表示456。GGSW类型密文的基于GLWE的密文可以由伪随机数生成器(PRNG)的相应种子445和数论变换的傅里叶域中的主体多项式的表示444来应基于GLWE的密文444的掩码多项式和主体多项式乘以基于GLWE的被乘数密文455的相应这种情况下，通过确定基于GLWE的被乘数密文455的所谓小工具分解GDec,439来获得被乘455的掩码多项式a1被基数分解为多项式A1,1,…,A1,e;主体多项式b被基数分解为多项式乘数多项式452的1X(K+1)f大小的向量与表示GGSW类型密文456的多项式442、444的(k+1)lx(k+1)大小的矩阵的矩阵一向量乘法。[0225]在此实施例中，给定基于GLWE的加密444的掩码多项式和主体多项式都乘以被乘[0226]乘法438可产生以傅里叶域表示的基于GLWE的密文454的掩码多项式和主体多项该乘积也称为外积。加密可以任选地由应用数论变换的逆的INTT单元434转换为系数形式[0228]另一个重要应用是计算加密的CMux门，也称为受控选择器门或受控多路复用通过计算GGSW类型密文与第一GLWE密文和第二GLWE密文之间的差的乘积并将第一GLWE密使用包括GGSW类型密文456的自举密钥。由于自举密钥通常包含许多此类外积中使用的自举可以通过计算TGGSW加密的外积来评估加密条件下使用此密钥的解密函数。这例如在“ProgrammableBootstrappingEnablesEfficientHomomorphicInferenceofDeep如果S=(S1,…,sn)EB"表示私有TLWE密钥，自举密钥可以包括加密：[0232]基于上面的自举密钥，将说明由于GGSW类型密文的压缩表示456而改进的存储和[0234]位用于进行存储和传输。典型参数是n＝630，f=3,k＝1，N＝1024以及q＝264。k+1个元素：(例如从Twa[x]中)均匀随机抽取的k个掩码多项[0239]因此，使用相同的种子σ,445来生成形成n个自举密钥的n·(K+1)l个TGLWE密文[0240]l+nl(k+1)NIlogzql(2)[0241]位表示，初始内存要求大致除以因子(k+1)。利用上面的实施例参数n＝630，兆字节。[0242]图4b示意性地示出了自举单元460(例如用于加密计算设备110的自举单元460)的加密将函数应用于输入加密461的结果。这种可编程自举例如从“Programmablebootstrappingenablesefficienthomomorphicinferenceofdeepneural入加密461的解密密钥的位或其他部分的加密)与基于输入加密461的基于GLWE的被乘数密盲旋转464的受控多路复用器的一部分来计算外积，以使用自举密钥456的LWE解密密钥的位的GGSW加密不经意地选择基于GLWE的密文用于LWE解密密钥的零位，或基于GLWE的密文分可以经过形式为I2N(-modq)/ql的运算，其中输入密文461按q取模定义。在这种情况以获得GLWE加密465，其将可编程自举的结果作为固定系数的值。可以获得样本提取运算[0248]“Programmablebootstrappingenablesefficienthomomorphicinference术，该申请由ZamaSAS于2021年12月7日提交，标题为“ENCRYPTEDCOMPUTATIONpolynomial4.Otherquotientpolynomials/coefficient”(通过引用纳入)中讨论的那这也在上面的参考在部分“Exampletestpolynomial1:fixedcoefficientisconstantcoefficient”和“Exampletestpolynomial2:fixedcoefficientisleadingcoefficient”(通过引用纳入[0251]在商多项