Reference : Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Security, Reliability and Trust
Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
Cogliati, Benoît-Michel mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Dodis, Yevgeniy mailto [New York University, USA]
Katz, Jonathan mailto [University of Maryland, USA]
Lee, Jooyoung mailto [KAIST, Korea]
Steinberger, John mailto []
Thiruvengadam, Aishwarya mailto [University of California, Santa Barbara]
Zhang, Zhe mailto [Tsinghua University, Beijing]
Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
August 19-23, 2018
[en] substitution-permutation networks ; tweakable block ciphers ; domain extension of block ciphers ; beyond-birthday-bound security
[en] Substitution-Permutation Networks (SPNs) refer to a family
of constructions which build a wn-bit block cipher from n-bit public
permutations (often called S-boxes), which alternate keyless and “local”
substitution steps utilizing such S-boxes, with keyed and “global” permu-
tation steps which are non-cryptographic. Many widely deployed block
ciphers are constructed based on the SPNs, but there are essentially no
provable-security results about SPNs.
In this work, we initiate a comprehensive study of the provable security
of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying
n-bit permutation is modeled as a public random permutation. When the
permutation step is linear (which is the case for most existing designs),
we show that 3 SPN rounds are necessary and sufficient for security. On
the other hand, even 1-round SPNs can be secure when non-linearity
is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-
birthday” (up to 2 2n/3 adversarial queries) security, and, as the number
of non-linear rounds increases, our bounds are meaningful for the number
of queries approaching 2 n . Finally, our non-linear SPNs can be made
tweakable by incorporating the tweak into the permutation layer, and
provide good multi-user security.
As an application, our construction can turn two public n-bit permuta-
tions (or fixed-key block ciphers) into a tweakable block cipher working
on wn-bit inputs, 6n-bit key and an n-bit tweak (for any w ≥ 2); the
tweakable block cipher provides security up to 2 2n/3 adversarial queries
in the random permutation model, while only requiring w calls to each
permutation, and 3w field multiplications for each wn-bit input.
© IACR 2018. This article is the final version submitted by the author(s) to the IACR and to Springer-Verlag on 2018-06-10. The version published by Springer-Verlag is available at 10.1007/978-3-319-96884-1\_24
H2020 ; 644209 - HEAT - Homomorphic Encryption Applications and Technology

File(s) associated to this reference

Fulltext file(s):

Open access
spn-bbb.pdfAuthor postprint640.36 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.