Paper 2014/337

Related Randomness Attacks for Public Key Encryption

Kenneth G. Paterson, Jacob C. N. Schuldt, and Dale L. Sibborn


Several recent and high-profile incidents give cause to believe that randomness failures of various kinds are endemic in deployed cryptographic systems. In the face of this, it behoves cryptographic researchers to develop methods to immunise - to the extent that it is possible - cryptographic schemes against such failures. This paper considers the practically-motivated situation where an adversary is able to force a public key encryption scheme to reuse random values, and functions of those values, in encryption computations involving adversarially chosen public keys and messages. It presents a security model appropriate to this situation, along with variants of this model. It also provides necessary conditions on the set of functions used in order to attain this security notation, and demonstrates that these conditions are also sufficient in the Random Oracle Model. Further standard model constructions achieving weaker security notions are also given, with these constructions having interesting connections to other primitives including: pseudo-random functions that are secure in the related key attack setting; Correlated Input Secure hash functions; and public key encryption schemes that are secure in the auxiliary input setting (this being a special type of leakage resilience).

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2014
Contact author(s)
kenny paterson @ rhul ac uk
2014-05-15: received
Short URL
Creative Commons Attribution


      author = {Kenneth G.  Paterson and Jacob C. N.  Schuldt and Dale L.  Sibborn},
      title = {Related Randomness Attacks for Public Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/337},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.