Information Security Seminar 

14/11/2008, 16:15 — 17:15 — Room P3.10, Mathematics Building
Gergei Bana, SQIG-IT

Computational Soundness of Symbolic Indistinguishability and Static Equivalence

In the research of the relationship between the symbolic and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of symbolic 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. However, we argue that static equivalence is too coarse to allow sound interpretations of many natural and useful equational theories. We illustrate this with several explicit examples in which static equivalence fails to work. To fix the problem, we propose a notion of symbolic indistinguishability that is more flexible than static equivalence. We provide general results, and then discuss how this new notion works for the explicit examples where static equivalence fails to ensure soundness. Joint work with P. Mohassel and T. Stegers.