Guessing Attacks and the Computational Soundness of Static Equivalence

Martin Abadi, Mathieu Baudet, Bogdan Warinschi

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

30 Citations (Scopus)


The indistinguishability of two pieces of data (or two lists of pieces of data) can be represented formally in terms of a relation called static equivalence. Static equivalence depends on an underlying equational theory. The choice of an inappropriate equational theory can lead to overly pessimistic or overly optimistic notions of indistinguishability, and in turn to security criteria that require protection against impossible attacks or---worse yet---that ignore feasible ones. In this paper, we define and justify an equational theory for standard, fundamental cryptographic operations. This equational theory yields a notion of static equivalence that implies computational indistinguishability. Static equivalence remains liberal enough for use in applications. In particular, we develop and analyze a principled formal account of guessing attacks in terms of static equivalence.
Translated title of the contributionGuessing Attacks and the Computational Soundness of Static Equivalence
Original languageEnglish
Title of host publicationFoundations of Software Science and Computational Structures - FOSSACS 2006
PublisherSpringer Berlin Heidelberg
Publication statusPublished - 2006

Bibliographical note

Other page information: -
Conference Proceedings/Title of Journal: Foundations of Software Science and Computational Structures -- FOSSACS'06
Other identifier: 2000655

Cite this