Accession Number:

ADA465155

Title:

Interpreting Strands in Linear Logic

Descriptive Note:

Corporate Author:

NAVAL RESEARCH LAB WASHINGTON DC

Report Date:

2000-01-01

Pagination or Media Count:

13.0

Abstract:

The adoption of the Dolev-Yao model, an abstraction of security protocols that supports symbolic reasoning, is responsible for many successes in protocol analysis. In particular, it has enabled using logic effectively to reason about protocols. One recent framework for expressing the basic assumptions of the Dolev-Yao model is given by strand spaces, certain directed graphs whose structure reflects causal inter- actions among protocol participants. We represent strand constructions as relatively simple formulas in first-order linear logic, a refinement of traditional logic known for an intrinsic and natural accounting of process states, events, and resources. The proposed encoding is shown to be sound and complete. Interestingly, this encoding differs from the multiset rewriting definition of the Dolev-Yao model, which is also based on linear logic. This raises the possibility that the multiset rewriting framework may differ from strand spaces in some subtle way, although the two settings are known to agree on the basic secrecy property.

Subject Categories:

  • Operations Research
  • Computer Systems Management and Standards

Distribution Statement:

APPROVED FOR PUBLIC RELEASE