iO(7)构造iO的最后一步

RE for TMs 的效率要求

我们考虑图灵机的RE，对于一个图灵机，图灵机的输入以及图灵机运行时间的上限，，根据可以高效地计算得到。我们把生成的过程叫做Encode，根据得到的过程叫做Decode，Decode的时间复杂度应当是。图灵机RE的效率定义和FE的效率定义是类似的。

Encode的时间复杂度为。

Encode的时间复杂度为。

Encode的时间复杂度为，输出长度为。

Encode的时间复杂度为，其中是图灵机输出的长度。

RE的安全性要求

RE的安全性至少要求其至少能够保护输入的信息，亦即，再某些更强的安全性定义里面，还会要求保护图灵机的信息，即；我们只需要较弱的RE。

FE=>RE

假设我们有一个FE方案和一个通用电路，。设，(看上去这个算法没有使用到，但是的大小会影响这个计算过程的时间复杂度，输出长度等，这就好比FE的加密算法的复杂度往往会和FE所能支持的最大电路的大小挂钩)，。因为直接调用了，因此这个FE=>RE的构造是没有效率损失的(对于功能一致的图灵机和电路，图灵机的运行时间和电路的大小是对应的，至多是关于的多项式，也至多是关于的多项式)。

由于我们已经有了Succinct FE和Weakly Sublinear Compact FE，通过这个构造，我们就能得到Succinct RE和Weakly Sublinear Compact RE。虽然这步构造用到了CRS，我们一会就将看到，最终的iO是不带CRS的(在介绍Split-FHE构造的时候，我们提到了Pass等人将原本构造中的RO改为了CRS，同样的，这一做法也不会导致最终得到的iO带有CRS)。

RE的组合

设是Succinct RE，是Weakly Sublinear Compact RE，我们通过将它们进行组合构造一个Sublinear Compact RE。这个计算过程本身可以视为关于输入的一个图灵机，记为，记为则；。

由于是先后分别使用了和，通过使用，的时间复杂度，输出长度为(由Weakly Sublinear Compact 可得)；接着调用时，由于此时输出长度由下降到了，因此时间复杂度为(由于Succinct的时间复杂性和输出长度相关)，从而得到了Sublinear Compact RE。

Sublinear Compact RE=>iO

此处的构造依旧采用类似GGM的构造；假设电路的输入长度为，则GGM树的高度为，，树的每个节点都是一个图灵机的RE，这个图灵机没有输入，我们用来表示这些图灵机，是一串01串，是输入的子串，长度为(根节点对应图灵机中的是空串，记为)。如果图灵机位于树的层，那么图灵机会输出；否则，图灵机会输出和，由RE的安全性，这个构造的正确性是显然的。

下图展示了一个输入长度为2的简单电路的iO构造。

下面我们说明为什么至少需要Sublinear Compact的RE。我们可以采用反证，令GGM树中的每个图灵机的运行时间均不超过，是一个多项式，是输入长度；假设GGM树种采用的RE不是Sublinear Compact的，即的时间复杂度至少为。由于父节点的图灵机的功能是生成两个子节点的图灵机的RE，因此父节点图灵机的运行时间是，根据的定义，我们有，移项得，一个多项式始终不大于一个常数是不可能的，因此至少需要Sublinear Compact的RE才能构造iO。

小结

至此，circularity-based iO的主要工作就大体介绍完毕了，LPN-based iO的相关工作的介绍将会在一段时间后更新。

参考文献

 Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang. Output-compressing randomized encodings and applications. 2015.

 Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. Cryptology ePrint Archive, Report 2020/1010, 2020.