Space-Efficient Kleptography Without Random Oracles

In the past, hiding asymmetric backdoors inside cryptosystems required a random oracle assumption (idealization) as “randomizers” of the hidden channels. The basic question left open is whether cryptography itself based on traditional hardness assumption(s) alone enables “internal randomized channels” that enable the embedding of an asymmetric backdoor inside another cryptosystem while retaining the security of the cryptosystem and the backdoor (two security proofs in one system). This question translates into the existence of kleptographic channels without the idealization of random oracle functions. We therefore address the basic problem of controlling the probability distribution over information (i.e., the kleptogram) that is hidden within the output of a cryptographic system. We settle this question by presenting an elliptic curve asymmetric backdoor construction that solves this problem. As an example, we apply the construction to produce a provably secure asymmetric backdoor in SSL. The construction is general and applies to many other kleptographic settings as well.