On the Guaranteed Number of Activations in XS-circuits

Sergey Agievich

Paper 2020/850

On the Guaranteed Number of Activations in XS-circuits

Sergey Agievich

, Belarusian State University

Abstract

XS-circuits describe cryptographic primitives that utilize 2 operations on binary words of fixed length: X) bitwise modulo 2 addition and S) substitution. The words are interpreted as elements of a field of characteristic 2. In this paper, we develop a model of XS-circuits according to which several instances of a simple round circuit containing only one S operation are linked together and form a compound circuit called a cascade. S operations of a cascade are interpreted as independent round oracles. When a cascade processes a pair of different inputs, some round oracles get different queries, these oracles are activated. The more activations, the higher security guarantees against differential cryptanalysis the cascade provides. We introduce the notion of the guaranteed number of activations, that is, the minimum number of activations over all choices of the base field, round oracles and pairs of inputs. We show that the guaranteed number of activations is related to the minimum distance of the linear code associated with the cascade. It is also related to the minimum number of occurrences of units in segments of binary linear recurrence sequences whose characteristic polynomial is determined by the round circuit. We provide an algorithm for calculating the guaranteed number of activations. We show how to use the algorithm to deal with linear activations related to linear cryptanalysis.

Note: Fix editorial issues.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Mat. Vopr. Kriptogr., 12:2 (2021), 7-20
DOI: 10.4213/mvk353
Keywords: circuit differential cryptanalysis linear cryptanalysis linear code linear recurrence sequence
Contact author(s): agievich @ bsu by
History: 2024-05-29: last of 2 revisions; 2020-07-12: received; See all versions
Short URL: https://ia.cr/2020/850
License: CC BY

BibTeX

@misc{cryptoeprint:2020/850,
      author = {Sergey Agievich},
      title = {On the Guaranteed Number of Activations in {XS}-circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/850},
      year = {2020},
      doi = {10.4213/mvk353},
      url = {https://eprint.iacr.org/2020/850}
}