Incompressible Encryption Beyond CPA/CCA Security
Authors
Venkata Koppula, Abhinav Kumar, Mahesh Sreekumar Rajasree, Harihar Swaminathan
Venkata Koppula
IIT Delhi, New Delhi, India
kvenkata at cse dot iitd dot ac dot in
kvenkata at cse dot iitd dot ac dot in
Mahesh Sreekumar Rajasree
CISPA Helmholtz, Saarbrücken, Germany
srmahesh1994 at gmail dot com
srmahesh1994 at gmail dot com
Abstract
An incompressible encryption scheme offers protection against adversaries who possess the entire secret key but can store only a portion of the ciphertext. In recent years, there has been growing interest in developing such primitives in both public-key and secret-key settings, as well as in the multi-user scenario.
In this work, we extend the concept of incompressible encryption to incorporate anonymity and key-dependent message security. We introduce the following schemes:
- The first key-dependent message incompressible SKE scheme secure against unbounded adversaries.
- The first anonymous incompressible SKE scheme secure against unbounded encryption queries.
Furthermore, we present the public key versions of these schemes.
References
[ABBC10]
Tolga Acar, Mira Belenkiy, Mihir Bellare, and David Cash. Cryptographic agility and its relation to circular encryption. In Advances in Cryptology–EUROCRYPT 2010, pages 403–422. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_23
[ABDY25]
Gal Arnon, Shany Ben-David, and Eylon Yogev. Instance Compression, Revisited. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 244–273. 2025. Springer. DOI: 10.1007/978-3-031-91134-7_9
[ABN10]
Michel Abdalla, Mihir Bellare, and Gregory Neven. Robust encryption. In Theory of Cryptography: 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings 7, pages 480–497. 2010. Springer. DOI: 10.1007/978-3-642-11799-2_28
[ACPS09]
Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, pages 595–618. 2009. Springer. DOI: 10.1007/978-3-642-03356-8_35
[AP16]
Navid Alamati and Chris Peikert. Three’s compromised too: Circular insecurity for any cycle length from (ring-) lwe. In Annual International Cryptology Conference (CRYPTO), pages 659–680. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_23
[AP24]
Navid Alamati and Sikhar Patranabis. Cryptographic primitives with hinting property. Journal of Cryptology, 37(3):21, 2024. DOI: 10.1007/s00145-024-09502-9
[BBDP01]
Mihir Bellare, Alexandra Boldyreva, Anand Desai, and David Pointcheval. Key-privacy in public-key encryption. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 566–582. 2001. Springer. DOI: 10.1007/3-540-45682-1_33
[BDD22]
Pedro Branco, Nico Döttling, and Jesko Dujmović. Rate-1 Incompressible Encryption from Standard Assumptions. In TCC 2022 (Part II), volume 13293 of LNCS, pages 33–69. 2022. Springer. DOI: 10.1007/978-3-031-22365-5_2
[BGK+25]
Kaartik Bhushan, Rishab Goyal, Venkata Koppula, Varun Narayanan, Manoj Prabhakaran, and Mahesh Sreekumar Rajasree. Leakage-Resilient Incompressible Cryptography: Constructions and Barriers. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology – ASIACRYPT 2024, Singapore. 2025. Springer Nature Singapore. DOI: 10.1007/978-981-96-0941-3_7
[BHHI10]
Boaz Barak, Iftach Haitner, Dennis Hofheinz, and Yuval Ishai. Bounded key-dependent message security. In Advances in Cryptology–EUROCRYPT 2010, pages 423–444. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_22
[BHHO08]
Dan Boneh, Shai Halevi, Mike Hamburg, and Rafail Ostrovsky. Circular-secure encryption from decision diffie-hellman. In Advances in Cryptology–CRYPTO 2008, pages 108–125. 2008. Springer. DOI: 10.1007/978-3-540-85174-5_7
[BHW15]
Allison Bishop, Susan Hohenberger, and Brent Waters. New circular security counterexamples from decision linear and learning with errors. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 776–800. 2015. Springer. DOI: 10.1007/978-3-662-48800-3_32
[CGH12]
David Cash, Matthew Green, and Susan Hohenberger. New definitions and separations for circular security. In International Workshop on Public Key Cryptography (PKC), pages 540–557. 2012. Springer. DOI: 10.1007/978-3-642-30057-8_32
[DKM+25]
Nico Döttling, Alexander Koch, Sven Maier, Jeremias Mechler, Anne Müller, Jörn Müller-Quade, and Marcel Tieplet. The Quantum Decoherence Model: Everlasting Composable Secure Computation and More. Cryptology ePrint Archive, 2025.
[DORS04]
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In EUROCRYPT 2004, volume 3027 of LNCS, pages 523–540. 2004. Springer. DOI: 10.1007/978-3-540-24676-3_31
[Dzi06]
Stefan Dziembowski. On forward-secure storage. In Annual International Cryptology Conference, pages 251–270. 2006. Springer. DOI: 10.1007/11818175_15
[GGH+16]
Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882–929, 2016. DOI: 10.1137/14095772X
[GKK+25]
Rishab Goyal, Fuyuki Kitagawa, Venkata Koppula, Ryo Nishimaki, Mahesh Sreekumar Rajasree, and Takashi Yamakawa. Non-committing Identity Based Encryption: Constructions and Applications. In IACR International Conference on Public-Key Cryptography, pages 158–193. 2025. Springer. DOI: 10.1007/978-3-031-91820-9_6
[GKRV25]
Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, and Aman Verma. Incompressible Functional Encryption. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1–56:22, Dagstuhl, Germany. 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ITCS.2025.56
[GKW17]
Rishab Goyal, Venkata Koppula, and Brent Waters. Separating semantic and circular security for symmetric-key bit encryption from the learning with errors assumption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 528–557. 2017. Springer. DOI: 10.1007/978-3-319-56614-6_18
[GM82]
Shafi Goldwasser and Silvio Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 365–377, New York, NY, USA. 1982. Association for Computing Machinery. DOI: 10.1145/800070.802212
[GMP22]
Paul Grubbs, Varun Maram, and Kenneth G Paterson. Anonymous, robust post-quantum public key encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 402–432. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_15
[GRS24]
Dhairya Gupta, Mahesh Sreekumar Rajasree, and Harihar Swaminathan. Leakage-Resilient Key-Dependent Message Secure Encryption Schemes. In International Conference on Cryptology in India, pages 234–257. 2024. Springer. DOI: 10.1007/978-3-031-80308-6_11
[GWZ22]
Jiaxin Guan, Daniel Wichs, and Mark Zhandry. Incompressible Cryptography. In EUROCRYPT 2022, volume 13275 of LNCS, pages 700–730. 2022. Springer. DOI: 10.1007/978-3-031-06944-4_24
[GWZ23]
Jiaxin Guan, Daniel Wichs, and Mark Zhandry. Multi-instance randomness extraction and security against bounded-storage mass surveillance. In TCC 2023, volume 14183 of LNCS, pages 93–122. 2023. Springer. DOI: 10.1007/978-3-031-48621-0_4
[HH09]
Iftach Haitner and Thomas Holenstein. On the (im) possibility of key dependent encryption. In Theory of Cryptography Conference (TCC), pages 202–219. 2009. Springer. DOI: 10.1007/978-3-642-00457-5_13
[HK17]
Mohammad Hajiabadi and Bruce M. Kapron. Toward fine-grained blackbox separations between semantic and circular-security notions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pages 561–591. 2017. Springer. DOI: 10.1007/978-3-319-56614-6_19
[HLH+22]
Zhengan Huang, Junzuo Lai, Shuai Han, Lin Lyu, and Jian Weng. Anonymous public key encryption under corruptions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 423–453. 2022. Springer. DOI: 10.1007/978-3-031-22969-5_15
[HSHI02]
Goichiro Hanaoka, Junji Shikata, Yumiko Hanaoka, and Hideki Imai. Unconditionally secure anonymous encryption and group authentication. In Advances in Cryptology—ASIACRYPT 2002: 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002 Proceedings 8, pages 81–99. 2002. Springer. DOI: 10.1007/3-540-36178-2_5
[JLS21]
Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 60–73. 2021. DOI: 10.1145/3406325.3451093
[KM19]
Fuyuki Kitagawa and Takahiro Matsuda. CPA-to-CCA transformation for KDM security. In Theory of Cryptography Conference (TCC) 2019, pages 118–148. 2019. Springer. DOI: 10.1007/978-3-030-36033-7_5
[KM20]
Fuyuki Kitagawa and Takahiro Matsuda. Circular security is complete for KDM security. In 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 26, pages 253–285. 2020. Springer. DOI: 10.1007/978-3-030-64837-4_9
[KMHT15]
Fuyuki Kitagawa, Takahiro Matsuda, Goichiro Hanaoka, and Keisuke Tanaka. Completeness of single-bit projection-KDM security for public key encryption. In Topics in Cryptology—CT‑RSA 2015, pages 201–219. 2015. Springer. DOI: 10.1007/978-3-319-16715-2_11
[KMT22]
Fuyuki Kitagawa, Takahiro Matsuda, and Keisuke Tanaka. CCA security and trapdoor functions via key-dependent-message security. Journal of Cryptology, 35(2):9, 2022. DOI: 10.1007/s00145-022-09420-8
[KN22]
Fuyuki Kitagawa and Ryo Nishimaki. KDM Security for the Fujisaki-Okamoto Transformations in the QROM. In IACR International Conference on Public-Key Cryptography, pages 286–315. 2022. Springer. DOI: 10.1007/978-3-030-97131-1_10
[KRW15]
Venkata Koppula, Kim Ramchen, and Brent Waters. Separations in circular security for arbitrary length key cycles. In Theory of Cryptography Conference (TCC), pages 378–400. 2015. Springer. DOI: 10.1007/978-3-662-46497-7_15
[KT18]
Fuyuki Kitagawa and Keisuke Tanaka. A framework for achieving KDM-CCA secure public-key encryption. In Advances in Cryptology–ASIACRYPT 2018, pages 127–157. 2018. Springer. DOI: 10.1007/978-3-030-03329-3_5
[KW16]
Venkata Koppula and Brent Waters. Circular Security Separations for Arbitrary Length Cycles from LWE. In Proceedings, Part II, of the 36th Annual International Cryptology Conference on Advances in Cryptology — CRYPTO 2016 - Volume 9815, Berlin, Heidelberg. 2016. Springer-Verlag. DOI: 10.1007/978-3-662-53008-5_24
[MO14]
Antonio Marcedone and Claudio Orlandi. Obfuscation=>(IND-CPA security circular security). In International Conference on Security and Cryptography for Networks (SCN), pages 77–90. 2014. Springer. DOI: 10.1007/978-3-319-10879-7_5
[Moh10]
Payman Mohassel. A closer look at anonymity and robustness in encryption schemes. In International Conference on the Theory and Application of Cryptology and Information Security, pages 501–518. 2010. Springer. DOI: 10.1007/978-3-642-17373-8_29
[MW20]
Tal Moran and Daniel Wichs. Incompressible Encodings. In CRYPTO 2020, volume 12171 of LNCS, pages 494–523. 2020. Springer. DOI: 10.1007/978-3-030-56784-2_17
[NY90]
Moni Naor and Moti Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 427–437, New York, NY, USA. 1990. Association for Computing Machinery. DOI: 10.1145/100216.100273
[PS18]
Chris Peikert and Sina Shiehian. Privately constraining and programming PRFs, the LWE way. In PKC 2018 (Part II), volume 10770 of LNCS, pages 675–701. 2018. Springer. DOI: 10.1007/978-3-319-76581-5_23
[RS91]
Charles Rackoff and Daniel R Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In Annual international cryptology conference, pages 433–444. 1991. Springer. DOI: 10.1007/3-540-46766-1_35
[Wee16]
Hoeteck Wee. KDM-security via homomorphic smooth projective hashing. In Public-Key Cryptography–PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II 19, pages 159–179. 2016. Springer. DOI: 10.1007/978-3-662-49387-8_7
[WW23]
Brent Waters and Daniel Wichs. Universal amplification of kdm security: From 1‑key circular to multi‑key kdm. In CRYPTO 2023 (Part 2), volume 14664 of LNCS, pages 674–693. 2023. Springer. DOI: 10.1007/978-3-031-38545-2_22
[YBD25]
Eylon Yogev and Shany Ben-David. Incompressible Encryption with Everlasting Security. Cryptology ePrint Archive, Paper 2025/975. 2025.
PDF
History
Submitted: 2025-01-14
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Venkata Koppula, Abhinav Kumar, Mahesh Sreekumar Rajasree, and Harihar Swaminathan, Incompressible Encryption Beyond CPA/CCA Security. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/ayfhbnja5.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.