[网络协议] （可实现的CCA2 放松条件---funcCPA）论文学习笔记

同态加密保护了使用的数据，但计算是昂贵的。为了避免大量的代价高的自举操作（bootstrapping），即刷新密文，一些工作需要开发客户辅助外包协议（client-aided outsourcing protocols）,在这个协议中客户间歇的刷新密文对于一个执行同态计算的服务者。但是对于抵挡恶意的服务者（malicious servers）这个协议安全吗？

我们提出了一个完全不安全的CPA-security 加密方案。并且我们定义一个关于安全性的概念，funcCPA，我们证明funcCPA是足够对于抵挡恶意服务者。另外，我们展示了：

——有某些类型的电路隐私的同态加密方案是funcCPA-security，例如，方案中的密文可以被“净化（sanitized）”。

——特别，假设确实存在一些HE方案是CPA-security，它们也是funcCPA-security。

——对于特定的加密方案，像Brakerski-Vaikuntanathan，有我们叫做不在意的私钥提取（oblivious secret key extraction）,funcCPA-security暗示了循环安全（circular security）的性质，即，这是安全的去提供一个对于私钥的加密，并以一种对自举（bootstrapping）可用的形式。

总之，funcCPA-security在合理的假设下严格的存在在CPA-security和CCA2-security之间，并且和循环安全有些有趣的关系，尽管并不是等同的。

1.介绍

同态加密支持在不使用私钥的情况下对密文进行计算，同态加密是一种重要的方法保护数据和将潜在的破坏的影响减到最小，尤其对于计算一些敏感数据的外包和基于云结构的工业要求十分有用。

对于同态加密方案可实现的安全概念是CPA-security，这是众所周知CCA2-security由于HE方案内在的延展性（inherent malleability）是不能实现的。然而，CPA-security对于安全协议来说并不总是充分的，因为它仅仅考虑诚实的生成密文并没有保证一种设置，在这种设置中，敌手是允许去注射他恶意地精心制作的密文到诚实的系统中去。因此，依赖于CPA安全的安全协议仅仅抵挡半诚实敌手（除非使用进一步的密码学工具去加强安全性。）

然而在实际中安全抵挡恶意敌手是期望去防止真实世界的攻击，一个自然的问题产生：

对于HE方案和安全抵挡恶意攻击者，是否存在一个有关CCA2-security放松是可实现的？

1.1 Our contribution

对于这项工作，我们通过提供一个新的安全概念肯定的回答了以上的问题，展现了这种新的安全概念对于公钥加密方案是CCA2安全的一种放松。具体地，CCA2安全是抵挡了具有复原能力敌手，该敌手可以收到他们所选择的密文对应的明文，funcCPA仅仅抵挡较低级的复原能力敌手，该敌手可以收到对于他们选择的密文潜在明文的重加密（一般的说，对潜在明文值的计算结果进行加密）更详细的可以看定义6。这说明，在funcCPA安全中，敌手只能观察到密文，不能观察到明文值，然而，敌手甚至在完全不知道明文值时，可以完全控制执行这些潜在明文值的计算，并且可以注入精心制作的恶意密文。

我们注意到CCA2安全暗示着funcCPA-security，此外，我们通过展示了这是可实现对于HE方案（CCA2对于同态加密来说不可实现），证明了这是一种对于CCA2严格的弱化。此外，（在假设单向函数（one-way functions）存在的情况下）funcCPA-security暗指CPA-security，但反过来不可以。为了证明后者，我们提供了：（1）关于一个广泛并自然的外包协议族（即，client-aided 外包协议）的一个安全性证明，这些外包协议在用funcCPA-security方案实例化时维持了安全性。（2）在用一种精心制作的CPA-security方案实例化的client-aided 外包协议，存在可以打破安全性的攻击。这证明了funcCPA-security严格存在在CPA-security和CCA2-security之间。

---------------------------------------------------------------------------------------------------------------------------------

