Another look at security definitions

Neal Koblitz and Alfred Menezes
Advances in Mathematics of Communications, 7 (2013), 1-38.

Abstract: We take a critical look at security models that are often used to give "provable security" guarantees. We pay particular attention to digital signatures, symmetric-key encryption, and leakage resilience. We find that there has been a surprising amount of uncertainty about what the "right" definitions might be. Even when definitions have an appealing logical elegance and nicely reflect certain notions of security, they fail to take into account many types of attacks and do not provide a comprehensive model of adversarial behavior.

Journal paper       Eprint paper

Publication information: The paper has three distinctions:
  1. It was published despite receiving very unfavourable reports from both referees; for further details, see the editorial by Marcus Greferath, the editor-in-chief of Advances in Mathematics of Communications.
  2. Both authors were invited to serve on the journal's editorial board immediately after the paper had been accepted.
  3. To the best of our knowledge, it is the first published paper in cryptography to use the "f" word (three times). Note, however, that the "f" word had already been used in a CRYPTO 2012 Rump Session presentation by Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman.

Related material:
  • Burdens of Proof: Cryptographic Culture and Evidence Law in the Age of Electronic Documents, by Jean-François Blanchette, MIT Press, 2012.
    Using the case of digital signatures, this book examines the gaps that often arise between the security assurances claimed for cryptographic protocols and the actual information security needs of an electronic world. The author argues that "the yearning for the moral authority provided by `provable security' has marginalized research on phenomena less amenable to mathematical formalization, but with the potential for greater social impact."
  • Review by William Whyte.