2026-07-24T02:57:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22684 2026-04-17T05:32:17Z ddc:004 open_access

Incompressible Functional Encryption Goyal, Rishab Koppula, Venkata Rajasree, Mahesh Sreekumar Verma, Aman functional encryption attribute-based encryption incompressible encryption Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a ciphertext within pre-specified memory bound S before receiving the secret key. In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the ciphertext to within S bits. An important efficiency measure for incompressible encryption is the ciphertext-rate (i.e., rate = |m|/|ct|). We give many new results for incompressible functional encryption for circuits, from minimal assumption of (non-incompressible) functional encryption, with 1) ct-rate-1/2 and short secret keys, 2) ct-rate-1 and large secret keys. Along the way, we also give a new incompressible attribute-based encryption for circuits from standard assumptions, with ct-rate-1/2 and short secret keys. Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with ct-rate-1 as well as short secret keys has strong barriers for provable security from standard assumptions. Moreover, our assumptions are minimal as incompressible attribute-based/functional encryption are strictly stronger than their non-incompressible counterparts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rishab Goyal and Venkata Koppula and Mahesh Sreekumar Rajasree and Aman Verma 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.56 urn:nbn:de:0030-drops-226849 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.56 eng https://creativecommons.org/licenses/by/4.0/legalcode