Document Open Access Logo

Small-Box Cryptography

Authors Yevgeniy Dodis, Harish Karthikeyan, Daniel Wichs

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.56.pdf
  • Filesize: 0.77 MB
  • 25 pages

Document Identifiers

Author Details

Yevgeniy Dodis
  • New York University, NY, USA
Harish Karthikeyan
  • New York University, NY, USA
Daniel Wichs
  • Northeastern University, Boston, MA, USA
  • NTT Research, Sunnyvale, CA, USA

Funding

  • Dodis, Yevgeniy: Partially supported by gifts from VMware Labs and Google, and NSF grants 1619158, 1319051, 1314568.
  • Wichs, Daniel: Partially supported by NSF grants CNS-1413964, CNS-1750795 and the Alfred P. Sloan Research Fellowship.

Acknowledgements

The authors would also like to thank Stefano Tessaro for his help in applying the results of [Ueli M. Maurer et al., 2007] in Section 4.4.

Cite As Get BibTex

Yevgeniy Dodis, Harish Karthikeyan, and Daniel Wichs. Small-Box Cryptography. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 56:1-56:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.56

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Cryptographic protocols
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Mathematical foundations of cryptography
  • Security and privacy → Block and stream ciphers
Keywords
  • Block Ciphers
  • S-Box
  • Cryptography

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Benny Applebaum. Cryptographic hardness of random local functions-survey. In Amit Sahai, editor, Theory of Cryptography, pages 599-599, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  2. Alex Biryukov, Charles Bouillaguet, and Dmitry Khovratovich. Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key (extended abstract). In Advances in Cryptology - ASIACRYPT 2014, Part I, volume 8873 of Lecture Notes in Computer Science, pages 63-84. Springer, Heidelberg, Germany, 2014. Google Scholar
  3. Alex Biryukov and Dmitry Khovratovich. Decomposition attack on SASASASAS. Available at http://eprint.iacr.org/2015/646. Google Scholar
  4. Alex Biryukov and Adi Shamir. Structural cryptanalysis of SASAS. Journal of Cryptology, 23(4):505-518, 2010. Google Scholar
  5. Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, François-Xavier Standaert, John P. Steinberger, and Elmar Tischhauser. Key-alternating ciphers in a provable setting: Encryption using a small number of public permutations. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 45-62. Springer, Heidelberg, Germany, 2012. Google Scholar
  6. Ran Canetti, Shai Halevi, and Michael Steiner. Hardness amplification of weakly verifiable puzzles. In Joe Kilian, editor, TCC 2005: 2nd Theory of Cryptography Conference, volume 3378 of Lecture Notes in Computer Science, pages 17-33, Cambridge, MA, USA, February 10-12, 2005. Springer, Heidelberg, Germany. Google Scholar
  7. Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, and Hoeteck Wee. Amplifying collision resistance: A complexity-theoretic treatment. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 264-283, Santa Barbara, CA, USA, August 19-23, 2007. Springer, Heidelberg, Germany. Google Scholar
  8. Debrup Chakraborty and Palash Sarkar. A new mode of encryption providing a tweakable strong pseudo-random permutation. In Fast Software Encryption - FSE 2006, volume 4047 of Lecture Notes in Computer Science, pages 293-309. Springer, Heidelberg, Germany, 2006. Google Scholar
  9. Shan Chen and John P. Steinberger. Tight security bounds for key-alternating ciphers. In Advances in Cryptology - EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 327-350. Springer, Heidelberg, Germany, 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_19.
  10. Kai-Min Chung, Feng-Hao Liu, Chi-Jen Lu, and Bo-Yin Yang. Efficient string-commitment from weak bit-commitment. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 268-282, Singapore, December 5-9, 2010. Springer, Heidelberg, Germany. Google Scholar
  11. Benoît Cogliati, Yevgeniy Dodis, Jonathan Katz, Jooyoung Lee, John P. Steinberger, Aishwarya Thiruvengadam, and Zhe Zhang. Provable security of (tweakable) block ciphers based on substitution-permutation networks. In Advances in Cryptology – CRYPTO 2018, volume 10991 of Lecture Notes in Computer Science, pages 722-753. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-96884-1_24.
  12. Sandro Coretti, Yevgeniy Dodis, and Siyao Guo. Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, volume 10991 of Lecture Notes in Computer Science, pages 693-721. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-96884-1_23.
  13. Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeoffs for attacks against one-way functions and PRGs. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 649-665, Santa Barbara, CA, USA, August 15-19, 2010. Springer, Heidelberg, Germany. Google Scholar
  14. Itai Dinur, Orr Dunkelman, Thorsten Kranz, and Gregor Leander. Decomposing the ASASA block cipher construction. Available at http://eprint.iacr.org/2015/507. Google Scholar
  15. Yevgeniy Dodis, Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets. Security amplification for interactive cryptographic primitives. In Omer Reingold, editor, TCC 2009: 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science, pages 128-145. Springer, Heidelberg, Germany, March 15-17, 2009. Google Scholar
  16. Yevgeniy Dodis, Abhishek Jain, Tal Moran, and Daniel Wichs. Counterexamples to hardness amplification beyond negligible. In Proceedings of the 9th International Conference on Theory of Cryptography, TCC'12, pages 476-493, Berlin, Heidelberg, 2012. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-28914-9_27.
  17. Yevgeniy Dodis, Martijn Stam, John P. Steinberger, and Tianren Liu. Indifferentiability of confusion-diffusion networks. In Advances in Cryptology - EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 679-704. Springer, Heidelberg, Germany, 2016. Google Scholar
  18. Orr Dunkelman, Nathan Keller, and Adi Shamir. Minimalism in cryptography: The Even-Mansour scheme revisited. In Advances in Cryptology - EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 336-354. Springer, Heidelberg, Germany, 2012. Google Scholar
  19. Cynthia Dwork, Moni Naor, and Omer Reingold. Immunizing encryption schemes from decryption errors. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 342-360, Interlaken, Switzerland, May 2-6, 2004. Springer, Heidelberg, Germany. Google Scholar
  20. Shimon Even and Yishay Mansour. A construction of a cipher from a single pseudorandom permutation. In Advances in Cryptology - ASIACRYPT'91, volume 739 of Lecture Notes in Computer Science, pages 210-224. Springer, Heidelberg, Germany, 1991. Google Scholar
  21. Horst Feistel. Cryptography and computer privacy. Scientific American, 228(5):15-23, 1973. Google Scholar
  22. Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs, pages 76-87. Springer-Verlag, Berlin, Heidelberg, 2011. Google Scholar
  23. Oded Goldreich, Noam Nisan, and Avi Wigderson. On yao’s xor-lemma. In In Electronic Colloquium on Computational Complexity (ECCC, 1995. Google Scholar
  24. Shai Halevi. Invertible universal hashing and the TET encryption mode. In Advances in Cryptology - CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 412-429. Springer, Heidelberg, Germany, 2007. Google Scholar
  25. Viet Tung Hoang and Stefano Tessaro. Key-alternating ciphers and key-length extension: Exact bounds and multi-user security. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part I, volume 9814 of Lecture Notes in Computer Science, pages 3-32. Springer, Heidelberg, Germany, 2016. URL: https://doi.org/10.1007/978-3-662-53018-4_1.
  26. Tetsu Iwata and Kaoru Kurosawa. On the pseudorandomness of the AES finalists - RC6 and Serpent. In Fast Software Encryption - FSE 2000, volume 1978 of Lecture Notes in Computer Science, pages 231-243. Springer, Heidelberg, Germany, 2000. Google Scholar
  27. Abhishek Jain, Stephan Krenn, Krzysztof Pietrzak, and Aris Tentes. Commitments and efficient zero-knowledge proofs from learning parity with noise. In ASIACRYPT, volume 7658, pages 663-680. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-34961-4_40.
  28. J. Katz and Y. Lindell. Introduction to Modern Cryptography, 2nd edition. Chapman & Hall/CRC Press, 2015. Google Scholar
  29. Joe Kilian and Phillip Rogaway. How to protect DES against exhaustive key search (an analysis of DESX). Journal of Cryptology, 14(1):17-35, 2001. Google Scholar
  30. Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2):373-386, 1988. Google Scholar
  31. Ueli M. Maurer, Krzysztof Pietrzak, and Renato Renner. Indistinguishability amplification. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 130-149, Santa Barbara, CA, USA, August 19-23, 2007. Springer, Heidelberg, Germany. Google Scholar
  32. Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In TCC 2004: 1st Theory of Cryptography Conference, volume 2951 of Lecture Notes in Computer Science, pages 21-39. Springer, Heidelberg, Germany, 2004. Google Scholar
  33. Eric Miles and Emanuele Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. Journal of the ACM, 62(6):46, 2015. Google Scholar
  34. Moni Naor and Omer Reingold. On the construction of pseudorandom permutations: Luby-Rackoff revisited. Journal of Cryptology, 12(1):29-66, 1999. Google Scholar
  35. Claude E. Shannon. Communication theory of secrecy systems. Bell Systems Technical Journal, 28(4):656-715, 1949. Google Scholar
  36. Stefano Tessaro. Security amplification for the cascade of arbitrarily weak PRPs: Tight bounds via the interactive hardcore lemma. In Yuval Ishai, editor, TCC 2011: 8th Theory of Cryptography Conference, volume 6597 of Lecture Notes in Computer Science, pages 37-54, Providence, RI, USA, March 28-30, 2011. Springer, Heidelberg, Germany. Google Scholar
  37. Andrew C. Yao. Theory and applications of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science, pages 80-91. IEEE Computer Society Press, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact