*18:11*[Pub][ePrint] Cliptography: Clipping the Power of Kleptographic Attacks, by Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou

Kleptography, originally introduced by Young and Yung [Crypto \'96],

studies how to steal information securely and subliminally from cryptosystems.

Secure cryptosystems can be broken if they are maliciously implemented

since the adversary may have some backdoors embedded in the implementation.

Although kleptographic attacks have been investigated about two decades ago,

for too long the possibility of kleptographic attacks have been dismissed and

been viewed only as a far-fetched theoretical concept.

This is dramatically changed when real-world examples were recently revealed

by Edward Snowden, demonstrating that such deliberate attacks

(directly inspired by the original work) exist and probably have been used for massive surveillance. In light of such possible failures of basic protective technology,

the security community started to seriously re-investigate this important issue: one notable example is the work of

Bellare, Paterson, and Rogaway [Crypto \'14], which initiated the formal studies of attacks on symmetric key encryption algorithms.

Motivated by the original examples of subverting key generation algorithms in the kleptography papers from Young and Yung [Crypto \'96, Eurocrypt \'97], we initiate the study of cryptography in the case that {\\em all} algorithms are subject to kleptographic attacks---we call it {\\bf cliptography}. As a first step, we formally study the fundamental primitives of one-way function and trapdoor one-way function in this complete subversion model. And more interesting, we investigate the general immunization strategy to clip the power of kleptographic subversions; concretely, we propose a general framework for sanitizing the (trapdoor) one-way function generation algorithm by hashing the function index, and prove that such procedure indeed destroys the connection between a subverted function generation procedure and any possible backdoor. Along the way, we propose a split program model for practical deployment.

We then examine the applications of (trapdoor) one way function secure in the complete subversion model in two ways. First we consider to build ``higher level\" primitives via black-box reductions. In particular, we consider how to use our trapdoor one-way function to defend against key generation sabotage, and showcase a digital signature scheme that preserves existential unforgeability when {\\em all} algorithms (including key generation, which was not considered to be under attack before) are subject to kleptographic attacks.

Also we demonstrate that the classic Blum-Micali pseudorandom generator (PRG) using our ``unforgeable\" one-way function yields a backdoor-free PRG. Second, we generalize our immunizing technique for one way functions, and

propose a new public immunization strategy to randomize the public parameters of a (backdoored) PRG. Since the previous result by Dodis, Ganesh, Golovnev, Juels, and Ristenpart~[Eurocrypt \'15] requires an honestly generated random key, construction of secure PRG in the complete subversion model was also open until our paper.