Paper 2026/2813

Overcoming Padding in Cryptography via Hardness of Certifying Random Strings

Abstract

Modern cryptography relies on a provable security paradigm where the security of a primitive is established from the intractability of one or more computational problems. Hybrid arguments are central to this approach. Somewhat unexpectedly, many security proofs in the literature that use this methodology require hybrids with description-size larger than the real scheme. To argue security, the real scheme is artificially padded to match this size. This so-called “superfluous padding” phenomenon is surprisingly commonplace and poses a barrier to achieving succinct cryptographic primitives where the size of the scheme parameters does not grow with the input length. We present a framework to eliminate padding in cryptography. We demonstrate several applications, including rate-1 iO, succinct (and extractable) witness encryption and succinct non-interactive arguments with short CRS for subclasses of NP, and multi-input functional encryption for functions with unbounded arity. To obtain our results, we establish a new connection between cryptography and proof complexity. Central to our approach is the notion of proof-complexity generators (PCGs) [Krajíček'01, Alekhnovich, Ben-Sasson, Razborov, Wigderson'04], which, informally speaking, formalizes the hardness of certifying random (incompressible) strings with propositional proof systems. Our applications are derived from a master theorem that lifts cryptographic security on “compressible instances” to security on any instance under the existence of PCGs. Due to its broad scope, this theorem might find future application