不可区分混淆的回顾与展望
郁 昱,姚 立
(1. 上海交通大学 计算机科学与工程系，上海 200240；
2. 上海期智研究院，上海 200232)
一个程序代码中有代码的框架结构、组件间的调用关系和算法思想等信息，有时还包含一些硬编码的字符，这些硬编码的字符或算法都可以被看作程序中隐藏的一些秘密信息。显然，软件行业往往并不希望软件中的算法随着软件的售卖而被泄露，也不希望软件被任意修改(例如运用反编译等手段对付费软件进行破解)。程序混淆便可用于解决这一问题(也许有人声称一份写得极为糟糕的代码也能达到类似的效果，但这种做法的有效性无法被严格证明，同时也会增加软件产生bug的风险)。
程序混淆(program obfuscation)保证了程序中确实能够隐藏某些秘密信息，即使是拥有这个程序并且能够任意运行这个程序的人也无法得知这些秘密信息。
1.1 正确性
实现程序混淆需要有程序混淆器(program obfuscator)。程序混淆器(记为Obf)可以被视为一个特殊的编译器，这个编译器的输入(例如一段代码)对应于某个程序，将输入对应的这个程序记为P，编译器将P编译后会输出一个混淆后的程序，记为。那么要求：
(1)这2个程序的功能完全一致;
(2)从实用性的角度出发，Obf和都应当是高效的。
1.2 安全性
1.2.1 虚拟黑盒混淆
1.2.2 不可区分混淆
不可区分混淆指对于2个功能完全一致的程序P1和P2，任何区分器都无法区分1和2。这个安全性的定义直觉上并没有特别强(事实上即使P=NP，iO 仍然能够存在，但这种情形下 iO 几乎隐藏不了什么信息)，2007年，Goldwasser 等[2]证明了iO 是有可能被实现的最好的混淆器。为了简述其思想，假设 VBBO 是可能存在的，并证明此时 iO 至少和 VBBO 一样安全。对于程序P和VBBO(P)，显然这二者功能一样，于是，根据 iO 的定义，任何多项式的敌手都无法区分iO(P)和iO(VBBO(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)、数字签名(digital signature)和可否认加密(deniable encryption)等组件。
综合这些研究成果可以看到，iO 不仅能用于构造已经熟知的经典密码学组件，更可以作为桥梁构造大量功能十分强大的“新”密码学组件(其中一部分组件目前只能基于 iO 构造)。
1.4 构造
尽管在如何应用iO方面已经有了很多可喜的研究成果，但至今仍无法构造出安全且高效的iO。这并不意味着研究者止步不前，事实上，自2013年Garg等[4]提出第一个iO的候选方案以来，iO的构造方案已经经历了多次演进。本文将这些年来iO构造的发展历程大致分为4个阶段，并选取有代表性以及突破性的工作逐一进行介绍。
自2013年起，有一系列工作基于多线性映射构造iO。相比于接下来的几代iO构造，第一代iO的构造非常直接高效，且易于理解。但由于多线性映射候选方案在安全性方面的缺失，从第一个iO候选方案[4]被提出算起，这些方案已经经历了多轮攻击与修补[5-10]。时至今日，针对第一个iO候选方案的某些变体方案仍然没有提出有效的攻击，与此同时，也没有人能够用数学工具来证明这些变体的安全性，除非借助于一些非常强的理想化模型。
2.1 多线性映射
代数群是密码学中常用的经典结构，RSA公钥加密及DH密钥交换等算法都运用了代数群以及群相关的困难假设。由于离散对数假设的存在，可以粗略地将ga视为a在群G上的编码，而代数群的一个特点便是加法同态性，即ga·gb=ga+b，这也意味着可以利用代数群的结构安全地进行加法计算。由于环上的任意计算都可以分解为加法和乘法，因此，如果能够进一步找到一类特殊的环，使得乘法同态也一并满足，那么这一代数结构将在密码学中具有极其广泛的应用。
虽然Miller的这篇文章被计算机理论科学的顶级会议STOC以没有应用为由拒稿，此后一直未公开发表，但是在20年后，基于双线性映射的基于身份加密(Identity Based Encryption,IBE)、基于属性加密(Attribute Based Encryption,ABE)和BLS 短签名(BLS short signature)等密码学原语相继发表，证明了双线性映射在密码学领域有着广泛的应用场景。
类似的，可以定义k阶多线性映射G1×G2×…×Gk→GT(G1,G2…Gk可以是同一个群)。然而，当试图将双线性映射的构造推广到三阶时，得到的映射将不再是多项式时间可计算的[12]。这也说明，构造多线性映射需要新的技术和方法。
2013年，Garg等[13]提出了第一个多线性映射的备选方案，此后陆续有其他候选方案[14-15]被提出。这些多线性映射的备选方案有着一些共同特点：
(1)带噪声编码：同一个元素在同一个群上的编码很可能不相同，它们之间会相差一个较小的噪声。
(2)零元素测试：由于同一个元素的编码往往不同，当它们相减时，会得到某一个而非唯一的零元素编码。因此，需要零元素测试算法来判断编码是否是零元素编码。
(4)无法维持经典假设：在这些多线性映射群上，经典的假设(双线性映射群上常见假设的推广)，例如判定性线性(Decisional Linear,DLIN)假设等均不成立。
2.2 用于对数深度电路的iO
有了多线性映射，便可以着手进行iO的构造了。下面介绍最经典的构造，同时也是第一个iO候选方案[4]。这一方案首先构造了只能用于对数深度电路的iO，之后利用自举技术将其适用性拓展为所有多项式大小的电路。尽管这一方案在理想的多线性映射代数系统中是可证明安全的，由于目前已有的多线性映射候选方案均无法维持经典假设，因此，这一类方案整体的安全性至今无法在标准模型中得到证明。
2.2.1 分支程序
早在1986年，Barrington[16]就证明了任意一个NC1的电路可以被表示为宽度为5的多项式大小的分支程序。这意味着一个NC1电路的计算可以被表示为多项式个五维矩阵的乘积，其中的每个矩阵都是从一对矩阵中依据某个输入位的值选取的。例如对于一对矩阵(A1，A2)，其关联的输入位为xi，那么有一种可能的情况：如果xi为0，就选取A2，否则，选取A1。需要注意的是，一个输入位可能会多次决定矩阵的选取。
2.2.2 类拼图游戏
多线性映射允许计算多项式个矩阵的乘积，但是却无法保证攻击者能够诚实地选取这些矩阵并诚实地进行运算。例如如果xi为0，应选取A2和B1参与运算，反之选取A1和B2参与运算，而敌手可能会选取A1和B1参与运算，这无疑会得到除电路正常输出以外的信息，从而利用这一信息打破iO(iO的安全定义中要求2个程序的功能完全一样，这也意味着往往只有正常的电路输出才能保证不会泄露信息)。再比如，程序正常计算时，应该是C1/C2乘以D1/D2，而敌手可能会计算D1乘以C1，从而得到额外的信息(矩阵乘法不满足交换律)。因此，仿照拼图游戏去设计一些算法来避免这一点，例如针对第一种情况，可以把A2和B1设计为一块拼图，只能同时选或同时不选；
针对第二种情况，可以让C1/C2这2块拼图右侧的锯齿和D1/D2这2块拼图左侧的锯齿相吻合，这样只有将C1/C2放在D1/D2左侧才能使得拼图呈现吻合的状态。在密码学中，这类操作通常通过添加噪声来实现，当程序按照预定的方式计算时，这些噪声的乘积刚好会相互抵消，得到正确的计算结果；
总之，这些噪声糅合在一起，将原本会被泄露的额外信息掩盖起来。同时，也需要给这些拼图添加一些随机性，例如当C1和C2完全一样时，它们的锯齿也会完全一样，那么此时会出现2块完全一样的拼图。而对于另一个功能一样的分支程序，可能不存在2块完全一样的拼图，这样敌手就可以轻易地区分这2个程序。所以，需要给拼图注入随机性，使得出现2块完全相同拼图的概率是可忽略的。
2.3 自举
自举(bootstrapping)技术最早出现在全同态加密(Fully Homomorphic Encryption,FHE)中，其核心思想是，当需要实现一个强大的功能时，也许只需要实现一个弱的版本，并利用这个弱的版本来构造出那个强大的功能。一个形象的例子是，当组装一个机器人时，只需组装出机器人的手，接下来便可以让机器人的手去组装机器人剩余的部分。为了实现iO的自举，还需要用到全同态加密和通用电路。
相比于通常的加密，全同态加密允许在不知道明文的情况下直接对密文进行操作。同时，全同态加密的解密函数较为简单，可以用一个NC1的电路表示。
通用电路(Universal Circuit,UC)可以用来模拟任意电路的计算过程，它将电路C的描述和电路C的输入作为输入，并得到电路C的输出。通用电路也可以交换电路C和电路C的输入立场，通过将电路C的输入硬编码在通用电路里，使UC(·,x)成为电路，而电路C的输入成为该电路的输入。
也就是说，要构造适用于所有多项式大小电路的iO，构造一个适用于NC1电路的iO就足够了。NC1的电路可以表示为多项式个矩阵的乘积，多项式个矩阵的乘积需要多项式次乘法运算，因此，可以通过多项式阶的多线性映射来完成这一任务。
目前，密码学标准假设中只有双线性映射，因此，自2015年起，有一系列工作[17-24]试图将iO规约到(相较于iO)稍弱的密码学组件中，从而最终只需要依赖三阶多线性映射，这与双线性映射已经十分接近了。
3.1 规约到亚线性简明随机化编码
随机化编码(Randomized Encoding,RE)可以用来保护一次计算，例如混淆电路(Garble Circuit,GC)就可以视为RE，它包含有2个算法：
函数加密是一类特殊的加密方式，不同于传统加密要么持有密钥得到全部的秘密，要么没有密钥从而对秘密一无所知的加密模式，FE存在有一个主密钥msk，通过主密钥可以派生与某个函数f相关的密钥skf，通过用该密钥对消息m的加密进行解密，可以得到f(m)。公钥FE(也可称作非对称FE或PKFE)包含4个算法：
(1)Setup(1λ)→(pk,msk):生成公钥和主密钥;
(3)KeyGen(msk,C)→skC:生成与电路C对应的解密密钥skC;
私钥FE(也可称作对称FE或SKFE)只需要将pk替换为msk，如果FE只支持执行一次KeyGen算法，则称该FE是 1-key FE；
如果支持执行任意次KeyGen算法，则称其为抗合谋(collusion-resistance) FE。如非特殊说明，FE指PKFE。
那么通过GC，就可以实现iO了吗？答案是否定的，这是因为GC的Encode算法的时间复杂度是ploy(λ)·s，将这一算法用电路表示，电路大小也是ploy(λ)·s,而GGM树的倒数第二层需要输出2个上述的RE，因此，耗时至少是ploy(λ)2·s，以此类推，每一层电路的大小都会增大ploy(λ)倍，根节点计算RE的耗时是ploy(λ)n·s。如果给定电路C，计算根节点的RE并输出需要耗费指数大小的时间，则需要一个高效的RE。自2015年起的一些工作[17-19]证明了，当RE满足亚线性简明时，这一构造才是可用的。
3.2 规约到弱亚线性简明随机化编码
由于构造亚线性简明随机化编码过于困难，研究者们把目光暂时转向了当时已有的最高效的FE/RE，即Goldwasser等[25]提出的succinct 1-key FE，该构造基于带噪声学习(Learning with Errors,LWE)假设，试图通过利用这一构造进一步将iO规约到更弱的密码学原语上。
3.3 规约到指数iO
指数iO (Exponential iO,XiO)进一步放宽了iO的要求，iO(C)的输出长度应该是poly(λ,|C|)，而XiO则允许输出长度达到poly(λ,|C|)·2n(1-)，一个电路的真值表可以看作一个平凡的混淆，其输出长度至多为|C|·2n，因此，XiO仅仅要求我们能够做得比直接输出真值表好一点。同时注意到，这一定义并没有对XiO的运行时间做任何规定，也就是说XiO运行的时间可以达到指数大小，这也是它被命名为指数iO的原因。2016年，Lin等[20]将iO规约到了LWE+XiO，这是一个比较反直觉的结论，只要能够对将混淆程序的大小压缩为亚指数，就能够将其压缩为多项式。这一规约的过程便是通过succinct 1-key FE和XiO构造weakly sublinear compact 1-key FE。
由于succinctness意味着FE的加密只和输出长度有关，与电路大小无关，因此，当计算1比特输出时，加密的复杂度将是poly(λ,|x|)(因为密文需要包含消息x的信息，所以必定与消息长度和安全参数有关)。对于一个n′比特输出的电路，可以用n′个succinct 1-key FE 的实例分别计算C(x)的每个比特，即消息x分别用n′个FE实例加密，同时这n′个FE的实例各自生成一个密钥，对应于计算电路C各个输出位的电路。把这n′个FE的加密过程封装进同一个电路D，当输入i∈[n′]时，输出x被第i个FE的实例加密的密文。将XiO(D)作为weakly sublinear compact 1-key FE加密算法的输出，把n′个FE实例各自生成的密钥作为密钥生成算法的输出。由于D的输入总共有n′个，且n′一定不大于电路大小s，由XiO的定义，XiO(D)的输出长度为poly(λ,|D|)·s，由于电路D的功能是计算x经由某个succinct 1-key FE加密的密文，而succinct 1-key FE加密的复杂度将是poly(λ,|x|)，因此，XiO(D)的输出长度为poly(λ,|x|)·s，从而满足weakly sublinear compactness。
3.4 对指数iO作进一步规约
从XiO继续向下规约，有2条路线，分别基于函数编码(functional encoding)和弱亚线性简明单密钥对称函数加密(weakly sublinear compact 1-key SKFE)。
Functional encoding可以视为FE的弱化，它包含3个算法：
(2)Opening(C,x,r)→h:确定性算法，除了电路C，还会输入x和r，其中，r是Encode时用到的随机数，因此，该算法可以完全复现Encode的过程。输出一个解码提示hC。
可以将FE视为特殊的functional encoding。与FE相比，functional encoding弱在其提示hf可能与Encode过程绑定，即其不能支持解码任意编码，而只能用于解码与其输入对应的Encode(x;r)。因此，与1-key many-ciphertexts FE对应的，functional encoding类似于1-ciphertext many-keys FE，也就是多个解码提示可对应于某一个编码。
假设有一个电路D，它能输出电路完整的真值表:D(C)=C(0)‖C(1)‖…‖C(2n-1)，这个电路可以看作通用电路的变体，那么可以设XiO(C)=(,hD)。根据functional encoding的定义，只能得到真值表的信息。
为了解决这一问题，可以将真值表拆分成2n1份，每份包含2n2项，其中，n1+n2=n。那么，总共需要一个和2n1个解密提示，分别解密每一份子真值表。因此，提示的数量是与2n1线性相关，而||与电路的输出，即子真值表的大小2n2线性相关，由于这两者都小于2n，因此，XiO(C)=(,hD1,hD2,…,hD2n1)关于2n亚线性相关，即实现了压缩真值表的要求。
3.5 FE中的自举技术
(1)混淆电路可以对电路的每个门分别生成真值表的混淆，生成混淆电路的过程可以用一个NC0电路表示，且这个电路可以表示为|C|个子电路，每个子电路用于混淆一个门，而混淆一个门的复杂度是与电路C无关的，这一特性被称为可分解的(decomposable)。最初的这类自举方案中需要使用PRF(NC0上不存在)，研究者们只将支持多项式大小电路的FE规约到支持NC1电路的FE[26]，后来才注意到能用PRG代替PRF[27]。
(2)AIK RE是一个作用于分支程序的RE[28]，只能支持将NC1上的电路进行编码，生成AIK RE的过程同样可以用一个NC0的电路表示。不仅如此，AIK RE的每个输出比特至多只和输入x的某一个比特及用到的随机串r的某3个比特有关。
与此同时，Lin[23]基于常数阶多线性映射的SXDH假设构造出了支持NC0电路的SKFE，由于NC0电路的每个输出最多与c个输入相关(c是常数)，因此至多需要进行c次乘法计算，才可以利用c阶多线性映射。不仅如此，构造得到的FE还满足线性效率，即加密的时间复杂度随消息的长度|x|呈线性增长。这样，只需要用这一SKFE去加密RE的输入，似乎就可以构造得到用于任意多项式大小电路的SKFE。但是，RE的输入除了消息x，还需要使用随机串，随机串的大小与电路大小|C|是线性关系，无法实现sublinear compactness。为此，可以将加密的内容由随机串换成PRG的种子，并用PRG生成的伪随机串来代替随机串。为了实现 sublinear compactness，要求PRG的种子长度是输出长度的亚线性，即PRG的拉伸度(stretch)是n。目前，NC0上具有超线性stretch的PRG只有Goldreich[29]提出的候选方案，而无法规约到现有的其他标准假设，因此，iO的构造中将NC0上存在具有超线性stretch的PRG作为一个假设提出。需要注意的是，目前已经证明了NC0上存在具有超线性stretch的PRG的locality必须大于等于5[30]。由于PRG的种子被FE加密在密文里，而PRG的种子被使用2次以上会影响安全性，虽然Lin[23]构造的是collusion-resistance的SKFE，但是当其用于计算NC0上的RE.Encode(C,·)时，就退化成了1-key SKFE，好在1-key sublinear compact SKFE已经足以构造iO。
下面进一步分析上述方案具体需要用到多少阶的多线性映射。根据AIK RE的特性，每个输出位与1个输入位和3个随机串位有关，随机串又是由PRG生成的，且PRG的locality至少是5，即PRG每个输出位与5个输入种子位有关，则总共与1个输入位和15个输入种子位有关。由于在安全证明中，需要加入一些额外的行为，因此，还会引入一个额外的输入比特b。当b=0时，电路会正常计算RE.Encode(C,·)；
当b=1时，电路会进行一些其他计算，这个计算涉及的比特位少于计算RE.Encode(C,·)，且b=1这一情况只在安全证明中才会出现。上述方案每个输出位至多会用到17个输入位，即需要17阶多线性映射。
3.6 降低至三阶线性映射
为了进一步降低多线性映射的阶数，Lin[23]同时指出可以赋予PRG特定的结构，并利用预处理的方法。由于GC具有decomposable的特性，因此，可以将RE.Encode(C,·)的计算拆分为|C|个计算，每个计算混淆C的一个电路门，每个计算的电路大小及需要用到的随机串均为poly(λ)。之后再用AIK RE进一步Encode，则此时Encode过程只和一个电路门以及poly(λ)个随机数相关。可以使用poly(λ)个完全相同的子PRG来生成随机串，这些子PRG的输出长度为|C|，这poly(λ)个子PRG输出的第i个比特可以拼成长为poly(λ)的伪随机串，用于混淆C的第i个电路门。在这种结构下，第i个AIK RE使用的随机数是由这些子PRG的第i个比特的输出拼成的，又因为这些子PRG完全相同，因此，子PRG第i个比特的输出一定对应于某5个特定的输入位置。虽然最终一个输出位会关联15个PRG输入位，但这15个输入位只来自于5个输入位置，每个位置取3个输入位。有了这一结构，就可以将每个输入位置的输入提前相乘，而不是使用多线性映射的能力计算乘法。由于总共有poly(λ)个子PRG，因此，每个输入位置有poly(λ)个输入，从中任取3个(也可以不取)，总共情况不超过(1+poly(λ))3。仍然是关于λ的与|C|无关的多项式，从而不会影响sublinear compactness。由于每个位置的输入已经提前乘好，剩下的计算则是围绕这5个位置进行的，b和x也可以用类似的预处理技术，因此，五阶多线性映射就足够了。
Lin等[24]又在2017年进一步降低了多线性映射的阶数，由于NC0上存在具有超线性stretch的PRG的locality必须大于等于5，他们提出了一种新的PRG，即block-wise PRG，PRG的每个输出对应的输入可以来自于常数多个分块，每个分块含有log(λ)个比特，这样通过预处理，可以将分块内的乘法提前算好，总共2log( λ)种情况。由于每个分块都含有大量比特，这样似乎可以不受locality必须大于等于5的限制。最初，他们宣称block-wise PRG的每个输出可以只依赖2个block，因而可以将iO规约到双线性映射这一标准假设，但是随后攻击这类PRG的方法被提出[31]，他们只得宣称block-wise PRG的每个输出至少要依赖3个block，最终iO被规约到三阶线性映射，离标准假设的目标仍有一步之遥。
2015年，Gorbunov等[32]首次提出了部分隐藏(Partial Hiding,PH)的概念，并将其与FHE的部分解密结合，构造了谓词加密(Predicate Encryption,PE)。PE是ABE的升级版，可以隐藏属性attr的同时计算policy(attr)的值，从这个角度看，它也可以说是一个特殊的FE，对于构造FE有着借鉴意义。PH是指加密消息时，将消息分为2个部分，即公开部分P和秘密部分S，同时PHPE只支持对秘密部分S做一些轻量级的计算(内积计算)。可以将attr在同态加密下的密文作为公开信息，将同态加密的密钥作为秘密信息。由于同态加密的密文是公开信息，因此，可以对它进行同态计算，得到policy(attr)的加密，而同态加密的解密算法正是计算内积并通过模数运算去除噪声。如果只计算内积的话，会得到policy(attr)+noise，只计算内积也被称作部分解密。在PE特殊的安全定义下，这个噪声的泄露将不会影响安全性。
运用类似的思想，Jain等[33-35]提出了相似的SKFE构造。强化了Lin[23]在2017年构造出的FE，基于双线性映射构造了PHFE。PHFE除了能够对秘密部分进行一次乘法计算外，还能对公开部分进行常数深度的计算。由于只需要构造一个支持NC0电路的SKFE，因此不需要使用全同态加密，只需要支持NC0电路的同态加密。同样的，会得到C(x)的加密，并用秘密部分的密钥来解密，解密操作是内积计算，得到的结果是C(x)+noise，不同于PE，这里的噪声会影响安全性，而模数操作又太复杂，无法依靠PHFE完成。为此，设想存在一个特殊的PRG，通过将种子加密在秘密部分和公开部分中，可以用PHFE计算得到PRG的输出，并用这个输出去掩盖噪声。也就是说，这个特殊的PRG输出的每个比特可以表示为秘密部分的至多2个比特和公开部分的至多常数个比特的乘积和。至此，iO被规约到了一个特殊的PRG。
2021年，Jain等[36]最终构造出了这一PRG，完成了基于标准假设构造iO的最后一块拼图。为此引入LPN假设，LPN假设与LWE假设有相似之处，主要区别在于LPN中的噪声虽然可能很大，但数量少；
LWE中的噪声都很小，但很少出现为0的情况。将PRG的种子用LPN加密，并同态计算一个NC0上的PRG，最终同样得到PRG(seed)+noise。LPN的噪声很稀疏，不同于LWE的噪声，其可能被PHFE去掉。具体做法是提前计算出LPN的噪声，并将其一并放在PHFE密文的秘密部分。解密时算出PRG(seed)+noise后，将其与PHFE中的噪声相减以抵消噪声。但是，噪声向量长度为|PRG(seed)|，为了sublinear compactness，只能加密长度小于这个值的输入(例如seed)。为此，需要将稀疏的噪声向量压缩后存储在PHFE密文的秘密部分，同时又要能够用一次乘法就将压缩的噪声向量还原回来(因为PHFE只支持对秘密部分计算一次乘法)。因此，用到了矩阵的分解，即将噪声向量排列为矩阵形式。由于其稀疏性，矩阵的秩很低，一个秩很低的m×m的矩阵可以分解为一个m×rank的矩阵和一个rank×m的矩阵的乘积。就这样，基于SXDH,LPN,LWE和NC0上存在PRG这4个假设的iO被构造了出来。之后，又利用LPN在NC0上的同态性去代替LWE(还包括一些其他技术)，将假设减少为3个，即去掉了LWE假设[37]。
群的特殊结构使得在面对量子计算机时，群上的安全假设(DH、RSA等)都会被攻破，因此，也有一些工作试图用LWE加上一些其他假设构造后量子安全的iO。这些候选方案有的是基于更强的循环安全 (circular security) 假设[38-40]，循环安全假设是用于构造FHE的重要假设，也是得到了较为广泛认可的假设。虽然这类iO方案同样使用了FHE及其相关的技术，但是它们所依赖的假设却强于FHE所需的假设。与此同时，Wee等[41]也展示了不经意的 LWE 采样可以蕴含 iO 并且给出了一个基于类似于循环安全的假设候选方案。然而，Hopkins等[42]针对上述候选方案的假设给出了反例。2021年，Wee等[43]进一步改进了他们先前的工作，基于一个更弱的密码学原语 (紧凑 LWE 采样 (succinct LWE sampling)) 构造出了 iO，同时也给出了一个紧凑 LWE 采样的候选方案，该方案的安全性与求解多项式等式系统的困难性相关联。除了基于循环安全方面的假设，也有一些工作试图基于带噪声的线性函数加密 (noisy linear functional encryption) 来构造 iO[44-45]。除此之外有个特殊的用于仿射行列式程序的混淆方案[46]，它的效率相较于其他方案非常高，而且安全性没有基于任何传统的假设，目前的量子技术对于攻击该方案也没有表现出特别的优势。但该方案的安全性无法规约到任何简明的具体假设上，且目前仅有唯一一篇针对该方案的安全分析[47]。
在这些工作中，基于更强的循环安全假设的工作最具代表性，也是本章重点介绍的方案。这类工作都是通过构造functional encoding从而构造iO，与上一节类似的是，他们也使用FHE加密消息，并在解密阶段对其进行解密。但是，FHE解密时不存在紧凑的解密提示，为此，使用了支持生成紧凑解密提示的线性同态加密(Linear Homomorphic Encryption,LHE)方案；
同时，采用密钥交换技术，能把消息在FHE下的加密转换为消息在LHE下的加密。最初这类方案[38]使用的LHE基于的是DCR假设[48]，因而无法实现后量子安全，后来这类方案[40]中的LHE被替换为基于LWE的LHE。
其中,线性同态加密只能支持线性函数的同态加密，其中一些构造可以将解密分为2步：①根据密钥和密文生成短的解密提示；
②根据解密提示对密文进行解密。
密钥交换技术最早出现在全同态加密的构造中，通常把解密过程视为用密钥对密文进行操作，如果转换视角，解密过程也可以理解为用密文对密钥进行操作。假设有第一个同态加密方案的密钥sk1，那么用x在第一个同态加密方案上的密文对该密钥进行操作可以解密得到x；
现在，将用第二个同态加密方案同态地进行这一操作，即最初持有地将不再是密钥sk1，而是用第二个同态加密方案加密过的sk1；
同理，此时的输出也不再是x，而是x在第二个同态加密方案上的密文。这样就完成了密钥的切换，需要注意的是，切换能够成功的前提是第二个同态加密方案支持同态地运行第一个同态加密方案的解密电路。FHE的部分解密是线性函数(计算内积)，因此,可以被LHE同态计算。但是，FHE部分解密得到的是C(x)+noise，至此，他们遇到了和之前的构造一样的问题，即如何掩盖噪声。
针对噪声的泄露通常只有2类方法：去除噪声或者用一个更大的随机噪声去掩盖。去除噪声是一个十分复杂的功能，无法用线性函数去解决(LHE只支持线性函数)，因此，只剩下用一个更大的噪声去掩盖这条路可以走。理想情况下，有一个预言机(oracle)，它能够产生一个LHE的密文，这个密文对应的明文是一个较大的随机噪声，通过LHE将两者进行叠加(加法是一个十分简单的线性函数,可以通过LHE的同态性完成)，就可以掩盖FHE产生的噪声。
现实情况下显然没有如此方便的oracle，但可以使用随机预言机(random oracle)产生一个随机数，前文提到的那几种LHE方案还具有一个非常好的性质，它们的密文空间很“稠密”(这意味着随机数有极大概率能被当成LHE的密文成功进行解密)。随机数对应的明文可能是个非常大的数，而需要的仅仅是一个稍大的噪声，这个噪声能够掩盖FHE解密时产生的噪声又不至于掩盖解密后的明文。此时，需要将明文的高位设为0，这又是一个十分复杂的操作，无法用线性函数完成，因此，使用密钥交换技术把LHE的密文转为FHE的密文，通过FHE全同态的能力去除明文的高位，之后再次利用密钥交换技术把FHE的密文转回LHE的密文，这样，就能得到一个经LHE加密的较大噪声。到这里仍然有一个小问题，就是利用密钥交换将FHE的密文转回LHE的密文时又会产生一个小噪声，这个小噪声会引入一定的相关性，虽然这个相关性看上去很难被敌手利用，但是这给安全性证明带来了困难。同时，由于密文需要在FHE和LHE之间互相转换，因此，这一构造在证明时需要用到循环安全假设。各类方案的对比见表1。
Gay等[39]随后对该方案做了进一步的改进，将random oracle替换为一串很长的CRS，并且发现FHE可以给密文附上新的噪声(同态地加上一个0的加密)，因此，通过给FHE密文附上较大噪声的方式去掩盖会产生相关性的小噪音。同时，给出了安全证明，将方案的安全性规约到了一个更强的循环安全假设。各类方案的对比见表1。
表1 iO主流候选方案对比Table 1 Comparison among the popular iO candidates
经过了十年的发展，构造可证明安全的iO已经初步取得了成功，一些曾经质疑iO是否有可能存在的研究者也开始转而投入相关的工作当中。尽管这一构造目前不是后量子安全的，但是研究者们也已经开始朝着这个方向前进。这类可证明安全的构造在安全性方面虽然更有保证，但是也会牺牲效率，而且完整的规约过程也十分复杂。除了实现后量子安全，这类方案未来可以朝着更少假设、更少规约和更高效实现这3个方向进一步前进。
另外，也有一些更为直接的构造，例如基于多线性映射以及矩阵随机化的候选方案。这类方案效率更高，但是在安全性方面需要大量的安全分析，并经受多轮攻击修复的循环才能得到较为广泛的信任。未来可以尝试提出各种直接构造iO的方案，并尝试对这些方案进行分析、攻击与修复。这类方案的高效性使得iO能更早地从理论世界进入应用领域。
猜你喜欢 同态密文解密 一种支持动态更新的可排名密文搜索方案黑龙江大学自然科学学报(2022年1期)2022-03-29基于模糊数学的通信网络密文信息差错恢复计算机仿真(2021年10期)2021-11-19炫词解密阅读（快乐英语高年级）(2021年4期)2021-07-11解密“一包三改”少先队活动(2020年9期)2020-12-17关于半模同态的分解*吉首大学学报（自然科学版）(2020年2期)2020-09-14拉回和推出的若干注记五邑大学学报（自然科学版）(2020年1期)2020-06-17τ-内射模的若干性质①佳木斯大学学报（自然科学版）(2020年2期)2020-05-18炫词解密阅读（快乐英语高年级）(2020年10期)2020-01-08一种基于LWE的同态加密方案信息安全研究(2016年3期)2016-12-01一种基于密文分析的密码识别技术*通信技术(2016年10期)2016-11-12