针对RIAC同态加密算法的攻击_刘易简.pdf
《针对RIAC同态加密算法的攻击_刘易简.pdf》由会员分享,可在线阅读,更多相关《针对RIAC同态加密算法的攻击_刘易简.pdf(14页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):433446密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618针对 RIAC 同态加密算法的攻击刘易简1,2,石 冰1,21.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 1000932.中国科学院大学 网络空间安全学院,北京 100049通信作者:刘易简,E-mail:摘要:RIAC(random iterative affine cipher)是一种具有加法同态性的加密算法,最初见诸于
2、 FATE、Fedlearn 等开源联邦学习框架中.RIAC 使用多个轮次模仿射密码嵌套进行加密,只需要模乘和模加运算,其性能比其他加法同态加密方案要高得多,但是 RIAC 的加密强度并不依赖任何困难性假设.本文研究了 RIAC 的安全性问题,提出了一种攻击,可以在已知几十组明文为 0 的密文的前提下,在数十秒内提取 RIAC 的私钥.讨论了几个在不改变 RIAC 结构的前提下可能进行的修复,但结果是这些修复均不能抵御所提攻击.根据此研究的安全通报,相关机构和开源组织已经在升级版本中删除了 RIAC 算法的相关内容.关键词:RIAC 算法;同态加密;联邦学习;格基规约攻击中图分类号:TP309
3、.7文献标识码:ADOI:10.13868/ki.jcr.000604中文引用格式:刘易简,石冰.针对 RIAC 同态加密算法的攻击J.密码学报,2023,10(2):433446.DOI:10.13868/ki.jcr.000604英文引用格式:LIU Y J,SHI B.An attack on RIAC homomorphic encryption algorithmJ.Journal ofCryptologic Research,2023,10(2):433446.DOI:10.13868/ki.jcr.000604An Attack on RIAC Homomorphic Encry
4、ption AlgorithmLIU Yi-Jian1,2,SHI Bing1,21.State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy ofSciences,Beijing 100093,China2.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,ChinaCorresponding author:LIU Yi-Jian,E-mail
5、:Abstract:Random iterative affine cipher(RIAC)is an encryption algorithm with additive homo-morphic property.The cipher was first seen in several open-source federated learning frameworks.RIAC uses a multi-round affine transform,the operation of RIAC only involves addition and multipli-cation over f
6、inite fields,it is far more efficient than other additive homomorphic encryption algorithms.However,the hardness of RIAC cannot be reduced to any hardness assumption.By doing a tailoredcryptanalysis on RIAC,this paper presents an attack that can extract the private key of RIAC in tensof seconds,assu
7、ming some encrypted zeroes are known to the attacker.Several possible defenses arediscussed,and it is concluded that RIAC cannot resist against the presented attack without modifyingthe affine structures.This study has affected some communities to upgrade their software by removingthe RIAC.收稿日期:2022
8、-03-03定稿日期:2022-09-26434Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023Key words:RIAC;homomorphic encryption;federated learning;lattice reduction1引言联邦学习这一概念最早由 Google 在 2016 年提出1,目的是基于分布式机器学习技术,在保证数据安全的基础上进行联合建模,使多个用户可以在不共享原始数据的情况下共同构建更好的机器学习模型.联邦学习方案虽然没有直接传输原始数据,但是会传输梯度,已经有一些工作证明这些梯度也可能会造
9、成隐私泄露2,3.为此,一些流行的联邦学习方案如文献 4 中使用了同态加密来保护传输的梯度,以提高方案的安全性.由于机器学习经常需要传输大量的数据,同态加密的性能成为决定联邦学习效率的关键因素之一.为了提高性能,文献 46 等多个联邦学习框架中使用了一种称为 RIAC(random iterative affinecipher)的同态加密算法.RIAC 使用多个轮次模仿射密码嵌套进行加密,因此具备加法同态性.RIAC 只需要模加和模乘运算,性能比其他加法同态加密方案要高得多,但是其加密强度并不依赖任何底层数学难题,因此并不具备可证明安全性,更无法达到语义安全.在分析其算法后,我们首先发现其中几
10、个默认设置参数明显存在问题,但即使更改了这些参数,结构本身仍然存在缺陷.我们提出了两种不同轮数的攻击,当轮数小于 5 时,发现可以利用格基规约寻找短向量,逐轮恢复私钥.这种攻击只需要公钥和少量的密文(4 轮大约需要 10 个).RIAC 在开源框架中的实现使用了 5 轮加密.这时如果可以得到一定量明文均为 0 的密文(实验中大概需要约 100 个)和少量明文非0 的密文(大概需要 10 个),那么就可以遍历某些特定的线性组合逐轮次恢复私钥.我们可以通过这两种攻击证明 RIAC 并不安全.2预备知识2.1RIACRIAC 是私钥加密算法,算法中提到的 Randbits 函数与 python 中的
11、“getrandbits”函数相同,可以通过给定的比特长度使用 MT19937 生成随机的比特串并转化为整数.2.1.1密钥生成参照文献 4 的源码,设置其默认参数为:t=5,bl=512,bh=1024.算法 1 RIAC 密钥生成算法Input:轮次数 t;最小模数的比特长度 bl;最大模数的比特长度 bhOutput:私钥 private_key,公钥 public_key1b=bl+(bhbl)kt1|k 0,1,t 1;2n=Randbits(bi)|bi b;3a=Randbits(bi r)|bi b,r (0,1);4g=Randbits(bh10),x=Randbits(16
12、0);5private_key=(a,g,x),public_key=n.2.1.2加密算法 2 RIAC 加密算法Input:私钥 a,x,g;公钥 n;编码后的明文 mOutput:密文 c1y=Randbits(160);2c0 y g mod n0;3c0 m+c0 x mod n0;4for i=0 to t 1 do5ci+1 ci aimod ni;6end7c=(c0,ct).刘易简 等:针对 RIAC 同态加密算法的攻击4352.1.3解密算法 3 RIAC 解密算法Input:私钥 a,x;公钥 n;密文 c0,ctOutput:编码后的明文 m1for i=t to 1
13、do2ci1 ci a1imod ni;3end4m=c0 c0 x mod n0.2.1.4同态加法算法 4 RIAC 同态加法Input:公钥 n;RIAC 轮数 t;密文一 c10,c1t;密文二 c20,c2t;密文一数乘次数 mt1;密文二数乘次数mt2;密文数乘系数 mult(默认为 223)Output:同态加法后密文 c30,c3t1ifmt1/=mt2then2c30(c10+c20)mult|mt1 mt2|mod nt1;3c3t(c1t+c2t)mult|mt1 mt2|mod nt14end5if mt1=mt2then6c30 c10+c20mod nt1;7c3t
14、 c1t+c2tmod nt18end2.1.5编码参照文献 4 的源码,设置其默认参数为:mult=2100,trans=0.算法 5 RIAC 编码算法Input:明文 m;乘法系数 mult;噪声因子 transOutput:编码后明文 m1m=mult (m+trans)2.1.6解码算法 6 RIAC 解码算法Input:编码后明文 m;乘法系数 mult;噪声系数 trans;噪声叠加的次数 multiplierOutput:明文 m1m=mmult multiplier trans2.2最短向量问题使得 s 和 t 为两个正整数,v0,v1,vt1 Rs为一个包含了 t 个线性无
15、关向量的集合,格 L 由这些向量张成,形如 L=t1i=0ivi|i Z.格基矩阵即为由向量 v0,v1,vt1 Rs构成的矩阵.在最短向量问题(SVP)中,需要在格 L 中找到一个最短的非零向量?0.在弱化一些的版本 SVP问题中,需要找到一个非零向量?i,其 2-范数至大不超过 N2(?0),1.在密码分析中,一些寻找方程小根的问题可以转化为 SVP 或 SVP.为此,我们总是需要求解 SVP,本文中使用了在多项式时间内得到较短格向量的 LLL 算法.定理 1(LLL 算法7)给定 t 个 Zs中的线性无关的向量 v0,v1,vt1,LLL 算法将找到这些向量所张成的格 L(v0,v1,v
16、t1)的一组新的基 v0,v1,vt1,并且这组基满足:|vj|2n(n1)/4(nj+1)det(L(v0,v1,vt1)1/(nj+1),1 j s,LLL 算法运行时间为多项式复杂度,由 s 和 v0,v1,vt1中元素的最长比特长度决定.知道了 LLL 算法可以寻找到短的格上向量,我们可以利用高斯启发式来估算格上最短向量的 2-范数,这可以帮助确定预期求得的向量是否会在 LLL 算法输出的向量中.436Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023定理 2(高斯启发式)高斯启发式 gh(L)为格 L 上最短向量的 2-
17、范数的估计.对于一个满秩格L Rs,其可以由公式给出:gh(L)=s2edet(L)1s,高斯启发式在随机格上更加精准.3格基规约攻击RIAC 的参数设置中存在一些明显的漏洞.虽然本节所述的攻击中利用了这些参数设置漏洞,但是在第5节中将会说明即使没有这些漏洞,RIAC 依然无法抵御所提的攻击.(1)私钥序列 ai 中元素的比特长度是随机的,有时候 ai可能会非常小以至于模数的存在没有了意义,比如会出现 c4=a3 c3 n3.我们可以通过计算最大公因数(GCD)来得到GCD(c30 a3,c31 a3,c3t a3)=GCD(c30,c31,c3t)a3,增加参与 GCD 计算的密文的数量,G
18、CD(c30,c31,c3t)可能为 1 或很小的正整数,这样就可以容易地得到 a3.(2)随机数 y 和 g 太小以至于存在 c0=y g n0,同样可以用上述的方法计算最大公因数,从而得到 g 和每一次加密中的 y.由于 RIAC 的多轮次加密结构,我们考虑逐轮次地恢复私钥.如果私钥有漏洞(1),那么我们可以直接获得轮次私钥.而如果私钥的比特长度不存在问题,注意到模数之间的比特长度差距很大,意味着 ni1相对于 ni小很多.这使得我们想到可能可以使用格基规约来解决问题,考虑到可以使用 ni大小相近的元素构建特定的格基矩阵,使得格上存在元素大小与 ni1相近的短向量.3.1基础攻击在基础攻击
19、中,我们主要关注于针对 4 轮及更低轮次的 RIAC 的攻击.3.1.1非首轮攻击这里以 4 轮的 RIAC 为例,参数设置为 bl=512,bh=1024,这样密文可以表示为 c0 yg mod n0,c4 a3c3mod n3.由于 c3 n2,则会存在 Ti满足 c4ia13+Tin3=c3 n2,我们可以利用模数之间的大小差距来攻击.使用 t 个密文来构建格 L0的格基矩阵 B0如下:B0=|n30.00n3.0.00.n3c40c41.c4t1|.格 L0上则会存在如下短向量:?v=(c30,c31,c3t1)=(T0,T1,Tt1,a13)B0(1)我们想要通过 LLL 算法得到?
20、v,那么需要确定上述短向量会是 LLL 输出中最短的非零向量.这里使用高斯启发式来估算最短格向量的 2-范数:gh(L0)=t+12edet(L0)1t+1.刘易简 等:针对 RIAC 同态加密算法的攻击437由于格基矩阵 B0并不满秩,只使用其线性无关的部分计算行列式:det(L0)=nt3,gh(L0)=t+12entt+13.我们希望预期向量为最短非零向量,所以向量?v需要满足|?v|gh(L0),max(?v)n2,|?v|tn2,这样条件就变为了tn2t+12entt+13.(2)使用 2854,21024来近似地估计 n2,n3,并将他们代入不等式(2)中:2ett+1 6,|?v
21、|gh(L0),这意味着?v很可能是 LLL 输出中的最短非零向量.在实验中,我们可以利用 7 个密文来稳定的恢复 a3.现在我们知道了可以通过少量密文来计算得到 a3,以此类推,可以恢复出私钥 a2,a1.在更低轮次时,对于密文数量的限制条件将会更加宽松.当恢复到第一轮时,我们得到了 c0=yg mod n0,c1=a0(m+ygx)mod n0.c0的比特长度并没有明显小于 n0的比特长度,故而上面所提到的格基规约攻击在这里无法实现.3.1.2首轮攻击如漏洞(2)所说,我们可以通过计算多个 c0的最大公因数来得到 g 和所有的 y,对于两个不同的密文c1i,c1j,可以计算得到 yj c1
22、i yi c1j=a0(yjmi yimj)mod n0,并且 yjmi yimj的比特长度非常小(小于 300).考虑到这个比特长度差距同样很大,我们可以继续使用 LLL 算法来进行格基规约.设 pi yic10 y0c1imod n0,由于明文均会被编码,mi=2100mi,pi(a0 2100)1 yjmiyimjmod n0 2200,于是可以通过构造格 L1的格基矩阵 B1如下:B1=|n00.00n0.0.00.n0p0p1.pt1|.那么格上会存在如下短向量:?v=(y1 m0 y0 m1,yt1 m0 y0 mt1)=(T0,T1,Tt1,(2100 a0)1)B1.如同上面给
23、出的格基规约攻击一样,这里也需要确认?v是 LLL 算法输出中的最短非零向量.我们仍然使用高斯启发式来估算格上最短向量的 2-范数:gh(L1)=t+12edet(L1)1t+1.格基矩阵 B1和矩阵 B0很相似,这里直接计算 det(L1)=nt0.在现实场景中,明文的大小都不大,这438Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023里假设 mi 240,那么则有 max(?v)max(y)max(m)2160+40,如果|?v|gh(L1),则应该满足:t2200t+12entt+10.(3)我们使用 2512来粗略地估计
24、 n0,并将其代入不等式(3):2ett+1 1 时,上述不等式成立,所以只需要至少两个密文即可获得预期向量?v.在获得了所有的yim0 y0mi之后,只需要找到一个 yi满足 yi y0,则有 m0=(yim0y0mi)mod yiy0,我们可以用这个方法获得所有的 mi和 x,之后就可以恢复出完整的私钥 ai,g,x.最终,我们通过基于格基规约的攻击只需要使用至少 7 个密文即可破解 4 轮的 RIAC 加密算法.3.2扩展攻击文献 4 中实际使用的轮数是 5,因此我们需要关注针对 5 轮及更高轮次的 RIAC 的攻击.由于RIAC 的线性结构,当轮次高于 4 时,模数之间的差距缩小,格
25、L0会产生很多 2-范数小于我们预期向量的短向量,所以在 5 轮等更高轮次的 RIAC 攻击中,无法使用之前的基础攻击方法.我们将利用实验数据进一步说明这一现象.表1通过多组实验取平均值展示了 5 轮 RIAC 中真实短向量和期望向量之间的差距(“期望向量”即为?v,“真实短向量”表示 LLL 输出中最短的非零向量,这里的 a3,a4与 n3,n4大小相同).表 1 5 轮 RIAC 中预期格最短向量Table 1Predicted norms of shortest vectors in 5-round RIAC明文比特长度密文数量平均预期短向量比特长度平均真实短向量比特长度02089685
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 针对 RIAC 同态 加密算法 攻击 刘易简
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。