Cryptology ePrint Archive: Report 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.
Category / Keywords: foundations / complexity theory
Date: received 7 May 2007
Contact author: unruh at cs uni-sb de
Available format(s): PDF | BibTeX Citation
Version: 20070507:211846 (All versions of this report)
Short URL: ia.cr/2007/169
[ Cryptology ePrint archive ]