Paper 2006/323

Computational Soundness of Formal Indistinguishability and Static Equivalence

Gergei Bana, Payman Mohassel, and Till Stegers

Abstract

In the research of the relationship between the formal and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of formal indistinguishability. Previous work has shown that this yields the soundness of natural interpretations of some interesting equational theories, such as certain cryptographic operations and a theory of XOR. In this paper however, we argue that static equivalence is too coarse for sound interpretations of equational theories in general. We show some explicit examples how static equivalence fails to work in interesting cases. To fix this problem, we propose a notion of formal indistinguishability that is more flexible than static equivalence. We provide a general framework along with general theorems, and then discuss how this new notion works for the explicit examples where static equivalence failed to ensure soundness. We also improve the treatment by using ordered sorts in the formal view, and by allowing arbitrary probability distributions of the interpretations.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. A shorter version was presented at ASIAN 2006.
Keywords
formal methodcomputational methodsoundness
Contact author(s)
bana @ math upenn edu
History
2007-01-09: revised
2006-09-26: received
See all versions
Short URL
https://ia.cr/2006/323
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/323,
      author = {Gergei Bana and Payman Mohassel and Till Stegers},
      title = {Computational Soundness of Formal Indistinguishability and Static Equivalence},
      howpublished = {Cryptology ePrint Archive, Paper 2006/323},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/323}},
      url = {https://eprint.iacr.org/2006/323}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.