We enlarge the scope of current work on the problem by permitting adversarial subversion of (randomized) key generation; in particular, we initiate the study of cryptography in the complete subversion model, where all relevant cryptographic primitives are subject to kleptographic attacks. We construct secure one-way permutations and trapdoor one-way permutations in this “complete subversion” model, describing a general, rigorous immunization strategy to clip the power of kleptographic subversions. Our strategy can be viewed as a formal treatment of the folklore “nothing up my sleeve” wisdom in cryptographic practice. We also describe a related “split program” model that can directly inform practical deployment. We additionally apply our general immunization strategy to directly yield a backdoor-free PRG. This notably amplifies previous results of Dodis, Ganesh, Golovnev, Juels, and Ristenpart [Eurocrypt ’15], which require an honestly generated random key. We then examine two standard applications of (trapdoor) one-way permutations in this complete subversion model and construct “higher level” primitives via black-box reductions. We showcase a digital signature scheme that preserves existential unforgeability when all algorithms (including key generation, which was not considered to be under attack before) are subject to kleptographic attacks. Additionally, we demonstrate that the classic Blum– Micali pseudorandom generator (PRG), using an “immunized” one-way permutation, yields a backdoor-free PRG.
Alongside development of these secure primitives, we set down a hierarchy of kleptographic attack models which we use to organize past results and our new contributions; this taxonomy may be valuable for future work.Category / Keywords: foundations / kleptography, massive surveiliance, cliptogrpahy Date: received 10 Jul 2015, last revised 21 May 2016 Contact author: acr at cse uconn edu; qtang84@gmail com; motiyung@gmail com; hszhou@vcu edu Available format(s): PDF | BibTeX Citation Version: 20160521:095407 (All versions of this report) Short URL: ia.cr/2015/695 Discussion forum: Show discussion | Start new discussion