不可区分混淆的回顾与展望_郁昱.pdf

书书书第 21 卷第 4 期2022 年12 月广州大学学报(自然科学版)Journal of Guangzhou University(Natural Science Edition)Vol 21No 4Dec2022收稿日期:2022-09-30;修回日期:2022-11-07作者简介:郁昱(1981)，男，教授 E-mail:yyuu sjtu edu cn引文格式:郁昱，姚立 不可区分混淆的回顾与展望 J 广州大学学报(自然科学版)，2022，21(4):1-11文章编号:1671-4229(2022)04-0001-11不可区分混淆的回顾与展望郁昱1，2，姚立1(1 上海交通大学 计算机科学与工程系，上海200240;2 上海期智研究院，上海200232)摘要:不可区分混淆是密码学中一个功能非常强大的原语，它可以实现在一个可运行的程序中隐藏某些信息。尽管研究者们在过去十年间已经展示了如何在不可区分混淆的基础上实现各种密码学应用，然而距离基于标准假设的高效不可区分混淆方案仍有很长一段路要走。事实上，已经有很多工作提出了多种不可区分混淆的候选方案或是对这些方案进行了密码分析。不可区分混淆相关技术的发展大致经历了以下 4 个阶段:最初，需要假设多项式阶多线性映射，这是一类非标准的假设;接着，试图降低多线性映射的阶数使之接近并达到标准假设的要求;如今，正试图构造后量子安全的不可区分混淆;未来，将会在效率上改进不可区分混淆，使之能够被应用在一般化的场景中。关键词:不可区分混淆;多线性映射;后量子安全中图分类号:TP 301.6文献标志码:AIndistinguishability obfuscation:etrospect and prospectYU Yu1，2，YAO Li1(1 Department of Computer Science and Engineering，Shanghai Jiao Tong University，Shanghai 200240，China;2 Shanghai Qi Zhi Institute，Shanghai 200232，China)Abstract:Indistinguishability Obfuscation(iO)is an extremely powerful primitive which allows arunnable program to hide some information Although researchers have shown how to base crypto-graphic applications on iO over the last decade，we are still far away from the goal of basing efficientiO on standard assumptions In fact，many works have proposed various candidates or made cryptanal-ysis on these candidates The state of art of iO has experienced roughly the following four stages:Atthe beginning，we need to assume multi-linear map with polynomial degree，a non-standard assump-tion Then we try to decrease the degree to more closely to and finally fit the standard assumptionNow，we are trying to construct post-quantum secure iO In the future，we will improve the efficiencyof iO so that it can be applied in general scenariosKey words:indistinguishability obfuscation;multi-linear map;post-quantum secure1程序混淆一个程序代码中有代码的框架结构、组件间的调用关系和算法思想等信息，有时还包含一些硬编码的字符，这些硬编码的字符或算法都可以被看作程序中隐藏的一些秘密信息。显然，软件行业往往并不希望软件中的算法随着软件的售卖而被泄露，也不希望软件被任意修改(例如运用反编译等手段对付费软件进行破解)。程序混淆便可用于解决这一问题(也许有人声称一份写得极为糟糕的代码也能达到类似的效果，但这种做法的有效性无法被严格证明，同时也会增加软件产生 bug 的风险)。程序混淆(program obfuscation)保证了程序中确实能够隐藏某些秘密信息，即使是拥有这个程序并且能够广州大学学报(自然科学版)第 21 卷任意运行这个程序的人也无法得知这些秘密信息。1 1正确性实现程序混淆需要有程序混淆器(program obfusca-tor)。程序混淆器(记为 Obf)可以被视为一个特殊的编译器，这个编译器的输入(例如一段代码)对应于某个程序，将输入对应的这个程序记为 P，编译器将 P 编译后会输出一个混淆后的程序，记为P。那么要求:(1)这 2 个程序的功能完全一致;(2)从实用性的角度出发，Obf 和P 都应当是高效的。1 2安全性人们希望P 尽可能地隐藏 P 中包含的秘密信息。密码学常见的安全性刻画方式有 2 类:基于模拟的(SIM-based)和基于不可区分的(IND-based)，前者称为虚拟黑盒混淆(Virtual Black Box Obfuscation，VBBO)，后者称为不可区分混淆(Indistinguishability Obfuscation，iO)。121虚拟黑盒混淆虚拟黑盒混淆指对于一个得到了P 的学习者和一个只能对 P 进行黑盒访问的模拟器，二者的能力是完全一致的。换言之，得到P 并没有给学习者带来任何通过黑盒调用无法得到的信息(即使学习者可以研究P 的运算步骤，查看计算过程中某些变量值的变化，设置断点，甚至在运算进行过程中直接修改某些寄存器的值，并观察产生的影响)。虽然这个安全性定义非常强，但是事实上它是无法达成的。比如至少有一项能力是学习者有而模拟器没有的，那就是学习者可以输出一个和P 功能一致的程序(这个程序就是P)，而模拟器仅靠对P 进行的多项式次黑盒访问根本不可能写出一份和 P功能一致的代码。在 2001 年，Barak 等1 最早注意到这一点并证明了不存在通用的虚拟黑盒混淆(VBBO 和 iO的定义也是由他们在同一篇文章中提出的)。122不可区分混淆不可区分混淆指对于 2 个功能完全一致的程序 P1和 P2，任何区分器都无法区分P1和P2。这个安全性的定义直觉上并没有特别强(事实上即使 P=NP，iO 仍然能够存在，但这种情形下 iO 几乎隐藏不了什么信息)，2007 年，Goldwasser 等 2 证明了 iO 是有可能被实现的最好的混淆器。为了简述其思想，假设 VBBO 是可能存在的，并证明此时 iO 至少和 VBBO 一样安全。对于程序 P 和 VBBO(P)，显然这二者功能一样，于是，根据 iO的定义，任何多项式的敌手都无法区分 iO(P)和 iO(VB-BO(P)。VBBO(P)已经实现了虚拟黑盒安全，对其应用任何算法(包括 iO)都无法打破虚拟黑盒混淆的安全性，因此，iO(VBBO(P)也实现了虚拟黑盒混淆安全;同时，iO(P)与 O(VBBO(P)不可区分，因此，iO(P)自然也符合虚拟黑盒混淆的安全性定义。1 3应用由于通用 VBBO 的不可实现以及 iO 具有很强的安全性，目前，已有大量根据 iO 来构造密码学组件的研究成果，其中最早的是 Sahai 等 3 在 2014 年通过 iO 和一些基础的密码学假设(例如单向函数(one-way function)构造了公钥加密(public-key encryption)、数字签名(digitalsignature)和可否认加密(deniable encryption)等组件。综合这些研究成果可以看到，iO 不仅能用于构造已经熟知的经典密码学组件，更可以作为桥梁构造大量功能十分强大的“新”密码学组件(其中一部分组件目前只能基于 iO 构造)。1 4构造尽管在如何应用 iO 方面已经有了很多可喜的研究成果，但至今仍无法构造出安全且高效的 iO。这并不意味着研究者止步不前，事实上，自 2013 年 Garg 等 4 提出第一个 iO 的候选方案以来，iO 的构造方案已经经历了多次演进。本文将这些年来 iO 构造的发展历程大致分为 4 个阶段，并选取有代表性以及突破性的工作逐一进行介绍。2第一代 iO:基于多项式阶多线性映射自 2013 年起，有一系列工作基于多线性映射构造iO。相比于接下来的几代 iO 构造，第一代 iO 的构造非常直接高效，且易于理解。但由于多线性映射候选方案在安全性方面的缺失，从第一个 iO 候选方案 4被提出算起，这些方案已经经历了多轮攻击与修补5 10。时至今日，针对第一个 iO 候选方案的某些变体方案仍然没有提出有效的攻击，与此同时，也没有人能够用数学工具来证明这些变体的安全性，除非借助于一些非常强的理想化模型。2 1多线性映射代数群是密码学中常用的经典结构，SA 公钥加密及 DH 密钥交换等算法都运用了代数群以及群相关的困难假设。由于离散对数假设的存在，可以粗略地将 ga视为 a 在群 G 上的编码，而代数群的一个特点便是加法同态性，即 gagb=ga+b，这也意味着可以利用代数群的结构安全地进行加法计算。由于环上的任意计算都可以分解为加法和乘法，因此，如果能够进一步找到一类特殊的环，使得乘法同态也一并满足，那么这一代数结构将在密码学中具有极其广泛的应用。2第 4 期郁昱等:不可区分混淆的回顾与展望在研究中，人们逐渐发现，在同一个环上实现加法和乘法同态是十分困难的，因此，线性映射的概念出现了。以 Miller 11提出的双线性映射为例，对于一个属于群 G1的元素 ga1，一个属于群 G2的元素 gb2和一个群GT，存在一个特殊的映射 G1 G2GT，当输入 ga1和 gb2，输出群 GT上的元素 gabT(G1和 G2可以是同一个群)。也就是说，双线性映射允许安全地计算一次乘法，但是乘法计算的结果被编码到了另一个群上。虽然 Miller 的这篇文章被计算机理论科学的顶级会议 STOC 以没有应用为由拒稿，此后一直未公开发表，但是在 20 年后，基于双线性映射的基于身份加密(Iden-tity Based Encryption，IBE)、基于属性加密(AttributeBased Encryption，ABE)和 BLS 短签名(BLS short signa-ture)等密码学原语相继发表，证明了双线性映射在密码学领域有着广泛的应用场景。类似的，可以定义 k 阶多线性映射 G1 G2 GkGT(G1，G2Gk可以是同一个群)。然而，当试图将双线性映射的构造推广到三阶时，得到的映射将不再是多项式时间可计算的12。这也说明，构造多线性映射需要新的技术和方法。2013 年，Garg 等13 提出了第一个多线性映射的备选方案，此后陆续有其他候选方案14 15 被提出。这些多线性映射的备选方案有着一些共同特点:(1)带噪声编码:同一个元素在同一个群上的编码很可能不相同，它们之间会相差一个较小的噪声。(2)零元素测试:由于同一个元素的编码往往不同，当它们相减时，会得到某一个而非唯一的零元素编码。因此，需要零元素测试算法来判断编码是否是零元素编码。(3)分级编码:并非是将 k 个元素一次性映射到GT，而是所有初始元素都位于 1 级，一个 m 级的 a 的编码 g