What CertPHash Can Prove—and What It Cannot
CertPHash is a proposed way to make perceptual-hash robustness claims explicit, but its certificates are only meaningful when their direction, perturbation range, data, and threshold are named. This chapter focuses on how the system verifies evasion and collision resistance, what its functionality and attack results show, and where the NSFW proxy experiment and engineering costs limit the conclusion. The reader should leave able to treat “certified” as a precise, scoped statement rather than as a synonym for invulnerable.
A certificate has a direction
The two robustness questions require two different calculations. For evasion, begin with one clean image and its output. Allow every input within a specified perturbation region around that image. The question is whether every resulting output stays close enough to the clean output to count as a match. CertPHash handles this with forward verification: bounds are propagated from the perturbed input through the network to the output. If the resulting output range remains inside the permitted match neighborhood, the model has a certified no-evasion result for that image, norm, radius, and threshold.
The word “every” is what distinguishes certification from trying a few examples. An empirical attack can search for a successful perturbation and fail to find one. A certificate aims to bound the worst case within the stated input region, even if a particular perturbation was never constructed. The bound is not a free-floating guarantee. It belongs to the exact model and verifier, and it ends at the boundary of the norm ball and radius that were checked.
Collision verification runs in the opposite direction. Start with an output neighborhood around a target hash: all outputs close enough to the target to be treated as a match. The verifier then works backward through the network to over-approximate the set of inputs that could produce an output inside that neighborhood. This set is a constrained preimage. If the over-approximated preimages for two distinct images do not overlap, the tested pair has a certified no-collision result under the chosen output constraint and input domain.
The distinction between forward and inverse reasoning is not a technical flourish. A forward bound asks how far one input’s output can move. An inverse bound asks which inputs could reach a target region. Two clean outputs can be far apart while their permitted preimage regions still overlap once the match neighborhood and perturbation allowance are accounted for. Conversely, an inverse verifier may produce a broad over-approximation that overlaps even when the exact preimages do not. That overlap is a conservative failure of the certificate, not proof that a successful collision has been found.
CertPHash measures these properties with separate rates. The certified no-evasion rate, or CNER, is the share of tested inputs for which the forward check establishes that all allowed perturbations remain within the match threshold. The certified no-collision rate, or CNCR, is the share for which the inverse constrained preimages do not overlap in the verification setup.