Formal Analysis of a Privacy-Preserving Billing Protocol

We provide a formal model and a security analysis of the Private Billing Protocol. This formal analysis allowed us to spell out precisely the details of the protocol, the security assumptions as well as the expected security goals. For the formal analysis we used SATMC, a model checker for security protocol analysis that supports the specification of security assumptions and goals as LTL formulae. Further analysis that we conducted manually revealed that the protocol allows for implementations that fail to meet the expected privacy goal. We describe the implications of our findings and discuss how the problem can be avoided.