Skip to content
Preprint

Decidability of Parameterised Dolev-Yao Secrecy

Aug 2026 · 0 citations · 24 references
Computer Science

TL;DR

A cut-off theorem is obtained: secrecy violations in systems with arbitrarily many sessions are always witnessed in systems of bounded size, so secrecy also reduces to a coverability problem in WSTS.

Abstract

We study the verification of parameterised secrecy for cryptographic protocols in the Dolev-Yao model, where the number of protocol sessions is unbounded and treated as a parameter. This differs fundamentally from classical Dolev-Yao secrecy, which asks whether a protocol leaks a secret irrespective of the number of executions; our question is whether secrecy holds uniformly across all system sizes, where such a size is a parameter. This parameterised perspective captures how attacks scale with the number of participants and provides a formal basis for the empirical effectiveness of small-instance analysis. Secrecy (parameterised or not) is undecidable in general, even under bounded freshness or bounded message size. We identify two structural restrictions that make parameterised secrecy decidable: (i) global bounded freshness per role, and (ii) a Dolev-Yao intruder restricted to well-typed substitutions. Under these assumptions, protocol executions admit a finite representation up to a collapsing map on agents and terms. Our main result is that parameterised secrecy is decidable in this setting. We obtain a cut-off theorem: secrecy violations in systems with arbitrarily many sessions are always witnessed in systems of bounded size. The cut-off is self-contained; more strongly, the induced transition system forms a well-structured transition system (WSTS) under a bound-based ordering, so secrecy also reduces to a coverability problem in WSTS. This provides a structural explanation for the existence of finite witnesses in symbolic protocol analysis and connects Dolev-Yao verification with parameterised verification techniques.

View source

Similar papers

Preprint Aug 2026

Rational Dolev--Yao Attackers: Decidable Incentive-Aware Verification of Security Protocols in Strategic Logic

A rational Dolev--Yao attacker is introduced, a DY intruder whose actions carry costs and whose security-violating goals carry rewards, and a protocol is called rationally secure when no intruder strategy achieves a violation with strictly positive utility, expressed in a weighted fragment of ATL (WATL).

Ioana Boureanu, R. Ramanujam · 0 citations
Preprint Sep 2026

Scalable Composition of Byzantine Agreements under Reorder Attacks

This work provides general black-box compilers that transform any single-instance secure BA protocol into one that is secure under parallel and concurrent executions without additional security assumptions, and designs refined compilers using erasure-correcting codes to optimize performance.

Jing Chen, Jin Dong, Ji-Chen Li et al. · 0 citations

Checking Leakage Witnesses versus Certifying Bounded Non-Leakage

When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is...

Chao Feng, Burkhard Stiller · 0 citations
Preprint Sep 2026

Fresh-Challenge VDF Attestations for Model-Relative Response Latency

Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? Verifiable delay functions (VDFs) make this possible in principle: evaluation requires T sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in the numerical valu...

Ansar Yesmukhanov, Aruzhan Tlessova · 1 citation
Preprint Sep 2026

Keyless secrecy against bounded adversaries

The first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, is obtained, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.

Anne Broadbent, Upendra S. Kapshikar, Denis Rochette · 0 citations
Preprint Aug 2026

Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions

Quantum indistinguishability obfuscation (qIO) aims to make a quantum circuit unintelligible while preserving its functionality. It serves as a foundational primitive for advanced applications, such as witness encryption (WE) for QMA, non-interactive zero-knowledge arguments for QMA, and attribute-based encryption for...

Mohammed Barhoush, T. Morimae, R. Movassagh · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.