iO(4) 构造Split-FHE

我们的出发点

为了构造Split-FHE，我们先找到两个各自拥有其一部分特性的密码学组件：FHE和Split-LHE(这个方案最早是由Brakerski等人提出的)。

全同态加密是能够支持任意函数的同态加密，由Gentry等人最早提出实现。这里我们采用Gentry等人在2013年提出的FHE方案，我们称之为GSW。GSW中，解密可以通过线性函数实现，即，但是此时解密结果会被附上一个小噪声。

线性同态加密(Linear HE, LHE)是只能支持线性函数的同态加密，而Split-LHE则是指解密可以分为两步的LHE：第一步，根据秘钥和密文产生短的解密提示()，第二步根据解密提示和密文求出明文。这里我们采用Jurik等人在2001年提出的Split-LHE方案，我们称之为DJ。

密钥交换(Key-Switch)

为了方便区分，我们在论及LHE方案时，会用上划线和FHE加以区分，例如代表LHE的私钥。我们首先运用FHE的全同态特性计算得到，之后我们就希望使用Split-LHE的分两步解密的特性，那怎样才能把一个FHE的密文变为LHE的密文呢？这个技术就是密钥交换，由于FHE的解密过程是线性函数，于是有

之后，只要对LHE的密文分两步进行解密即可得到一个Split-FHE方案。

但是我们注意到，这样得到的Split-FHE方案是不安全的，因为它泄露了FHE的噪音，在GSW中，泄露噪音会泄露1比特关于秘钥的信息，而构造XiO时需要用到大量解密提示，也会带来大量信息的泄露，此时很可能会将完全泄露出去(最近有一篇针对CKKS同态加密方案的攻击正是基于这个原理)。

修复安全性

针对噪声的泄露通常只有两类方法：去除噪声或者用一个更大的随机噪声去掩盖，而去除噪声是一个十分复杂的功能，无法用线性函数去解决(LHE只支持线性函数)，因此只剩下用一个更大的噪声去掩盖这条路可以走。理想情况下，我们有一个Oracle，它能够产生一个LHE的密文，这个密文对应的明文是一个较大的随机噪声，通过LHE将两者进行叠加(加法是一个十分简单的线性函数,可以通过LHE的同态性完成)，就可以掩盖FHE产生的噪声。

现实情况下显然没有如此方便的Oracle，我们使用Random Oracle产生一个随机数，DJ有一个非常好的性质，它的密文空间很"稠密"(这意味着随机数有极大概率能被当成LHE的密文成功进行解密)。但是随机数对应的明文可能是个非常大的数，而我们需要的仅仅是一个稍大的噪声，此时需要将明文的高位置为0。这又是一个十分复杂的操作，无法用线性函数完成，因此我们使用密钥交换技术把LHE的密文转为FHE的密文，通过FHE全同态的能力去除明文的高位；之后再次利用密钥交换技术把FHE的密文转回LHE的密文，这样，我们就能得到一个经LHE加密的较大的噪声。到这里仍然有一个小问题，就是利用密钥交换将FHE的密文转回LHE的密文时又会产生一个小噪声，这个小噪声会引入一定的相关性，虽然这个相关性看上去很难被敌手利用，但这给安全性证明带来了困难。

因为使用密钥交换技术来回交换密钥时需要用到和，因此这个方案的安全性依赖于Circularity假设，这个假设说的是：在公开了和之后，FHE和LHE的加密方案仍然是安全的。

进一步改进

Pass等人对这个方案进行了进一步的改进，他们将Random Oracle替换为了一串很长的公共引用串(Common Reference String, CRS)，并且他们发现GSW可以给密文附上噪声，因此他们通过给FHE密文附上较大噪声的方式去掩盖会产生相关性的小噪音，从而最终在标准模型下完成了该方案安全性的证明。

由于DJ基于的是DCR假设，导致整个iO的构造不具有后量子安全性；Brakerski等人随后又提出了一个基于LWE假设的LHE方案用于替代DJ，来实现iO的后量子安全。

参考文献

 Z. Brakerski, N. Döttling, S. Garg, and G. Malavolta. Candidate iO from homomorphic encryption schemes. In EUROCRYPT 2020, Part I, LNCS, pages 79–109. Springer, Heidelberg, May 2020.

 C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with er- rors: Conceptually-simpler, asymptotically-faster, attribute-based. In CRYPTO 2013, Part I, LNCS 8042, pages 75–92. Springer, Heidelberg, August 2013.

 I. Damgård and M. Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In PKC 2001, LNCS 1992, pages 119–136. Springer, Heidelberg, February 2001.

 Baiyu Li and Daniele Micciancio. On the Security of Homomorphic Encryption on Approximate Numbers. Cryptology ePrint Archive, Report 2020/1533, 2020.

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

 Z. Brakerski, N. Döttling, S. Garg, and G. Malavolta. Factoring and pairings are not necessary for iO: Circular-secure LWE suffices. Cryptology ePrint Archive, Report 2020/1024, 2020.