Weakening the Perfect Encryption Assumption in Dolev-Yao Adversaries

We consider secrecy and authentication in a simple process calculus with cryptographic primitives. The standard Dolev–Yao adversary is enhanced so that it can guess the key required to decrypt an intercepted message. We borrow from the computational complexity approach the assumptions that guessing succeeds with a given negligible probability and that the resources available to adversaries are polynomially bounded. Under these hypotheses we prove that the standard Dolev–Yao adversary is as powerful as the enhanced one.