Paper 2022/991

Coefficient Grouping: Breaking Chaghri and More

Fukang Liu
Ravi Anand
Libo Wang
Willi Meier
Takanori Isobe
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 with time complexity of about $2^{119.6}$. 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: Fix some typos.

Metadata
Available format(s)
PDF
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-08-06: last of 2 revisions
2022-08-03: received
See all versions
Short URL
https://ia.cr/2022/991
License
Creative Commons Attribution
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.