*15:17*[Pub][ePrint] Barriers in Cryptography with Weak, Correlated and Leaky Sources, by Daniel Wichs

There has been much recent progress in constructing cryptosystems that maintain their security without requiring uniform randomness and perfect secrecy. These schemes are motivated by a diverse set of problems such as providing resilience to side-channel leakage, using weak physical sources of randomness as secret keys, and allowing deterministic encryption for high-entropy messages. The study of these problems has significantly deepened our understanding of how randomness is used in cryptographic constructions and proofs.

Nevertheless, despite this progress, some basic and seemingly achievable security properties have eluded our reach. For example, we are also unable to prove the security of basic tools for manipulating weak/leaky random sources, such as as pseudo-entropy generators and seed-dependent condensers. We also do not know how to prove leakage-resilient security of any cryptosystem that has a unique secret key for each public key. In the context of deterministic encryption, we do not have a standard-model constructions achieving the strongest notion of security originally proposed by Bellare, Boldyreva and O\'Neill (CRYPTO \'07), that allows for the encryption of arbitrarily correlated messages of sufficiently large individual entropy.

In this work, we provide broad black-box separation results, showing that the security of such primitives cannot be proven under virtually \\emph{any} standard cryptographic hardness assumption via a reduction that treats the adversary as a \\emph{black box}. We do so by formalizing the intuition that ``the only way that a reduction can simulate the correctly distributed view for an attacker is to know all the secrets, in which case it does not learn anything useful from the attack\'\'. This intuition is often misleading and subtle ways of getting around it allow us to achieve a wealth of positive results for many cryptographic primitives with imperfect randomness. However, in this work we show that this intuition can be formalized and that it indeed presents a real barrier in many special cases involving the above-mentioned examples.