**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.

**Permalink:** http://www.ut.ee/~unruh/publications/backes07security.html