[Resource Topic] 2022/991: Coefficient Grouping: Breaking Chaghri and More

Welcome to the resource topic for 2022/991

Coefficient Grouping: Breaking Chaghri and More

Authors: Fukang Liu, Ravi Anand, Libo Wang, Willi Meier, Takanori Isobe


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.

ePrint: https://eprint.iacr.org/2022/991

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .