Paper 2019/1107

On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy

Lorenzo Grassi, Reinhard Lüftenegger, Christian Rechberger, Dragos Rotaru, and Markus Schofnegger

Abstract

Keyed and unkeyed cryptographic permutations often iterate simple round functions. Substitution-permutation networks (SPNs) are an approach that is popular since the mid 1990s. One of the new directions in the design of these round functions is to reduce the substitution (S-Box) layer from a full one to a partial one, uniformly distributed over all the rounds. LowMC and Zorro are examples of this approach. A relevant freedom in the design space is to allow for a highly non-uniform distribution of S-Boxes. However, choosing rounds that are so different from each other is very rarely done, as it makes security analysis and implementation much harder. We develop the design strategy Hades and an analysis framework for it, which despite this increased complexity allows for security arguments against many classes of attacks, similar to earlier simpler SPNs. The framework builds upon the wide trail design strategy, and it additionally allows for security arguments against algebraic attacks, which are much more of a concern when algebraically simple S-Boxes are used. Subsequently, this is put into practice by concrete instances and benchmarks for a use case that generally benefits from a smaller number of S-Boxes and showcases the diversity of design options we support: A candidate cipher natively working with objects in GF(p), for securing data transfers with distributed databases using secure multiparty computation (MPC). Compared to the currently fastest design MiMC, we observe significant improvements in online bandwidth requirements and throughput with a simultaneous reduction of preprocessing effort, while having a comparable online latency.

Note: With respect to the last ePrint version, changes basically include the following. 1. We provide a generalization of the S-Box from x^3 to x^(alpha), where alpha is the smallest positive integer s.t. gcd(alpha, p-1) = 1. 2. We provide a new specification for the linear layer, fixing a security problem highlighted in [1], [2], and [3]. 3. We note that the round numbers for the original construction with the S-Box x^3 did not change. [1] Keller et al., Mind the Middle Layer: The HADES Design Strategy Revisited, IACR ePrint Archive 2020. [2] Beyne et al., Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems, Crypto 2020. [3] Grassi et al., Weak Linear Layers in Word-Oriented Partial SPN and HADES-Like Ciphers, IACR ePrint Archive 2020.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in Eurocrypt 2020
Keywords
Hades StrategyCryptographic PermutationsSecure Multiparty Computation (MPC)
Contact author(s)
lorenzo grassi @ iaik tugraz at
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ tugraz at
dragos rotaru @ bristol ac uk
markus schofnegger @ tugraz at
History
2020-07-14: last of 3 revisions
2019-09-29: received
See all versions
Short URL
https://ia.cr/2019/1107
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1107,
      author = {Lorenzo Grassi and Reinhard Lüftenegger and Christian Rechberger and Dragos Rotaru and Markus Schofnegger},
      title = {On a Generalization of Substitution-Permutation Networks: The HADES Design Strategy},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1107},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1107}},
      url = {https://eprint.iacr.org/2019/1107}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.