TY - GEN
T1 - Small-Box Cryptography
AU - Dodis, Yevgeniy
AU - Karthikeyan, Harish
AU - Wichs, Daniel
N1 - Funding Information:
Funding Yevgeniy Dodis: Partially supported by gifts from VMware Labs and Google, and NSF grants 1619158, 1319051, 1314568. Daniel Wichs: Partially supported by NSF grants CNS-1413964, CNS-1750795 and the Alfred P. Sloan Research Fellowship.
Publisher Copyright:
© Yevgeniy Dodis, Harish Karthikeyan, and Daniel Wichs; licensed under Creative Commons License CC-BY 4.0
PY - 2022/1/1
Y1 - 2022/1/1
N2 - One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building block ciphers from small 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 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: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such “big-boxes” were completely abstracted out; (b) the theoretically predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the “big-box” building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored the substitution-permutation network (SPN) paradigm which is at the heart of most real-world implementations of such ciphers. In this work, we 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 analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable and plausible concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we managed to find a direct “big-box”-style security justification, under a well studied and widely believed eXact Linear Parity with Noise (XLPN) assumption. Overall, we hope that our work will initiate many follow-up results in the area of small-box cryptography.
AB - One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building block ciphers from small 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 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: (a) the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such “big-boxes” were completely abstracted out; (b) the theoretically predicted number of rounds for the security of this approach was always dramatically smaller than in reality, where the “big-box” building block could not be made as ideal as required by the proof. For example, Even-Mansour (and, more generally, key-alternating) ciphers completely ignored the substitution-permutation network (SPN) paradigm which is at the heart of most real-world implementations of such ciphers. In this work, we 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 analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable and plausible concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we managed to find a direct “big-box”-style security justification, under a well studied and widely believed eXact Linear Parity with Noise (XLPN) assumption. Overall, we hope that our work will initiate many follow-up results in the area of small-box cryptography.
KW - Block ciphers
KW - Cryptography
KW - S-Box
UR - http://www.scopus.com/inward/record.url?scp=85123991781&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85123991781&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2022.56
DO - 10.4230/LIPIcs.ITCS.2022.56
M3 - Conference contribution
AN - SCOPUS:85123991781
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
A2 - Braverman, Mark
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Y2 - 31 January 2022 through 3 February 2022
ER -