Paper 2007/169

On the Security of Protocols with Logarithmic Communication Complexity

Michael Backes and Dominique Unruh

Abstract

We investigate the security of protocols with logarithmic communication complexity. We show that for the security definitions with environment, i.e., Reactive Simulatability and Universal Composability, computational security of logarithmic protocols implies statistical security. The same holds for advantage-based security definitions as commonly used for individual primitives. While this matches the folklore that logarithmic protocols cannot be computationally secure unless they are already statistically secure, we show that under realistic complexity assumptions, this folklore does surprisingly not hold for the stand-alone model without auxiliary input, i.e., there are logarithmic protocols that are statistically insecure but computationally secure in this model. The proof is conducted by showing how to transform an instance of an NP-complete problem into a protocol with two properties: There exists an adversary such that the protocol is statistically insecure in the stand-alone model, and given such an adversary we can find a witness for the problem instance, hence yielding a computationally secure protocol assuming the hardness of finding a witness. The proof relies on a novel technique that establishes a link between cryptographic definitions and foundations of computational geometry, which we consider of independent interest.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
complexity theory
Contact author(s)
unruh @ cs uni-sb de
History
2007-05-07: received
Short URL
https://ia.cr/2007/169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/169,
      author = {Michael Backes and Dominique Unruh},
      title = {On the Security of Protocols with Logarithmic Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2007/169},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/169}},
      url = {https://eprint.iacr.org/2007/169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.