Paper 2005/406

Relations amount Statistical Security Notions - or - Why Exponential Adversaries are Unlimited

Dominique Unruh

Abstract

In the context of Universal Composability, we introduce the concept of universal environments and simulators. Then, Universal Composability is equivalent to Universal Composability wrt. universal environments and simulators. We prove the existence of universal environments and simulators and investigate their computational complexity. From this, we get a number of consequences: First, we see that for polynomial-time protocols, exponential adversarial entities are as powerful as unlimited ones. Further, for a large class of protocols (those with bounded communication-complexity) we can show that UC and specialised-simulator UC coincide in the case of statistical security, i.e., that it is does not matter whether the simulator is chosen in dependence of the environment or not. This also implies that for the Universal Composition Theorem for polynomial-time protocols specialised-simulator UC is sufficient. This result is the last piece needed to find all implications and non-implications between the notions of UC, specialised-simulator UC, O(1)-bounded and polynomially-bounded general composability for polynomial-time protocols in the cases of perfect, statistical and polynomial security. Finally, we introduce the notion of bounded-risk UC, which allows to give explicit security guarantees for concrete security parameters and show that in the above case also this variant coincides with UC.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
secure multi-party computationprotocol compositionuniversal composabilitygeneral compositioncomplexity theory
Contact author(s)
unruh @ ira uka de
History
2005-11-15: received
Short URL
https://ia.cr/2005/406
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/406,
      author = {Dominique Unruh},
      title = {Relations amount Statistical Security Notions - or - Why Exponential Adversaries are Unlimited},
      howpublished = {Cryptology ePrint Archive, Paper 2005/406},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/406}},
      url = {https://eprint.iacr.org/2005/406}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.