## An improved degree evaluation method of NFSR-based cryptosystems.(English)Zbl 1477.94064

Summary: In this paper, we study the algebraic degree evaluation of NFSR-based cryptosystems. The degree evaluation method based on the numeric mapping proposed by M. Liu [Lect. Notes Comput. Sci. 10403, 227–249 (2017; Zbl 1406.94073)] is very fast and could be applied to a cube of any size. The numeric degree of $$f_1(x,v)\times f_2(x,v)$$ is estimated as $$D_1+D_2$$, where $$D_1$$ and $$D_2$$ are the numeric degrees of $$f_1$$ and $$f_2$$ respectively and the algebraic degree of a function is no more than its numeric degree. It can be observed that some variables may be counted twice in $$D_1+D_2$$ and the precise of the numerical mapping heavily depends on how many variables are counted redundantly. When applied to an iterative cryptosystem, such redundances will accumulate during iteratively computing numeric degrees. This is an important factor accounting for the difference between the numeric degree and the algebraic degree of a cryptosystem. To reduce this difference, a new framework on the degree evaluation algorithm based on the numeric mapping is proposed. The main idea is to identify variables which are repeatedly counted in the numeric mapping and eliminate the redundant degrees on these variables. As illustrations, a concrete algorithm on Trivium-like ciphers is given which is shown to be useful in correlation cube attacks and the zero-sum distinguisher search. For correlation cube attacks on $$835$$-round Trivium, we find some more useful cubes so that we could recover about $$1.5$$ more bits at a cost of $$2^{40.7}$$. Furthermore, we find several cubes leading to zero-sum distinguishers for Kreyvium variants with from $$875$$ to $$880$$ initialization rounds.

### MSC:

 94A60 Cryptography 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory

Zbl 1406.94073

### Software:

Quark; Grain; Trivium; KATAN; KTANTAN
Full Text: