Generalized Mirror Theory

Lower-bounding non-degenerate solution counts for arbitrary dependency graphs

Motivation

Mirror Theory bounds are a core technical tool behind beyond-birthday-bound security proofs for constructions such as sum-of-permutations and counter-mode variants: they lower-bound how many ways a system of “no two of these values collide” constraints can be satisfied. Extending the theory from the restricted graph topologies it’s currently proven for to arbitrary cycle-consistent multi-graphs would unlock tight security proofs for a much wider class of constructions.

Provenance and history

Patarin introduced Mirror Theory for linear graphs and trees (2003, 2005), though gaps were later identified in the original proofs. Cogliati & Seurin proved the circle-graph case (2018), and Cogliati et al. extended this to arbitrary forest graphs up to component size \(O(N^{1/4}/\sqrt{n})\) (2023). The fully generalized conjecture, for arbitrary multi-graphs up to the information-theoretic limit \(\xi_{\max} = o(N^{1/2})\), remains open.

Parameter lattice

The known axis of variation is graph topology, ordered by how much of the conjecture it establishes.

Topology Max component size proven Status
Linear graphs / trees \(O(1)\) Gaps identified
Circle graphs (\(\nu=1\)) \(O(N^{1/3})\) Proven
Arbitrary forests \(O(N^{1/4}/\sqrt{n})\) Proven
Arbitrary multi-graphs \(o(N^{1/2})\) c/0002 – open

Only the fully general multi-graph case is a leaf in this archive; the proven special cases above are cited results, not separate statements here.

Statements in this hub