这是介绍了client-aid outsourcing protocols是如何定义的。主要是有关先前的一些论文都有关提供给敌手对潜在明文值进行重加密[38][5,1,2,22,3,26],这里的加密方式不同。computing comparions[5], minima[1,2], linear equations solutions [22,3], ReLU and Max-Pooling[26].为了捕捉和生成[5,1,2,22,3,26]安全外包协议，我们定义了一族自然的协议，即client-aid outsourcing protocols。这个族由所有这类型的协议构成：用户生成密钥和上传加密数据给服务者；服务者执行计算在加密的数据上，并且把加密结果给用户；此外，为了减少一些计算量，sever可能给client（typical few and lightweight）形如 $(e, G)$ 这样的询问，这里e是一个密文向量，G是一个函数,以至于client用作用在潜在明文值，并给sever一个加密结果 $\boldsymbol{e}'\leftarrow Enc_{pk}(G(Dec_{sk}(\boldsymbol{e})))$ .?

我们证明了client-aided outsourcing protocols 拥有funcCPA-security实例化方案可以抵挡恶意服务者（malicious servers）。即，funcCPA-security 足够在这些设置中保持隐私，甚至可以抵挡恶意的攻击者。

---------------------------------------------------------------------------------------------------------------------------------

相反的，我们具体说明了CPA-security对上面的协议族（client-aid outsourcing protocols）并不提供隐私（privacy）。

?Achievability by existing schemes of funcCPA-security.为了避免由于使用净化（sanitization）导致的性能开销，我们检查了一些popular HE schemes的funcCPA-security的可能性。我们证明了leveled HE schemes像BV[9], BGV[8], B/FV[7,18] 是leveled-funcCPA-security（基于它们的CPA-security）。这是因为对于有限级（leveled）设置它们关于funcCPA满足自然的自适应，这里的funcCPA oracle（预言机）对于下一级用密文回答询问。我们的安全证明本质上没有对这些方案进行修改（除了一些稍微改变在求值密钥生成，这仅仅在性能上有一些影响），并没有任何额外安全假设。

?更一般的，上面的成立对每一个有限级的HE scheme对于每一级独立的密钥生成。（详细说明在定义 12）.

相比之下，对于BV和BGV同态方案，我们展示了funcCPA-security 暗示了（weak） circular security. 具体地，我们展示了funcCPA 预言机（oracle）能够从公钥生成私钥的加密（in the encoding required for bootstrapping）,因此funcCPA-security 剔除了这个弱循环安全假设。对于这些方案，在证明funcCPA-security，这能被解释为一个界限，因为它将解决长期存在的关于循环安全假设的必要性的开放问题（see e.g. Question 11 in Peikert's survey[33]）。

?On the necessity of? funcCPA against semi-honest adversaries.为了进一步学习funcCPA-security的概念，我们审查了funcCPA-security对于抵挡半诚实的敌手（semi-honest adversaries）的必要性。我们证明了对于client-aided outsourcing protocols 满足一个自然的性质，CPA-security足够抵挡半诚实的敌手。我们要求的这个性质是协议是明文可计算的（cleartext computable），从某种意义上说通过这个协议用户的输入决定了传输密文潜在的明文值。这体现了一个事实，这种协议中的加密是对明文值的外部包装，仅仅用来抵挡server实现隐私，并没有影响潜在的明文计算。这个性质在外包协议中是自然的，在外包协议中，server对于计算没有提供任何输入，而是它只是一个代表用户（client）存储和处理加密数据的容器。

?总之，在这项工作中，我们引入了严格位于CPA和CCA2之间的funcCPA的概念（在标准的假设下），并且展示了对于HE schemes来说funcCPA-security是可实现的（不像CCA2）,对于广泛和自然的client-aided outsourcing protocols对于抵挡恶意的servers是足够确保隐私（不像CPA）。据我们所知，funcCPA-security是第一个对CCA2放松，并且对于同态方案是可实现的和确保隐私（对于client-aided 外包协议）抵挡恶意的敌手。

1.2 Our Techniques

