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.
Joint Session with Logic and Computation Seminar
