This paper presents the Completeness Invariant, a lightweight cryptographic primitive for detecting omission attacks on digital evidence sets. We address the open problem of verifying that no items have been selectively removed from an unordered evidence collection—a vulnerability that existing tamper-evident mechanisms (hash chains, Merkle trees, digital signatures, C2PA manifests) leave unaddressed. Our construction applies XOR aggregation of SHA-256 hashes—building on the incremental hashing paradigm of Bellare and Micciancio (1997) and the multiset hash constructions of Clarke et al. (2003)—to achieve O(1) per-event update and O(1) verification with a 32-byte constant-size commitment, independent of set size. We formalize the notion of omission resistance through the OmitForge security game and prove (t, n, ε)-omission resistance under the random oracle model. We analyze known vulnerabilities—XHASH attacks, Wagner's generalized birthday problem (2002), and self-inverse cancellation—and specify concrete countermeasures including bounded set sizes, unique nonce enforcement, and hardware-backed computation via Apple Secure Enclave and Android StrongBox. We implement the Completeness Invariant within the Capture Provenance Profile (CPP v1.5) specification, deployed in VeraSnap, a consumer iOS application. Experimental evaluation on 10,000 evidence sessions demonstrates 0.003ms per-event XOR aggregation overhead, 100% omission detection rate, and 56-byte total verification state. Integration with RFC 3161 trusted timestamping, RFC 6962 Merkle trees, and biometric human-presence binding provides defense-in-depth across four independent security layers. While related standards such as RFC 4998 (Evidence Record Syntax) address hash-tree-based evidence preservation for ordered archives, and alternative multiset hash constructions (MuHash, LtHash) offer stronger algebraic guarantees without set-size bounds, our contribution lies in the specific combination of formal omission-resistance definitions, bounded XOR construction with explicit countermeasures, and validated deployment on consumer hardware.
Tokachi Kamimura (Mon,) studied this question.