Design Strategies for ARX with Provable Bounds: Sparx and LAX

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationAdvances in Cryptology -- ASIACRYPT 2016
EditorsJung Hee Cheon, Tsuyoshi Takagi
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages30
ISBN (Electronic)978-3-662-53887-6
ISBN (Print)978-3-662-53887-6
Publication statusE-pub ahead of print - 9 Nov 2016
Event22nd International Conference on the Theory and Application of Cryptology and Information Security - Hanoi, Viet Nam
Duration: 4 Dec 20168 Dec 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameSecurity and Cryptology


Conference22nd International Conference on the Theory and Application of Cryptology and Information Security
Abbreviated titleASIACRYPT 2016
Country/TerritoryViet Nam
Internet address


Dive into the research topics of 'Design Strategies for ARX with Provable Bounds: Sparx and LAX'. Together they form a unique fingerprint.

Cite this