### Coefficient Grouping: Breaking Chaghri and More

##### Abstract

We propose an efficient technique called coefficient grouping to evaluate the algebraic degree of the FHE-friendly cipher Chaghri, which has been accepted for ACM CCS 2022. It is found that the algebraic degree increases linearly rather than exponentially. As a consequence, we can construct a 13-round distinguisher with time and data complexity of $2^{63}$ and mount a 13.5-round key-recovery attack. In particular, a higher-order differential attack on 8 rounds of Chaghri can be achieved with time and data complexity of $2^{38}$. Hence, it indicates that the full 8 rounds are far from being secure. Furthermore, we also demonstrate the application of our coefficient grouping technique to the design of secure cryptographic components. As a result, a countermeasure is found for Chaghri and it has little overhead compared with the original design. Since more and more symmetric primitives defined over a large finite field are emerging, we believe our new technique can have more applications in the future research.

Note: Correct some mistakes

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Chaghri degree evaluation coefficient grouping optimization problem finite field
Contact author(s)
liufukangs @ gmail com
ravianandsps @ gmail com
wanglibo12b @ gmail com
willimeier48 @ gmail com
takanori isobe @ ai u-hyogo ac jp
History
2022-10-03: last of 6 revisions
See all versions
Short URL
https://ia.cr/2022/991

CC BY

BibTeX

@misc{cryptoeprint:2022/991,
author = {Fukang Liu and Ravi Anand and Libo Wang and Willi Meier and Takanori Isobe},
title = {Coefficient Grouping: Breaking Chaghri and More},
howpublished = {Cryptology ePrint Archive, Paper 2022/991},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/991}},
url = {https://eprint.iacr.org/2022/991}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.