On the Security of Protocols with Logarithmic Communication Complexity

Michael Backes, Dominique Unruh

TL;DR

This paper investigates a long-standing "folklore" belief in cryptography: that protocols with very short (logarithmic) messages cannot be computationally secure unless they are already statistically secure. The authors prove this is true for most modern security frameworks (like Universal Composability), but surprisingly show it is false for the stand-alone security model without auxiliary input, where they construct a protocol that is computationally secure but statistically broken.

What Problem Does This Paper Address?

In cryptography, we distinguish between statistical security (secure even against an infinitely powerful attacker) and computational security (secure against attackers with limited time/memory). A common intuition—the "folklore"—suggests that if a protocol only exchanges a few bits (logarithmic in the security parameter), an attacker can simply brute-force every possible message. Therefore, any such protocol that is computationally secure must also be statistically secure because the "computational" limit doesn't actually restrict the attacker's ability to see everything.

The authors set out to formally test this intuition across three major security models:

  1. Security with Environment: (e.g., Universal Composability or Reactive Simulatability), which looks at protocols running alongside other arbitrary processes.
  2. Advantage-Based Security: Which focuses on the probability of an adversary winning a specific "game" (like guessing an encrypted bit).
  3. Stand-Alone Security: A model where the protocol is analyzed in isolation.

Methods

The paper employs a mix of complexity theory, game theory, and a novel geometric approach:

  • Geometric Reductions (Adversary-Polytopes): To analyze stand-alone security, the authors represent the set of possible probability distributions of a protocol's output as a geometric shape called a polytope. They show that finding a "good" adversary is equivalent to finding a point in one polytope that is far from another.
  • NP-Complete Reductions: They prove the separation in the stand-alone model by reducing the Set Cover problem to the task of finding a successful adversary. They construct a protocol where a "witness" (solution) to a hard Set Cover instance is required to break the protocol. If the problem is hard, the protocol is computationally secure, even if it is statistically insecure.
  • Game Theory: For advantage-based security, they model the protocol as a one-player game. Since the communication is logarithmic, the "game tree" is only polynomial in size, allowing them to show that an optimal strategy can be efficiently computed.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, it relies on mathematical proofs and complexity assumptions (e.g., $NP \not\subseteq BPTIME(n^{O(\log n)})$) rather than empirical datasets.

Key Insights and Ideas

  • The Folklore is Mostly Right: The authors confirm that for the most rigorous modern definitions (UC and Advantage-based), computational security does indeed imply statistical security for logarithmic protocols. This is because an environment or a game-player can "guess" the right messages with high enough probability to bridge the gap.
  • The Stand-Alone Surprise: The "folklore" fails in the stand-alone model without auxiliary input. In this specific setting, even though the messages are short, an efficient adversary might not be able to "find" the specific sequence of messages needed to break the protocol unless they can solve an NP-complete problem.
  • The Role of Auxiliary Input: The authors show that the gap disappears if the adversary is given non-uniform auxiliary input. If the attacker has a "cheat sheet" (the witness to the NP problem), they can break the protocol, reuniting computational and statistical security.
  • Bridging Geometry and Crypto: The use of polytopes to define security properties is a novel technique introduced here, providing a visual and mathematical way to reason about the "space" of possible adversarial attacks.

Key Results

  • Theorems 6 & 21: Formally prove that for Security with Environment and Advantage-Based Security, computational security $\implies$ statistical security for logarithmic protocols.
  • Theorem 17: Proves that Computational Stand-Alone Security does NOT imply statistical security (assuming certain complexity-theoretic hard instances exist).
  • Theorem 18: Proves that if you add non-uniform auxiliary input to the stand-alone model, the implication holds again.
  • Efficiency: The authors demonstrate that for logarithmic protocols in the UC/Advantage models, an optimal (or near-optimal) adversary can be constructed in polynomial time.

Limitations and Future Work

  • Complexity Assumptions: The counter-example in the stand-alone model relies on the assumption that certain NP problems are hard to solve even in quasi-polynomial time. While widely believed, these are unproven.
  • Non-Uniformity: The separation only exists in the "uniform" setting. Most modern cryptographic proofs assume non-uniform adversaries (who can have "built-in" advice), which would nullify the authors' counter-example.
  • Geometric Artifacts: The authors note that a specific factor in their geometric proof (a $3^{-r}$ reduction in statistical distance) might be an artifact of their proof method rather than a fundamental limit, suggesting a potential area for refinement.

Summary updated

BibTeX
@article{backes2007security,
  author = {Michael Backes and Dominique Unruh},
  title = {{On the Security of Protocols with Logarithmic Communication Complexity}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2007},
  url = {https://openreview.net/forum?id=WYX3M5ilLl},
}
Figure