可复用Garbling的注解.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(5):936943密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]可复用 Garbling 的注解*胡予濮,董思越,王保仓,刘 君西安电子科技大学 综合业务网理论与关键技术国家重点实验室,西安 710071通信作者:胡予濮,E-mail:摘要:Garbling 是一个有着多重应用的密码原语,主要适用于权力受限的场景,比如安全多方计算(MPC)、属性加密(ABE)、函数加密(FE)、不可区分混淆(IO)等等.2013 年以前的 garbling 方案都是一次性 garbling,GKP+13 和 Agr17 提出了可复用 garbling.我们曾经指出,可复用 garbling 并没有获得新的应用场景,它仍然是一个一次性 garbling.本文继续讨论可复用 garbling 的可用性和效率.本文指出以下两点:(1)即使可复用 garbling 被当作一次性 garbling 使用,也常常是不可用的,它只能用于两个基本场景中的基本场景二,不能用于基本场景一.比如,它不能用于安全多方计算(MPC).(2)即使可复用garbling 被当作一次性 garbling 用于基本场景二,没有证据表明它比原来的一次性 garbling 效率更高.关键词:garbling;函数加密(FE);全同态加密(FHE);属性加密(ABE)中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000637中文引用格式:胡予濮,董思越,王保仓,刘君.可复用 Garbling 的注解J.密码学报,2023,10(5):936943.DOI:10.13868/ki.jcr.000637英文引用格式:HU Y P,DONG S Y,WANG B C,LIU J.Notes on reusable garblingJ.Journal of CryptologicResearch,2023,10(5):936943.DOI:10.13868/ki.jcr.000637Notes on Reusable GarblingHU Yu-Pu,DONG Si-Yue,WANG Bao-Cang,LIU JunState Key Laboratory of Integrated Services Networks,Xidian University,Xian 710071,ChinaCorresponding author:HU Yu-Pu,E-mail:Abstract:Garbling is a cryptographic primitive with multiple applications.It is often used in sce-narios where the authority is limited,e.g.,secure multiparty computation,attribute-based encryption,functional encryption,indistinguishable obfuscation,etc.All garbling schemes proposed before 2013are one-time garbling.GKP+13 and Agr17 propose reusable garbling.The authors once pointed outthat reusable garbling does not acquire new application scenarios,which means that it is still one-timegarbling.This paper further discusses the validity of reusable garbling,which is concluded by thefollowing two points.(1)Even if reusable garbling is used as one-time garbling,it is often invalid.Reusable garbling can only be applied in the second fundamental scenario out of two fundamental*基金项目:国家重点研发计划(2017YFB0802000);国家自然科学基金(61972457,U19B2021);国家密码发展基金(MMJJ20170104,MMJJ20180111);陕西省重点研发计划(2020ZDLGY08-04)Foundation:National Key Research and Development Program of China(2017YFB0802000);National NaturalScience Foundation of China(61972457,U19B2021);National Cryptography Development Fund(MMJJ20170104,MMJJ20180111);Key Research and Development Program of Shaanxi Province(2020ZDLGY08-04)收稿日期:2022-09-20定稿日期:2022-11-15胡予濮 等:可复用 Garbling 的注解937scenarios,and cannot be applied in the first fundamental scenario.E.g.,it cannot be applied in securemultiparty computation.(2)Even if reusable garbling is applied in the second fundamental scenario,there is no proof that it is more efficient than the previous one-time garbling.Key words:garbling;functional encryption;fully homomorphic encryption;attribute-based encryp-tion1前言Garbling 是一个有着多重应用的密码原语.Garbling 主要适用于权力受限的场景,其中最早的应用是安全多方计算(MPC)1,2.随后出现的应用有属性加密(ABE)和函数加密(FE),有意思的是 garbling和 FE 常常互为底层结构3,4.Garbling 还被应用于不可区分混淆(indistinguishability obfuscation,IO)57.注意到 garbling 和 obfuscation 的中文翻译同为“混淆”,说明 garbling 和 IO 有相似的功能,但后者的定义更强大.1.1Garbling 的两个基本场景Garbling 的所有应用都源于以下两个基本场景,是这两个基本场景的组合或变形.基本场景一Alice 知道布尔电路 f 的值,Bob 知道布尔变量 x 的值.Alice 对 f 编码得到 f,并对变量域 X 的所有可能值编码得到 X(具体说就是,对 X=(X1,X2,Xn)的每个分量 Xi的两个可能值 0 和 1 分别编码得到 Xi,0和 Xi,1,因此变量域 X 的编码值为 X=(X1,0,X1,1,X2,0,X2,1,Xn,0,Xn,1).Alice 将 f 发给 Bob,并将 X 用“定向选择不经意传输”的方式发给 Bob(具体说就是,对每个分量 Xi的两个编码值 Xi,0和 Xi,1,Bob 能选择且仅能选择接收一个编码值).Bob 按照 x 的值从 X 中选择接收对应的那一部分码字 x.于是,“正确性”指的是 Bob 由(x,f)能正确计算 f(x)的值;“隐私性”指的是:(1)Alice 对 x 一无所知;(2)Bob 对 f 除 f(x)外一无所知.基本场景二Alice 知道布尔电路 f 和布尔变量 x 的值.Alice 对 f 编码得到 f,对 x 编码得到 x.Alice 将(x,f)发送给 Bob.于是,“正确性”指的是 Bob 由(x,f)能正确计算 f(x)的值;“隐私性”指的是 Bob 对(x,f)除了 f(x)外一无所知.关于上述两个基本场景,我们有以下三个注解.注解 1基本场景一中的“定向选择不经意传输”是容易实现的.注解 2基本场景一就是多方安全计算的底层结构.以用户 U1和用户 U2的两方安全计算为例,设用户 U1知道 x1,用户 U2知道 x2,双方都知道电路 C(,).双方希望共同计算 C(x1,x2)的值,但 U1需要隐藏 x1,U2需要隐藏 x2.于是,首先取 f()=C(x1,),U1和 U2在基本场景一中分别扮演 Alice 和Bob,使 U2获得 f(x2)=C(x1,x2).其次取 f()=C(,x2),U1和 U2位置互换,在基本场景一中分别扮演 Bob 和 Alice,使 U1获得 f(x1)=C(x1,x2).两次使用基本场景一,就使用户 U1和用户 U2都得到C(x1,x2)(正确性);但 U1不知道 x2,U2不知道 x1(隐私性).注解 3基本场景二不能成为多方安全计算的底层结构.这是因为在基本场景二中,一方拥有的知识包含了另一方拥有的知识,不符合多方安全计算的场景设置.1.2可复用 garbling 及我们以往的工作2013 年以前的 garbling 方案1,2,8,9都是一次性 garbling.即一次编码(基本场景一或基本场景二)只能计算一个 f 和一个 x 的组合值 f(x),否则将不能保证隐私性.Goldwasser 等人3和 Agrawal4提出了可复用 garbling 方案.从字面意思来理解,可复用 garbling 似乎满足以下标准:一次编码能计算一个f 和任意多个 x 的组合值 f(x),同时保证隐私性(如果是这样的话,可复用 garbling 就是 IO 了).然而我们10对可复用 garbling 的有效性进行了分析,指出它只达到了一个更弱的标准:对 f 的一次编码确实可以用来计算多个 x 的组合值 f(x),但对变量(值或域)的一次编码只能计算一个 x 的组合值 f(x).这就是说,可复用 garbling 实际上仍然是一个一次性 garbling.1.3本文的工作本文继续讨论可复用 garbling 的可用性和效率.本文指出以下两点:(1)即使可复用 garbling 被当作一次性 garbling 使用,也常常是不可用的,它只能用于两个基本场景中的基本场景二,不能用于基本场938Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023景一.结合本文前述的注解 3 可知,可复用 garbling 至少不能用于安全多方计算(MPC).(2)即使可复用 garbling 被当作一次性 garbling 用于基本场景二,没有证据表明它比原来的一次性 garbling 效率更高.本文工作的细节如下.为了说明第(1)点,本文首先指出对变量的编码并不是与 f 相互独立的,而是要用到 f 的信息.换句话说,对变量的编码可以看作对 f 的编码的另一部分.在此基础上,本文说明在可复用 garbling 方案中,要么 Alice 的知识包含 Bob 的知识,要么 Bob 的知识包含 Alice 的知识,因此不符合基本场景一的场景设置.为了说明第(2)点,我们仔细讨论可复用 garbling 的中层结构和底层结构(由于我们11已经指出 Agrawal 的中层结构/底层结构4不可用,因此只能讨论 Goldwasser 等人的中层结构/底层结构3).在此基础上,我们将可复用 garbling 方案与一个以前的一次性 garbling 方案9进行比较.我们说明,当前者不使用全同态加密技术中的自举(Bootstrapping)和降模(Modular switching)运算时,前者的计算复杂度远远高于后者的计算复杂度;当前者使用自举或降模运算时,两者的比较非常复杂,但没有迹象显示前者的计算复杂度更低.2BHR12:主流的一次性 garbling 方案2.1布尔电路的一般表达式布尔函数的一般表达式是按照运算顺序来表示每一步的 两个输入比特,运算符号,一个输出比特.设运算符号集为+,其中+”为比特异或,”为比特与,则 n 维布尔函数 f(x)的一般表达式如下.输入:x=(x1,x2,xn),xn+1.其中 xn+1=1 为常数.对于 i=n+2,n+3,N,令 xi xa(i)Oixb(i).其中 a(i)1,2,i 1,b(i)1,2,i 1,a(i)4N.理由如下.942Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023由于 f 作为布尔函数的电路尺寸为 N,且 D(,)的电路尺寸稍大于 N,因此 f作为布尔函数的电路尺寸稍大于 N+N.这就是说,f是顺序做大约 N+N个布尔运算.作为 f的密文同态函数,f应该是顺序做大约 N+N个模 q 运算,而且 f和 f的依次运算类型相互对应:一个比特异或对应一个模 q 加法运算,一个比特与运算对应一个模 q 乘法运算.现在我们考虑这些模 q 运算所造成的全同态密文噪声尺寸的累积.设原始噪声的平均尺寸为 e,考虑到全同态加密方案的安全性,一般取 e 为多项式大,因此设 log2e 8 是合理的.然后设 N+N个模 q 运算中有大约一半是模 q 加法运算,另一半是模 q 乘法运算.模 q 加法会使噪声尺寸增加,但影响不大,此处忽略.模 q 乘积的噪声尺寸是原来噪声尺寸的乘积,因此N+N2个模 q 乘法得到的噪声尺寸平均大约是 eN+N2.而在全同态加密方案中,防止解密出错的一个前提是 q 2 eN+N2.最后我们得到=log2q N+N2log2e 4(N+N)4N.第二个观察:当可复用 garbling 方案不使用全同态加密技术中的自举和降模运算时,可复用 garbling方案中的一个(属性加密,属性解密)的计算复杂度高于一个(E(,),D(,)的计算复杂度.理由如下.注意到 f=f1,f2,f.f中的一个布尔运算对应 f中的一个模 q 运算;而对于每个 i=1,2,f中的一个模 q 运算对应 fi的远远不止一个布尔运算.换句话说,每个 fi的电路尺寸都远远大于 f的电路尺寸,也就远远大于 N+N.另一方面,根据主流 KP-ABE 方案的结构13,14,对于布尔函数 fi中的每个布尔运算 O,ABE2,i的解密算法中总有一组对应操作 O,其中 O的计算复杂度远远超过两个布尔运算的计算复杂度.我们称 O为 O 的拟同态运算.综上所述,一个(属性加密,属性解密)的计算复杂度远远高于 2(N+N)个布尔运算,而一个(E(,),D(,)的计算复杂度稍高于 2N个布尔运算.5.3计算复杂度的比较:不使用自举和降模运算BHR12 方案的主要计算是大约 4N 个(E(,),D(,).可复用 garbling 的主要计算是 个(属性加密,属性解密),全同态加密方案的(密钥生成,同态运算),以及一个一次性 garbling(仍然是一个 BHR12方案).根据我们的两个观察(见5.2小节),可复用 garbling 的计算复杂度远远高于 BHR12 方案.5.4计算复杂度的比较:使用自举或降模运算当可复用 garbling 使用自举或降模运算时,密文同态运算函数就不是 f=f1,f2,f了,而是 f=f1,f2,f,其中=log2q,q是一个更小的模,q q.此时(属性加密,属性解密)所针对的函数是 fi,i=1 ,而不是 fi,i=1 .f比 f的分量布尔函数的个数少,因而(属性加密,属性解密)的个数少.但 f的分量布尔函数的电路尺寸更大,因而每个(属性加密,属性解密)的计算复杂度更大.综上所述,此时计算复杂度的比较非常复杂,但没有迹象显示 BHR12 方案比使用自举或降模运算的可复用 garbling 方案有更高的计算复杂度.参考文献1 YAO A C.Protocols for secure computations(extended abstract)C.In:Proceedings of the 23rd Annual Sympo-sium on Foundations of Computer Science(SFCS 1982).IEEE,1982:160164.DOI:10.1109/SFCS.1982.382 YAO A C.How to generate and exchange secrets(extended abstract)C.In:Proceedings of the 27th Annual Sym-posium on Foundations of Computer Science(SFCS 1986).IEEE,1986:162167.DOI:10.1109/SFCS.1986.253 GOLDWASSER S,KALAI Y,POPA R A,et al.Reusable garbled circuits and succinct functional encryptionC.In:Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing.ACM,2013:555564.DOI:10.1145/2488608.24886784 AGRAWAL S.Stronger security for reusable garbled circuits,general definitions and attacksC.In:Advances inCryptologyCRYPTO 2017,Part I.Springer Cham,2017:335.DOI:10.1007/978-3-319-63688-7_15 GENTRY C,GORBUNOV S,HALEVI S,et al.How to compress(reusable)garbled circuitsJ/OL.IACRCryptology ePrint Archive,2013:2013/687.https:/eprint.iacr.org/2013/687.pdf胡予濮 等:可复用 Garbling 的注解9436 LIN H J.Indistinguishability obfuscation from constant-degree graded encoding schemesC.In:Advances inCryptologyEUROCRYPT 2016,Part I.Springer Berlin Heidelberg,2016:2857.DOI:10.1007/978-3-662-49890-3_27 LIN H J.Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGsC.In:Advances inCryptologyCRYPTO 2017,Part I.Springer Cham,2017:599629.DOI:10.1007/978-3-319-63688-7_208 ISHAI Y,KUSHILEVITZ E.Randomizing polynomials:A new representation with applications to round-efficientsecure computationC.In:Proceedings of the 41st Annual Symposium on Foundations of Computer Science(SFCS 2000).IEEE,2000:294304.DOI:10.1109/SFCS.2000.8921189 BELLARE M,HOANG V T,ROGAWAY P.Foundations of garbled circuitsC.In:Proceedings of the 2012 ACMConference on Computer and Communications Security.ACM,2012:784796.DOI:10.1145/2382196.238227910 HU Y P,LIU J,WANG B C.Efficiency analysis and simplified scheme of reusable garblingJ.Journal of Cryp-tologic Research,2022,9(1):106112.DOI:10.13868/ki.jcr.000506胡予濮,刘君,王保仓.可复用 Garbling 的效率分析及简化方案 J.密码学报,2022,9(1):106112.DOI:10.13868/ki.jcr.00050611 HU Y P,LIU J,WANG B C,et al.P/poly invalidity of the Agr17 functional encryption schemeJ/OL.IACRCryptology ePrint Archive,2021:2021/1442.https:/eprint.iacr.org/2021/1442.pdf12 GOLDWASSER S,GORDON S D,GOYAL V,et al.Multi-input Functional EncryptionC.In:Advances inCryptologyEUROCRYPT 2014.Springer Berlin Heidelberg,2014:578602.DOI:10.1007/978-3-642-55220-5_3213 GORBUNOV S,VAIKUNTANATHAN V,WEE H.Attribute based encryption for circuitsC.In:Proceedingsof the 45th Annual ACM Symposium on Theory of Computing(STOC 2013).ACM,2013:545554.DOI:10.1145/2488608.248867714 BONEH D,GENTRY C,GORBUNOV S,et al.Fully key-homomorphic encryption,arithmetic circuit ABE,andcompact garbled circuitsC.In:Advances in CryptologyEUROCRYPT 2014.Springer Berlin Heidelberg,2014:533556.DOI:10.1007/978-3-642-55220-5_30作者信息胡予濮(1955),河南濮阳人,教授.主要研究领域为密码算法的安全性分析董思越(1990),陕西渭南人,博士研究生.主要研究领域为格基密码的应用与分析王保仓(1979),河南郸城人,教授.主要研究领域为公钥密码学刘君(1993),陕西宝鸡人,博士研究生.主要研究领域为混淆和白盒密码