iO(6) 构造Weakly Sublinear Compact FE

设FE方案能支持的最大电路的大小为，为安全参数，是被加密的消息。

如果一个FE方案的加密算法的时间复杂度是，则这种FE被称作Sublinear Compact FE。

如果一个FE方案的加密算法的时间复杂度是，但是输出长度是，则这种FE被称作Weakly Sublinear Compact FE。

穿孔(Puncture)

当使用iO来构造其他密码学组件时，往往需要使用到Punctured Program来进行安全性的规约，这项技术最早是Sahai等人于2014年提出的。

一个伪随机数发生器的输入是一串长为的真随机数，输出是长为的伪随机数()，PRG的安全性要求输出的伪随机数和长为的真随机数不可区分；同时由于进行多项式次PRG的调用就可以得到任意多项式长度的伪随机数，因此可以直接认为调用PRG能得到一个任意多项式长的伪随机数。

伪随机函数有和两个输入，当随机选取K后，函数就变成了，简写为；假设我们还有一个随机函数将长为的每个输入随机地映射到长为的每个输出上，则任何能对和进行黑盒访问的PPT敌手无法区分这两者。

通过PRG构造PRF最早是由GGM三人提出的，这项构造需要一个长度翻倍的PRG()。首先假设有一个长为的伪随机数(可以由PRG和得到)，经过一次长度翻倍后，得到了两个长度为m的伪随机数，对这两个伪随机数分别进行长度翻倍就得到了四个长度为m的伪随机数......重复进行次就得到了个两个长度为m的伪随机数，并且产生这些伪随机数的过程可以被看作一颗完全二叉树，从这颗树的根节点到叶子节点需要进行次left-or-right的选择，而PRF的输入恰有位比特位，可以表示n次选择，这样对于输入，就得到了一个相应的长度为m的伪随机数输出。

相比于通常的PRF，可穿孔PRF能够支持穿孔(穿孔就是隐藏PRF在某些输入上对应的输出)。设集合，也就是说是取值范围的子集，针对集合穿孔分为两个步骤：首先利用PPRF提供的函数，输入和，输出；接着，对于任意，都能够依靠得到对应的输出，即；而对于那些，根据无法得到任何与对应的输出有关的信息，也就是说，对于持有而不持有的人，，其中是真随机数。

通过对GGM稍加改造，我们就可以实现PPRF。我们以对一个输入进行穿孔为例，我们把这个叶子节点命名为，那么从根节点到总共途径个中间节点(包括)，这些节点我们称作，与这些相邻的节点我们称为，那么只需要注意到，如果我们只有的信息，那我们就能到达除以外所有的叶子节点，同时这些的值不会泄露任何有关的信息，也就是说，只要令等于构成的集合，就实现了PPRF。

Succinct FE + XiO => Weakly Sublinear Compact FE

我们先从只支持单比特输出的Succinct FE出发，Succinct FE对于单比特输出的函数是Compact的，设函数的输出长度为，则可以用个Succinct FE 分别计算函数的每个比特的输出，我们用来表示这些Succinct FE。当需要加密一个消息时，我们分别用这个去做加密得到个加密密文；对函数进行解密时也只需要生成个解密密钥，并将这些解密密钥应用到相应的加密密文上，这样我们实际上得到了一个支持多项式长度输出的FE，其加密的时间复杂度和加密密文的长度均为。为了得到Weakly Sublinear Compact FE，我们需要压缩加密密文的长度，XiO刚好可以用于对电路的真值表进行压缩。

现在我们假设有一个电路，可以看做一个选择器，输入，输出相应的，显然，这个电路的输入长度是，刚才提到的FE的密文，也就是个刚好可以视为这个选择器的真值表。那么，根据XiO的定义，，同时根据XiO功能保持的性质，通过输入仍然可以得到相应的密文，即。这样，通过Succinct FE和XiO的组合，我们就得到了Weakly Sublinear Compact FE。

为了使用PPRF进行安全性证明，我们假设加密过程会用到PPRF产生的伪随机数，即。

hybrid argument

这是一个能将单比特安全转为多比特安全的常用技巧，通过每次改变一个中的值，只要能证明这一次的修改是安全的，就证明了多项式次这样的修改也是安全的，因此我们只需要证明。

单步证明

首先，假设电路的前个输出是，其后均为；我们对电路稍加改造，使得前个输出是，第i+1个输出是,其后均为，记这个电路为。由于PPRF的穿孔位于，因此这两个电路在以外的输入上都是一致的；同时又由于我们把它们在处的输出也设置为了一致的，因此根据XiO的性质，功能相同的电路混淆后不可区分，于是有；类似的，有.

接着再将电路在处的值改为随机数，由于PPRF的性质，不包含任何的信息，即，因此；类似的，有。(需要注意的是，这个程序中只有的信息，没有的信息，只是它的第个输出设置成了这个具体的数，这一个数本身是不需要携带K的信息的)

之后，根据Succinct FE的CPA安全性，有，即，综上可得。

参考文献

 Amit Sahai and Brent Waters. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. Proc. of STOC 2014. ,2014

 O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792- 807, 1986.

 H. Lin, R. Pass, K. Seth, and S. Telang. Indistinguishability obfuscation with non-trivial efficiency. In PKC 2016, Part II, LNCS 9615, pages 447–462. Springer, Heidelberg, March 2016.