From Qualitative to Quantitative Proofs of Security Properties: Using First-Order Conditional Logic

Joseph Y. Halpern

A first-order conditional logic is considered, with semantics given by a variant of epsilon-semantics, where p -> q means that \Pr(p | q) approaches 1 super-polynomially—faster than any inverse polynomial. This type of convergence is needed for reasoning about security protocols. A complete axiomatization is provided for this semantics, and it is shown how a qualitative proof of the correctness of a security protocol can be automatically converted to a quantitative proof appropriate for reasoning about concrete security.

Subjects: 3.3 Nonmonotonic Reasoning; 11. Knowledge Representation

Submitted: Apr 14, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.