Abstract
In the field of cryptography, a long-standing "folklore" belief suggests that protocols with logarithmic communication complexity—where the total number of bits exchanged is small relative to the security parameter—cannot be computationally secure unless they are also statistically secure. This intuition stems from the idea that an adversary could simply brute-force the limited message space. This paper provides a formal treatment of this intuition across various security frameworks. We prove that while the folklore holds true for Universal Composability (UC) and advantage-based models, it surprisingly fails in the stand-alone security model without auxiliary input. By constructing a protocol based on the hardness of the Set Cover problem, we demonstrate a separation between computational and statistical security in the stand-alone setting.
Introduction
The distinction between statistical security (resilience against all-powerful adversaries) and computational security (resilience against polynomial-time adversaries) is fundamental to modern cryptography. For decades, researchers have operated under the assumption that for protocols with very short messages, this distinction disappears. The logic is straightforward: if only $O(\log n)$ bits are exchanged, an attacker can enumerate all possible protocol transcripts in polynomial time. Therefore, any attack that exists in the statistical sense should be discoverable by a computationally bounded adversary.
This paper rigorously tests this intuition across three primary security models: Security with Environment (e.g., Universal Composability), Advantage-Based Security (game-theoretic models), and Stand-Alone Security. Our findings reveal that the validity of the folklore depends entirely on the specific security definitions and the presence of auxiliary input.
The Folklore Confirmed: UC and Advantage-Based Models
Our analysis begins by confirming the folklore for the most rigorous modern security definitions. In models involving an environment (such as UC) or advantage-based games, we prove that computational security indeed implies statistical security for logarithmic protocols.
Security with Environment
In the UC framework, a protocol is compared against an ideal functionality in the presence of an environment. Because the communication is logarithmic, the environment can effectively "simulate" all possible interactions. We demonstrate that an optimal adversary can be constructed in polynomial time, bridging the gap between computational and statistical limits. This is formalized in Theorem 6.
Advantage-Based Security
In game-based models, security is measured by the adversary's probability of winning a specific challenge. We model these protocols as one-player games. Since the communication is logarithmic, the resulting game tree has a polynomial number of nodes. This allows for the efficient computation of an optimal strategy using standard algorithmic techniques, confirming the folklore in Theorem 21.
The Stand-Alone Surprise
The most significant contribution of this work is the discovery that the folklore fails in the stand-alone security model when auxiliary input is not provided. We prove in Theorem 17 that there exist protocols that are computationally secure but statistically insecure in this specific setting.
The Set Cover Construction
To prove this separation, we employ a reduction from the NP-complete Set Cover problem. We construct a protocol where breaking the security requires the adversary to find a "witness" (a solution) to a hard instance of Set Cover.
Even though the messages exchanged are short, a computationally bounded adversary cannot "find" the specific sequence of messages required to break the protocol unless they can solve the underlying NP-hard problem. However, a statistically powerful adversary—unbounded by time—can find the witness and break the protocol easily. This demonstrates that short communication alone does not guarantee that a computational adversary can mimic a statistical one.
The Role of Auxiliary Input and Geometry
Why does the folklore fail in the stand-alone model but hold elsewhere? The answer lies in the adversary's resources. We show in Theorem 18 that if the adversary is given non-uniform auxiliary input (a "cheat sheet" containing the witness), the gap disappears. Most modern cryptographic proofs assume non-uniform adversaries, which explains why this counter-example had not been previously prioritized.
Adversary-Polytopes
To facilitate these proofs, we introduce a novel geometric approach. We represent the set of possible probability distributions of a protocol's output as a geometric shape known as a polytope. By analyzing the "space" of these polytopes, we can visualize security properties: finding a successful adversary becomes equivalent to finding a point in one polytope that is sufficiently distant from another. This geometric lens provides a new way to reason about the limits of adversarial power.
Conclusion
Our research clarifies the relationship between communication complexity and security. While the folklore belief that "logarithmic communication implies statistical security" is a reliable rule of thumb for UC and advantage-based models, it is not a universal law of cryptography. The stand-alone model without auxiliary input allows for a unique gap where computational hardness can be preserved despite minimal communication. These results highlight the importance of precise model selection when making claims about the fundamental limits of cryptographic protocols.
Summary updated