?我们的定义关于funcCPA(定义6)扩大了CPA，通过授予敌手在CPA 实验可以使用 $Enc_{pk}(\mathcal{G}(Dec_{sk}(\cdot)))$ 预言机对于一个函数族 $\mathcal{G}$ 。即，敌手能够提交（possibly, adaptive）询问 $(e, G)$ ，对于密文e和一个函数所选择的 $G\in \mathcal{G}$ ，收到一个结果 $\boldsymbol{e}'\leftarrow Enc_{pk}(G(Dec_{sk}(\boldsymbol{e})))$ 。

为了证明funcCPA对于可净化的HE方案的可实现性（Theorem 1）我们首先定义了 $curcuit-pricacy^{+}$ 的概念，它存在在半诚实和恶意的电路隐私之间，在 $curcuit-pricacy^{+}$ 允许恶意形式的密文，但是要求诚实的生成密钥。我们展示了如何在一个净化算法下从CPA-security转化为 $CPA-secure \,circuit-private^{+}$ 方案。最后我们证明了CPA-secure? $curcuit-pricacy^{+}$ 方案是funcCPA-secure.

?对于我们证明CPA-security是不足的攻击（Theorem 3），我们第一次展示了每一个CPA-secure 方案能被略微修改去得到一个打孔（punctured）CPA-secure 方案，而在打孔的CPA-secure 方案我们的攻击是适用的。这个攻击使用了单个询问 $\boldsymbol{e}'\leftarrow Enc_{pk}(G(Dec_{sk}(\boldsymbol{e})))$ ，where e is a concatenation of the client's encrypted input with a special "trapdoor" ciphertexts planted in the publiec-key.询问e攻击方案的打孔以至于这个结果e'揭示了用户的输入。尽管这是可打孔的，这个加密方案保持CPA secure，因为陷门密文是不可行诚实的产生，即加密一个有效的可抽样的信息。

1.3 Related Work

CCA2 relaxations. 许多放松关于CCA2-security先前已经被考虑过了[37,10,34,30,28],虽然放松CCA2的其他方面，而不是我们funcCPA概念。

具体地，Shoup[37], Canetti et al[10]? 和 Prabhakaran and? Rosulek[34]提出了一种关于CCA2的放松，在这种情况下，禁止解密预言机询问，不仅仅是挑战密文，包括任意和挑战密文解密成相同明文的密文（或扩展了这个概念）。这捕捉了加密方案密文是有延展性的，但仅保留其底层的明文（或它的陪集）。这些放松是以捕捉加密方案为目的（一些是自然的在实例中提出），放松不是CCA2 secure 但是似乎充分安全”用于大多数实际可行的目的“；直觉是，生成不同的密文的能力，解密到与给定的密文相同的值，应该不会帮助攻击者。然而在HE的内容中这些放松时不可能实现的，因为如果同态是支持的，那么敌手收到一个挑战密文关于x的加密，能同态的产生一个密文对于一个相关信息（e.g. x+1 or 2x）的加密，然后通过调用解密预言机在这些密文，敌手就可以恢复x。

另一种工作方法，包括（e.g. [30],[28]）展示了CCA1 是可实现的对于HE（unlike CCA2）.这似乎是不充足的在client-aided outsourcing protocols 对于隐私抵挡恶意的服务者来说，因为如果在挑战之后提交了一些重要的查询，CCA1并不能保证安全性。此外，CCA1是不能实现的对于全同态方案（因为完全同态方案出于自举的目的提供了对密钥的加密作为公共密钥的一部分，并且在这个密文上查询CCA1预言机将恢复密钥并破坏安全性）。相比之下，我们的结果展示了funcCPA-security 是可实现的对于全同态方案（e.g., see Theorem 1）.

Insufficiency of CPA-security. 对于一个利用同态加密的协议来说CPA-security的不足性被Li and Micciancio[29]考虑。他们表明，当协议向攻击者公开解密(exposes decryptons)时，使用CKKS[12]的CPA安全近似HE方案实例化的协议是不安全的，即使是对半诚实的对手也是如此。相比之下，我们的攻击使用于精确的和近似的方案，即使没有解密被提供（尽管是一个恶意的对手）。此外，我们展示了CPA-security是足够去保证隐私抵挡半诚实的敌手对于明文可计算的client-aided outsourcing protocols.

