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

A first-order conditional logic is considered, with semantics given by a variant of ǫ-semantics (Adams 1975; Goldszmidt & Pearl 1992), where ϕ ψ means that Pr(ψ ϕ) 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.