Title | Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks |
---|---|

Booktitle | Advances in Cryptology – CRYPTO 2018 |

Volume | 10991 |

Pages | 722-753 |

Year | 2018 |

URL | Search for the paper |

DOI | 10.1007/978-3-319-96884-1_24 (link) |

Author | Benoît Cogliati |

Author | Yevgeniy Dodis |

Author | Jonathan Katz |

Author | Jooyoung Lee |

Author | John Steinberger |

Author | Aishwarya Thiruvengadam |

Author | Zhe Zhang |

Abstract | 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” permutation 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}$$ 22n/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$$ 2n. 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 permutations (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\ge 2$$ w≥2); the tweakable block cipher provides security up to $$2^{2n/3}$$ 22n/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. |

@inproceedings{crypto-2018-28857, title={Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks}, booktitle={Advances in Cryptology – CRYPTO 2018}, series={Lecture Notes in Computer Science}, publisher={Springer}, volume={10991}, pages={722-753}, doi={10.1007/978-3-319-96884-1_24}, author={Benoît Cogliati and Yevgeniy Dodis and Jonathan Katz and Jooyoung Lee and John Steinberger and Aishwarya Thiruvengadam and Zhe Zhang}, year=2018 }