Miyaji Laboratory

In recent years, information and communication technology has advanced rapidly and has become an indispensable part of the digitalization of modern society. In particular, the technologies used to achieve confidentiality are symmetric-key cryptography, where the encryption and decryption keys are the same, and public-key cryptography, where the encryption and decryption keys are different. Symmetric-key cryptography is faster in data processing compared to public-key cryptography and is an essential tech nology for encrypting large volumes of data. ChaCha is a symmetric-key cipher and an encryption communication protocol standardized by the IETF. It is also the only stream cipher adopted in TLS 1.3. ChaCha was proposed in 2008 as an improved version of the stream cipher Salsa20, which was introduced in 2004, with enhanced diffusion and resistance to cryptanalysis. Analysis techniques for ChaCha include differential-linear cryptanalysis, which improves the overall bias by combining highly biased input-output bits in the QuarterRound Function (QRF) with even more biased linear approximations. Another ap proach involves decomposing the QRF into two SubRound Functions (SRFs) and deriving more biased linear approximations from the SRF perspective to apply them to differential-linear cryptanalysis. In such differential-linear cryptanalysis, Coutinho et al. reported that a distinguisher attack based on 7 rounds is possible with a complexity of 2²¹⁴. The complexity of a distinguisher attack is derived from the computational costs of differential and linear analysis. In particular, linear analysis involves dividing a single linear approximation into multiple partial linear approximations, theoretically constructing the bias (linear bias) of each partial approximation, and experimentally verifying the theoretical values. The theoretical bias of the linear approximation used to derive the aforementioned 7-round result is 2</sup>−53<sup>, which is obtained from four partial linear approximations, I-IV. Two of them appropriately reflect the experimental values in their theoretical values, while it has been reported that the theoretical values of the remaining two, II and III, are significantly lower than the experimental values. Specifically, the theoretical biases of the two partial linear approximations, II and III, are 2⁻¹⁴ and 2⁻¹⁵, respectively. However, the ratio of the experimental value to the theoretical value, which represents the error between the theoretical and experimental values, is 3.227 and 4.554. Regarding the accuracy of theoretical eval uations of linear approximations, Nyberg et al. have addressed the case of SNOW 2.0, but there have been no reports on this matter for ChaCha so far. In this study, we rigorously reexamined these partial linear approximations, II and III, and constructed more accurate theoretical formulas. As a result, we theoretically proved that the theoretical linear biases of the partial linear approximations II and III are 5² · 3⁻² · 2⁻¹⁴ and 3⁻³ · 2⁻⁸, respectively. The ratio of the experimental value to the theoretical value, representing the error between the theory and the experiment, is 1.189 and 0.943. From this result, it is evident that the theoretical formulas we introduced more accurately reflect the experimental values. With the improvement of the theoretical values of the partial linear approximations, the theoretical bias of the linear approximation used in the above 7-round distinguisher attack is refined to 5² · 3⁻⁵ · 2⁻⁴⁶. The theoretical biases of the 3-7 linear approximations derived in this study represent, to the author's knowledge, the highest linear biases achieved.