This paper presents Pseudo-Random Grouping with Certified Robustness (PRG-CR), a framework that partitions input features into cryptographically-secure pseudo-random groups to provide deterministic robustness certificates against adaptive adversaries. The approach leverages structured grouping with cryptographically secure pseudo-randomness to create an information-theoretic barrier against adaptive attacks. The paper derives certified robustness bounds for PRG-CR and demonstrates its effectiveness on CIFAR-10, ImageNet, and MNIST datasets.
Key findings
PRG-CR provides deterministic robustness certificates against adaptive attacks.
Achieves comparable certified radii to Gaussian smoothing with improved resilience.
Formalizes adaptive attacks against grouped smoothing and proves security against computationally bounded adversaries.
Outperforms existing randomized smoothing baselines by up to 15% under strong adaptive threat models.
Limitations & open questions
The paper does not discuss the computational overhead introduced by cryptographically secure pseudo-random grouping.