The possibility of applying linear analysis to the ARX stochastic algorithms depending on round key functions

Abstract

ARX stochastic algorithms are a promising solution in the development of unpredictable pseudo- random number generators for low-resource systems. The ease of implementation of their round operations, as well as their high energy efficiency, make the choice of such algorithms attractive for ensuring the confidentiality of information. Existing studies on the possibility of applying linear analysis to ARX stochastic algorithms use imprecise linear approximations of round functions. The key idea of linear analysis is the use of linear statistical analogs of non-linear functions. Linear approximations are used to express the inputs of the stochastic transformation algorithm by its outputs as a linear function. The resulting linear function is true with a certain probability, which depends on the probability of fulfilling the used linear approximations. The only non-linear operation in ARX algorithms is addition modulo 2n. In this paper we study the limitations of the applicability of the linear analysis to ARX stochastic transformation algorithms. The study is carried out for various cases of the implementation of round key addition: the use of the addition modulo 2n, the addition modulo 2, and the cyclic shift. For ARX stochastic transformation algorithms, using addition modulo 2n or addition modulo 2 as a round key mix operation, estimates are obtained for the number of addition operations modulo 2n needed to ensure their stability to linear analysis.

Keywords

• addition modulo 2n, arx, linear analysis, pseudorandom number generator.