Cryptology ePrint Archive: Report 2017/016

Provable Security of Substitution-Permutation Networks

Yevgeniy Dodis and Jonathan Katz and John Steinberger and Aishwarya Thiruvengadam and Zhe Zhang

Abstract: Many modern block ciphers are constructed based on the paradigm of substitution-permutation networks (SPNs). But, somewhat surprisingly---especially in comparison with Feistel networks, which have been analyzed by dozens of papers going back to the seminal work of Luby and Rackoff---there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the security of SPNs as strong pseudorandom permutations when the underlying "S-box" is modeled as a public random permutation. We show that 3 rounds of S-boxes are necessary and sufficient for secure linear SPNs, but that even 1-round SPNs can be secure when non-linearity is allowed.

Category / Keywords: secret-key cryptography / SPNs, block ciphers

Date: received 9 Jan 2017

Contact author: jkatz at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20170111:132353 (All versions of this report)

Short URL: ia.cr/2017/016

Discussion forum: Show discussion | Start new discussion