Paper 2015/695

Cliptography: Clipping the Power of Kleptographic Attacks

Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou


Kleptography, introduced 20 years ago by Young and Yung [Crypto ’96], considers the (in)security of malicious implementations (or instantiations) of standard cryptographic prim- itives that embed a “backdoor” into the system. Remarkably, crippling subliminal attacks are possible even if the subverted cryptosystem produces output indistinguishable from a truly secure “reference implementation.” Bellare, Paterson, and Rogaway [Crypto ’14] recently initiated a formal study of such attacks on symmetric key encryption algorithms, demonstrating a kleptographic attack can be mounted in broad generality against randomized components of cryptographic systems. 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.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2016
kleptographymassive surveiliancecliptogrpahy
Contact author(s)
acr @ cse uconn edu
qtang84 @ gmail com
motiyung @ gmail com
hszhou @ vcu edu
2017-11-25: last of 8 revisions
2015-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Russell and Qiang Tang and Moti Yung and Hong-Sheng Zhou},
      title = {Cliptography: Clipping the Power of Kleptographic Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/695},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.