iO(5) 构造succinct FE

前文已经提到，Lin等人在2016年给出了XiO=>iO的构造，而这个构造的第一步就是要构造一个succinct的FE方案。

需要特别指出的是，这个构造中涉及的FE都是公钥FE，且这些FE的算法针对每个只能运行一次(同时拥有和可能会影响安全性)。

FE的效率要求(1)

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

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

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

Succinct vs Compact

二者的区别在于Compact的加密复杂度与支持的电路的输出长度无关，亦即对于单比特输出电路而言，Succinct和Compact是等价的。

准备工作

为了构造succinct的FE方案，我们需要全同态加密、混淆电路和基于属性加密。

混淆电路最早是由姚期智院士提出的。考虑一个电路，它的输入有个比特，电路的持有者可以通过设置电路的输入位得到相应的输出，那么有没有办法在隐藏电路输入的情况下计算输出呢？混淆电路便可做到这一点，混淆电路的输入不再是比特0或比特1，而是对与之关联的标签，每对标签分别代表在某一输入位上输入0或输入1(这些标签可以被视为随机数，不会泄露信息)，通过输入这些标签，GC可以计算得到相应的输出，这个计算过程不会泄露输入的信息。需要注意的是，通常情况下GC是不可重复使用的，亦即如果需要计算两个不同输入对应的输出，就必须生成两次混淆电路。由于GC能够安全地计算电路的输出，其在MPC领域也有着广泛的应用。

ABE是一种特殊的公钥加密方案，这主要体现在它的加密过程和解密过程上。在加密一个消息时，加密算法还会要求输入属性；政策(policy)是ABE解密过程的一个概念，它是一个函数，ABE的解密过程是同政策相关的，拥有主密钥人的可以根据不同的政策产生不同的子密钥，这些子密钥拥有不同程度的解密能力，具体说来，当且仅当子密钥对应的和密文对应的属性满足时，解密才能成功。

考虑这样一个应用场景，公司有三份文件，其机密程度不同，分别是3级、8级和10级(数字越大代表机密程度越高)；现在公司中有两个员工，其中一个是中层领导，能够查看4级以下的机密文件，另一个是高层领导，能查看9级以下的机密文件，那么运用ABE给他们分配相应的密钥，就可以很方便地保证他们各自只能查看他们有权限查看的文件。

ABE

ABE是ABE的一种变体，它与传统ABE的区别在于其在加密阶段会加密两个消息，分别记为和；在解密阶段，当且仅当子密钥对应的和密文对应的属性满足时，得到，换言之，解密时一定能且仅能得到两个消息中的某一个消息。ABE可以通过两个主密钥不同的ABE直接构造得到(其中)。

Succinct FE for NC

构造Succinct的FE方案用到的ABE采用Gorbunov等人在13年提出的GVW方案(LWE-based)。

之前通过对比FE和HE，我们指出了，二者的区别在于HE得到的结果是的密文，而FE可以直接得到，那么如果能够对FHE得到的结果进行解密就可以得到一个FE的方案。那么怎样安全地进行FHE密文的解密呢？GC刚好可以用于安全地计算某个电路的输出，通过生成FHE解密电路的混淆电路，就可以在不知道解密密钥等信息的情况下对FHE的密文进行解密(可以把这个过程类比为密钥持有方和密文持有方的2PC)。但是，如何在非交互场景下给出GC输入对应的标签就成了新的问题(这毕竟不是2PC，无法使用OT)。由于GC安全性的要求，我们只能给出和某个输入对应的标签而不能将标签全部公开，但是我们又无法预测得到的密文是什么，这时ABE刚好能解决这个困境，ABE保证了任何人只能获取每对标签的其中一个(这一点和2-to-1的OT非常相似)，同时有了之后我们能通过计算得到，那我们自然也能构造函数，其中为第个比特的值。只要将作为ABE加密时的属性用来加密两个标签，将作为ABE解密时的政策，就能通过ABE得到第个比特对应的标签。

文章的开头已经提到了，刚才构造的FE的针对单个只能运行一次，这是由GC不可重复使用的特性决定的。

刚才构造的FE的加密过程需要用ABE加密组标签()，而密文长度是和明文长度相关的，即，因此加密算法的时间复杂度是关于也即电路的输出长度的多项式，这就解释了为什么这个FE是Succinct的。

这个方案本身是支持所有的电路的，但是，由于这个方案中采用的GVW方案是leveled-ABE，因此该方案的加密算法的时间复杂度是关于电路深度的多项式，如果想要保证整体的FE方案满足Succinct的性质(Succinct要求加密的时间复杂度是关于电路大小s的对数的多项式)，那么该方案只能适用于NC的电路。

Bootstrapping

通过bootstraping能够将NC上的Succinct FE方案变为上的Succinct FE方案。在介绍具体做法之前先介绍Randomized Encoding的概念。

RE可以看做是对一个计算过程的编码，它包含Encode和Decode两个算法，Encode输入函数和函数的输入，输出一个编码，记为(隐藏了的信息)；而Decode则可以根据还原出的值。

我们注意到，GC就是一种能够编码的RE，通过将转化为电路，再把电路变为混淆电路，并从混淆电路关联的标签中把与输入相对应的标签挑选出来，混淆电路和被选出来的标签共同构成了；Decode的时候只需要将标签作为混淆电路的输入就能得到。

构造混淆电路的过程主要有两个步骤，首先是为每个输入和中间结果生成标签，这是NC内可计算的；接下来是为每个逻辑门用对称加密算法加密标签，如果选用的对称加密方案是NC上的，那么这一步也是NC内可计算的。这样，任给一个的电路和一个输入，计算的结果均可以在NC内完成。

由于是NC内可计算的，而我们恰有一个NC上的Succinct FE方案，综合这两点，我们可以用NC上的FE计算任意的电路在输入上的，即；得到后，再调用就可以得到。

参考文献

 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.

 Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. Reusable garbled circuits and succinct functional encryption. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 555–564, 2013.

 Andrew C. Yao. Protocols for secure computations. In FOCS, pages 160–164, 1982.

 Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Attribute-based encryption for circuits. In STOC, 2013.

 Prabhanjan Ananth, Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan. The trojan method in functional encryption: From selective to adaptive security. Technical report, generically. Cryptology ePrint Archive, Report 2014/917, 2014.