POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

In simulation-based security, a protocol realizes a secure ideal functionality if no adversary can distinguish between the two. Establishing this indistinguishability is challenging: even in the simplified symbolic (Dolev-Yao) model, one must reason about asynchronous execution and adversarial interaction. Prior work addresses this challenge by imposing strong protocol restrictions, such as structural equivalence. However, these restrictions preclude many protocols of interest: in a simulation-based security proof, the protocol and ideal functionality are often structurally distinct. In this paper, we propose a novel technique to prove symbolic indistinguishability for a broader class of protocols that combines Fernandez and Mounier’s w-bisimulation with a Lipton-style right-moving transition-partitioning reduction. W-bisimulation lets us handle asynchronous adversarial interaction by relating only the barrier states, i.e., states after observable transitions, whereas Lipton-style reduction allows us to generalize the symbolic indistinguishability reasoning to unbounded protocol concurrency in a semi-commutative setting. We prove our proof technique sound in Lean. Finally, we introduce Doppel, an F* framework that mechanizes this technique, and demonstrate its effectiveness through two case studies — including the proof that a Needham-Schroeder-Lowe (NSL) protocol realizes ideal mutual authentication. Each case study yields the first direct, mechanized simulation-style security proof for its protocol in a symbolic model.