Related Randomness Attacks for Public Key Encryption

Kenneth G.  Paterson; Jacob C. N.  Schuldt; Dale L.  Sibborn

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/337

Related Randomness Attacks for Public Key Encryption

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

Abstract

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).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in PKC 2014
Contact author(s): kenny paterson @ rhul ac uk
History: 2014-05-15: received
Short URL: https://ia.cr/2014/337
License: CC BY

BibTeX

@misc{cryptoeprint:2014/337,
      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{https://eprint.iacr.org/2014/337}},
      url = {https://eprint.iacr.org/2014/337}
}