Optimizing Protocol Rewrite Rules of CIL Specifications

For purposes of security analysis, cryptographic protocols can be translated from a high-level message-list language like CAPSL into a multiset rewriting (MSR) rule language like CIL. The natural translation creates two rules per message or computational action. We show how to optimize the natural rule set by about 50% into a form similar to the result of hand encoding, and prove that the transformation is sound because it is attack-preserving, and unique because it is terminating and confluent. The optimization has been implemented in Java.