Communications in Cryptology IACR CiC

Impossibility of Post-Quantum Shielding Black-Box Constructions of CCA from CPA

Authors

Loïs Huguenin-Dumittan, Serge Vaudenay
Loïs Huguenin-Dumittan
EPFL, Switzerland
lois dot huguenin-dumittan at epfl dot ch
Serge Vaudenay
EPFL, Switzerland
serge dot vaudenay at epfl dot ch

Abstract

Proving whether it is possible to build IND-CCA public-key encryption (PKE) from IND-CPA PKE in a black-box manner is a major open problem in theoretical cryptography. In a significant breakthrough, Gertner, Malkin and Myers showed in 2007 that shielding black-box reductions from IND-CCA to IND-CPA do not exist in the standard model. Shielding means that the decryption algorithm of the IND-CCA scheme does not call the encryption algorithm of the underlying IND-CPA scheme. In other words, it implies that every tentative construction of IND-CCA from IND-CPA must have a re-encryption step when decrypting.

This result was only proven with respect to classical algorithms. In this work we show that it stands in a post-quantum setting. That is, we prove that there is no post-quantum shielding black-box construction of IND-CCA PKE from IND-CPA PKE. In the type of reductions we consider, i.e. post-quantum ones, the constructions are still classical in the sense that the schemes must be computable on classical computers, but the adversaries and the reduction algorithm can be quantum. This suggests that considering quantum notions, which are stronger than their classical counterparts, and allowing for quantum reductions does not make building IND-CCA public-key encryption easier.

References

[AS16]
Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput., 45(6):2117–2176, 2016. https://doi.org/10.1137/15M1034064.
Google Scholar ePrint
[BBF13]
Paul Baecher, Christina Brzuska, and Marc Fischlin. Notions of black-box reductions, revisited. In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I, volume 8269 of Lecture Notes in Computer Science, 296–315. Springer, 2013. https://doi.org/10.1007/978-3-642-42033-7_16.
Google Scholar ePrint
[BDF+11]
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, 41–69. Springer, 2011. https://doi.org/10.1007/978-3-642-25385-0_3.
Google Scholar ePrint
[BN13]
Ahto Buldas and Margus Niitsoo. Black-box separations and their adaptability to the non-uniform model. In Colin Boyd and Leonie Simpson, editors, Information Security and Privacy - 18th Australasian Conference, ACISP 2013, Brisbane, Australia, July 1-3, 2013. Proceedings, volume 7959 of Lecture Notes in Computer Science, 152–167. Springer, 2013. https://doi.org/10.1007/978-3-642-39059-3_11.
Google Scholar ePrint
[BZ13]
Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II, volume 8043 of Lecture Notes in Computer Science, 361–379. Springer, 2013. https://doi.org/10.1007/978-3-642-40084-1_21.
Google Scholar ePrint
[CX21]
Shujiao Cao and Rui Xue. Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives. Theor. Comput. Sci., 855:16–42, 2021. https://doi.org/10.1016/J.TCS.2020.11.013.
Google Scholar ePrint
[FO99]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In Michael J. Wiener, editor, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, 537–554. Springer, 1999. https://doi.org/10.1007/3-540-48405-1_34.
Google Scholar ePrint
[FO13]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol., 26(1):80–101, 2013. https://doi.org/10.1007/S00145-011-9114-1.
Google Scholar ePrint
[GMM07]
Yael Gertner, Tal Malkin, and Steven A. Myers. Towards a separation of semantic and CCA security for public key encryption. In Salil P. Vadhan, editor, Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings, volume 4392 of Lecture Notes in Computer Science, 434–455. Springer, 2007. https://doi.org/10.1007/978-3-540-70936-7_24.
Google Scholar ePrint
[HR04]
Chun-Yuan Hsiao and Leonid Reyzin. Finding collisions on a public road, or do secure hash functions need secret coins? In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, 92–105. Springer, 2004. https://doi.org/10.1007/978-3-540-28628-8_6.
Google Scholar ePrint
[HY20]
Akinori Hosoyamada and Takashi Yamakawa. Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I, volume 12491 of Lecture Notes in Computer Science, 3–32. Springer, 2020. https://doi.org/10.1007/978-3-030-64837-4_1.
Google Scholar ePrint
[IR89]
Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, 44–61. ACM, 1989. https://doi.org/10.1145/73007.73012.
Google Scholar ePrint
[MS09]
Steven A. Myers and Abhi Shelat. Bit encryption is complete. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, 607–616. IEEE Computer Society, 2009. https://doi.org/10.1109/FOCS.2009.65.
Google Scholar ePrint
[NO02]
Harumichi Nishimura and Masanao Ozawa. Computational complexity of uniform quantum circuit families and quantum turing machines. Theor. Comput. Sci., 276(1-2):147–181, 2002. https://doi.org/10.1016/S0304-3975(01)00111-6.
Google Scholar ePrint
[RTV04]
Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Moni Naor, editor, Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951 of Lecture Notes in Computer Science, 1–20. Springer, 2004. https://doi.org/10.1007/978-3-540-24638-1_1.
Google Scholar ePrint
[Sim98]
Daniel R. Simon. Finding collisions on a one-way street: can secure hash functions be based on general assumptions? In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, 334–345. Springer, 1998. https://doi.org/10.1007/BFB0054137.
Google Scholar ePrint
[Unr15]
Dominique Unruh. Revocable quantum timed-release encryption. J. ACM, 62(6):49:1–49:76, 2015. https://doi.org/10.1145/2817206.
Google Scholar ePrint
[Vaz98]
Umesh Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 356(1743):1759–1768, 1998. https://doi.org/10.1098/rsta.1998.0247.
Google Scholar ePrint
[Zha15]
Mark Zhandry. A note on the quantum collision and set equality problems. Quantum Inf. Comput., 15(7&8):557–567, 2015. https://doi.org/10.26421/QIC15.7-8-2.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/akp2fhbmo
History
Submitted: 2023-12-22
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Loïs Huguenin-Dumittan and Serge Vaudenay, "Impossibility of Post-Quantum Shielding Black-Box Constructions of CCA from CPA," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/akp2fhbmo.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.