Overview
The study addresses the intruder deduction problem within symbolic security-protocol analysis, which concerns an attacker's ability to derive a target message from observed messages using available cryptographic operators. While convergent rewrite systems offer canonical normal forms, general deduction modulo convergent theories remains undecidable. Existing decidable fragments are frequently influenced by practical cryptographic examples. This work examines deduction from a minimal structural perspective, specifically when all function symbols are unary.
Research Context
In symbolic security-protocol analysis, the intruder deduction problem involves determining if an attacker can deduce a specific target message from a set of observed messages. This deduction is performed using cryptographic operators accessible to the attacker. Convergent rewrite systems are known for providing canonical normal forms. However, deduction within convergent theories, in a general sense, is undecidable. Decidable fragments that do exist are often tailored based on specific practical cryptographic scenarios.
Approach
The researchers adopted a minimal structural perspective to investigate the deduction problem. This involved a specific focus on scenarios where all function symbols are unary. Under this condition, terms simplify to words, transforming the deduction problem into a right-divisibility problem for semi-Thue systems. The core question becomes: given words $u$ and $v$, does there exist a word $w$ such that $wu \equiv_S v$?
The investigation proceeded by examining this right-divisibility problem across several classes of semi-Thue systems. Subsequently, the perspective was extended to term rewriting systems. These extended systems feature rules that erase contexts while simultaneously lifting selected subterms or variables.
Findings
- For semi-Thue systems where all function symbols are unary, the deduction problem becomes a right-divisibility problem: given words $u$ and $v$, determine if there exists a word $w$ such that $wu \equiv_S v$.
- New decidability results were established for the right-divisibility problem in convergent prefix-erasing systems.
- New decidability results were also established for the right-divisibility problem in convergent suffix-erasing systems.
- The study extended its scope to term rewriting systems where rules erase contexts and lift specific subterms or variables.
- Despite the potential for decidable generalizations suggested by these classes beyond the unary setting, deduction was found to be undecidable for a convergent simultaneous variable-lifting system.
Why This Matters
The findings expose both the potential for extending right-divisibility results to richer equational theories and the inherent limits of such extensions. This contributes to understanding the boundaries of decidability in symbolic security-protocol analysis and related computational problems.