Computationally Sound Symbolic Secrecy in the Presence of Hash Functions

Computationally Sound Symbolic Secrecy in the Presence of Hash Functions. Véronique Cortier, Steve Kremer, Ralf Küsters, and Bogdan Warinschi. In Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'06), pp. 176–187, Lecture Notes in Computer Science 4337, Springer, Kolkata, India, December 2006.

Download

[PDF] [HTML]

Abstract

The standard symbolic, deducibility-based notions of secrecy are in general insufficient from a cryptographic point of view, especially in presence of hash functions. In this paper we devise and motivate a more appropriate secrecy criterion which exactly captures a standard cryptographic notion of secrecy for protocols involving public-key enryption and hash functions: protocols that satisfy it are computationally secure while any violation of our criterion directly leads to an attack. Furthermore, we prove that our criterion is decidable via an NP decision procedure. Our results hold for standard security notions for encryption and hash functions modeled as random oracles.

BibTeX

@inproceedings{CKKW-fsttcs2006,
  address =       {Kolkata, India},
  author =        {Cortier, V{\'e}ronique and Kremer, Steve and
                   K{\"u}sters, Ralf and Warinschi, Bogdan},
  booktitle =     {{P}roceedings of the 26th {C}onference on
                   {F}oundations of {S}oftware {T}echnology and
                   {T}heoretical {C}omputer {S}cience ({FSTTCS}'06)},
  editor =        {Garg, Naveen and Arun-Kumar, S.},
  month =         dec,
  pages =         {176-187},
  publisher =     {Springer},
  series =        {Lecture Notes in Computer Science},
  title =         {Computationally Sound Symbolic Secrecy in the
                   Presence of Hash Functions},
  volume =        {4337},
  year =          {2006},
  abstract =      {The standard symbolic, deducibility-based notions of
                   secrecy are in general insufficient from a
                   cryptographic point of view, especially in presence
                   of hash functions. In~this paper we devise and
                   motivate a more appropriate secrecy criterion which
                   exactly captures a standard cryptographic notion of
                   secrecy for protocols involving public-key enryption
                   and hash functions: protocols that satisfy it are
                   computationally secure while any violation of our
                   criterion directly leads to an attack. Furthermore,
                   we prove that our criterion is decidable via an NP
                   decision procedure. Our~results hold for standard
                   security notions for encryption and hash functions
                   modeled as random oracles.},
  doi =           {10.1007/11944836_18},
}