Small-Box Cryptography, and the Provable Security of SPNs

One of the ultimate goals of symmetric-key cryptography is to find rigorous theoretical framework for building block ciphers from small pseudorandom components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond than 2^{-n}, where n is the size of the corresponding component. As a result, prior provably secure approaches --- which we call "big-box cryptography" --- always made n larger than the security parameter, which led to several problems divorcing such results from reality. In this work introduce a novel paradigm for justifying the security of existing block ciphers, which we call *small-box cryptography*. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for *reduced-round* idealized variants of the existing block ciphers, into meaningful, *full-round* security justifications of the actual ciphers used in the real world. We then apply our framework to the design of popular SPN-based ciphers, which include AES, Serpent, and PRESENT, among others. To the best of our knowledge, our results give the most accurate and plausible theoretical justification for the security of SPN ciphers to date.