International Association
for Cryptologic Research

A receiver non-committing encryption (RNCE) scheme ~\cite{CFGN96,CHK05} allows one to sample a public key pk and (dummy) ciphertext ct without knowing the message m. Later, when the message is known, one can sample a secret key sk that looks like the secret key corresponding to pk, and decryption of ct produces m. In this work, we study receiver non-committing identity-based encryption (RNC-IBE). We give constructions based on standard assumptions on bilinear groups (prior works~\cite{HMNY21} require indistinguishability obfuscation). Our RNC-IBE constructions have important implications for incompressible identity based encryption. This notion was recently introduced ~\cite{GKRV24}. However, there were no constructions for the strongest security definitions in ~\cite{GKRV24}. Our RNC-IBE scheme also leads to the first incompressible IBE scheme with optimal ciphertext size, which was another open question in \cite{GKRV24}. We also give constructions for relaxed RNC-IBE (where the identity space is polynomial in the security parameter, but the public key is compact) that are based on DDH, LWE. This leads to a relaxed incompressible IBE scheme with strong security from the same assumptions.

We present the first construction for adaptively secure HIBE, that does not rely on bilinear pairings or random oracle heuristics. Notably, we design an adaptively secure HIBE from any selectively secure IBE system in the standard model. Combining this with known results, this gives the first adaptively secure HIBE system from a wide variety of standard assumptions such as CDH/Factoring/LWE/LPN. We also extend our adaptively secure HIBE system to satisfy full anonymity, giving the first adaptively secure anonymous HIBE under CDH/LWE assumption. All our HIBE systems support unbounded length identities as well as unbounded number of recursive delegation operations.

Pseudorandom codes (PRCs) are error-correcting codes with the distinguishing feature that their codewords are computationally indistin- guishable from random strings. Introduced by Christ and Gunn (CRYPTO 2024), PRCs have found applications in areas such as AI watermarking, where both robustness and pseudorandomness are essential. All known constructions of PRCs rely on coding-theoretic hardness assumptions. In this work, we study how inherent the use of coding-theoretic hardness is in the construction of pseudorandom codes. We show that there is no black-box construction of PRCs with binary alpha- bets capable of decoding from a constant fraction of Bernoulli noise from a class of oracles we call local oracles. The class of local oracles includes random oracles and trapdoor permutation oracles, and can be interpreted as a meaningful notion of oracles that are not resilient against noise. Our separation result is cast in the Impagliazzo-Rudich framework and crucially relies on the Bonami-Beckner hypercontractivity theorem on the Boolean hypercube. As a complementary result, we show that PRCs with large alphabets that can tolerate high error rates can indeed be constructed in a black-box man- ner from one-way functions.

We introduce Leakage-Resilient Incompressible cryptography, which simultaneously addresses two variants of side-channel attacks that have been tackled in theoretical cryptography. Leakage-resilience seeks to provide security against an adversary who learns a part of the secret-key and the entire ciphertext or signature; conversely, incompressible cryptography provides security against an adversary who learns the entire secret-key, but only a part of the ciphertext or signature. However, constructions in either of these security models can fail against an attack in the other model. In this work, we define a new model of security that subsumes both leakage-resilient cryptography and incompressible cryptography, and we present several non-trivial positive and negative results. On the positive side, first we present a transformation from incompressible symmetric-key encryption (SKE) to leakage-resilient incompressible SKE in the information-theoretic setting. Next, as one of our main results, we construct a leakage-resilient incompressible public-key encryption (PKE), combining an incompressible SKE and a new primitive that we call leakage-resilient non-committing key encapsulation mechanism (LR-NC-KEM). While an incompressible SKE suitable for use in both these constructions already exists in the literature (Dziembowski, CRYPTO 2006), we present a new construction with better parameters, using an appropriate notion of invertible extractors; this leads to corresponding improvements in the final parameters we obtain in these constructions. We also design a leakage-resilient incompressible signature scheme. On the negative side, we show barriers to significantly improving the parameters we obtain, by showing impossibility of basing the security of such improved schemes on blackbox reductions. Apart from the general framework and the specific results we obtain, some of the intermediate tools that we define and instantiate, like LR-NC-KEM and invertible extractors, may be of independent interest.