Paper organization. 预备知识定义在第2部分，我们对恶意对手的研究结果——包括功能CPA的定义、净化和充分性的可实现性，以及CPA的不足——出现在第3节中；第4节给出了现有HE方案可实现性的结果；以及我们在第五节中对半诚实对手的结果；我们在第6节中总结。

---------------------------------------------------------------------------------------------------------------------------

篇幅过长，分开来学习，这一部分都是一些介绍，提出了一个新的概念，很好理解，但是对于文章中的参考文献，由于还没有进行阅读学习，有些知识还有待提高。

-------------------------------------------------------------------------------------------------------------------------------

2. A. Akavia, M. Leibovich, Y. S. Resheff, R. Ron, M. Shahar, and M. Vald. Privacy-preserving decision trees training and prediction. In Machine Learning and Knowl edge Discovery in Databases , pages 145–161. Springer International Publishing, 2021.

3. A. Akavia, H. Shaul, M. Weiss, and Z. Yakhini. Linear-regression on packed encrypted data in the two-server model. In M. Brenner, T. Lepoint, and K. Rohloff, editors, Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2019, London, UK, November 11-15, 2019 , pages 21–32. ACM, 2019.

5. R. Bost, R. A. Popa, S. Tu, and S. Goldwasser. Machine learning classification over encrypted data. In NDSS , volume 4324, page 4325, 2015.

7. Z. Brakerski. Fully homomorphic encryption without modulus switching from classical gapSVP. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptol ogy Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings , pages 868–886, 2012.

8. Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012 , pages 309–325, 2012.

9. Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from?(standard) lwe. SIAM Journal on computing , 43(2):831–871, 2014.

10. R. Canetti, H. Krawczyk, and J. B. Nielsen. Relaxing chosen-ciphertext security. In D. Boneh, editor, Advances in Cryptology - CRYPTO 2003 , pages 565–582, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.

12. J. H. Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and? Application of Cryptology and Information Security , pages 409–437. Springer, 2017.

18. J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption.? IACR Cryptology ePrint Archive , 2012:144, 2012.

22. I. Giacomelli, S. Jha, M. Joye, C. D. Page, and K. Yoon. Privacy-preserving ridge?regression with only linearly-homomorphic encryption. In Applied Cryptography and Network Security - 16th International Conference, ACNS 2018 , pages 243–261. Springer, 2018.

26. C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan. Gazelle: A low latency framework for secure neural network inference. In Proceedings of the 27th USENIX Conference on Security Symposium , SEC’18, page 1651–1668. USENIX Association, 2018.

28. J. Lai, R. H. Deng, C. Ma, K. Sakurai, and J. Weng. Cca-secure keyed-fully homomorphic encryption. In C.-M. Cheng, K.-M. Chung, G. Persiano, and B.-Y. Yang, editors, Public-Key Cryptography – PKC 2016 , pages 70–98, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.

29. B. Li and D. Micciancio. On the security of homomorphic encryption on approximate numbers. IACR Cryptology ePrint Archive , 2020:1533, 2020.

30. J. Loftus, A. May, N. P. Smart, and F. Vercauteren. On cca-secure somewhat?homomorphic encryption. In A. Miri and S. Vaudenay, editors, Selected Areas in? Cryptography , pages 55–72, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.

33. C. Peikert. A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. , 10(4):283–424, mar 2016.

34. M. Prabhakaran and M. Rosulek. Homomorphic encryption with cca security. In?L. Aceto, I. Damg?ard, L. A. Goldberg, M. M. Halld′orsson, A. Ing′olfsd′ottir, and?I. Walukiewicz, editors, Automata, Languages and Programming , pages 667–678,?Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.

37. V. Shoup. A proposal for an ISO standard for public key encryption. IACR Cryptol. ePrint Arch. , page 112, 2001.

38. W. Wang, Y. Jiang, Q. Shen, W. Huang, H. Chen, S. Wang, X. Wang, H. Tang, K. Chen, K. E. Lauter, and D. Lin. Toward scalable fully homomorphic encryption?through light trusted computing assistance. CoRR , abs/1905.07766, 2019.