  Many important cryptographic primitives offer probabilistic guarantees of
security that can be specified as quantitative hyperproperties; these are
specifications that stipulate the existence of a certain number of traces in
the system satisfying certain constraints. Verification of such hyperproperties
is extremely challenging because they involve simultaneous reasoning about an
unbounded number of different traces. In this paper, we introduce a technique
for verification of quantitative hyperproperties based on the notion of trace
enumeration relations. These relations allow us to reduce the problem of
trace-counting into one of model-counting of formulas in first-order logic. We
also introduce a set of inference rules for machine-checked reasoning about the
number of satisfying solutions to first-order formulas (aka model counting).
Putting these two components together enables semi-automated verification of
quantitative hyperproperties on infinite state systems. We use our methodology
to prove confidentiality of access patterns in Path ORAMs of unbounded size,
soundness of a simple interactive zero-knowledge proof protocol as well as
other applications of quantitative hyperproperties studied in past work.
