Paper 2016/984

Design Strategies for ARX with Provable Bounds: SPARX and LAX (Full Version)

Daniel Dinu, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, Johann Großschädl, and Alex Biryukov


We present, for the first time, a general strategy for designing ARX symmetric-key primitives with provable resistance against single-trail differential and linear cryptanalysis. The latter has been a long standing open problem in the area of ARX design. The wide trail design strategy (WTS), that is at the basis of many S-box based ciphers, including the AES, is not suitable for ARX designs due to the lack of S-boxes in the latter. In this paper we address the mentioned limitation by proposing the long trail design strategy (LTS) -- a dual of the WTS that is applicable (but not limited) to ARX constructions. In contrast to the WTS, that prescribes the use of small and efficient S-boxes at the expense of heavy linear layers with strong mixing properties, the LTS advocates the use of large (ARX-based) S-Boxes together with sparse linear layers. With the help of the so-called Long Trail argument, a designer can bound the maximum differential and linear probabilities for any number of rounds of a cipher built according to the LTS. To illustrate the effectiveness of the new strategy, we propose SPARX -- a family of ARX-based block ciphers designed according to the LTS. SPARX has 32-bit ARX-based S-boxes and has provable bounds against differential and linear cryptanalysis. In addition, SPARX is very efficient on a number of embedded platforms. Its optimized software implementation ranks in the top 6 of the most software-efficient ciphers along with SIMON, SPECK, Chaskey, LEA and RECTANGLE. As a second contribution we propose another strategy for designing ARX ciphers with provable properties, that is completely independent of the LTS. It is motivated by a challenge proposed earlier by Wall{é}n and uses the differential properties of modular addition to minimize the maximum differential probability across multiple rounds of a cipher. A new primitive, called LAX, is designed following those principles. LAX partly solves the Wall{é}n challenge.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2016
ARXblock ciphersdifferential cryptanalysislinear cryptanalysislightweightwide trail strategy
Contact author(s)
leo perrin @ inria fr
2021-05-31: revised
2016-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Dinu and Léo Perrin and Aleksei Udovenko and Vesselin Velichkov and Johann Großschädl and Alex Biryukov},
      title = {Design Strategies for {ARX} with Provable Bounds: {SPARX} and {LAX} (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/984},
      year = {2016},
      doi = {10.1007/978-3-662-53887-6_18},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.