International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On the Security of Protocols with Logarithmic Communication Complexity

Michael Backes
Dominique Unruh
Search ePrint
Search Google
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.
  title={On the Security of Protocols with Logarithmic Communication Complexity},
  booktitle={IACR Eprint archive},
  keywords={foundations / complexity theory},
  note={ 13640 received 7 May 2007},
  author={Michael Backes and Dominique Unruh},