International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Coefficient Grouping: Breaking Chaghri and More

Authors:
Fukang Liu , Tokyo Institute of Technology; University of Hyogo
Ravi Anand , University of Hyogo
Libo Wang , University of Hyogo
Willi Meier , FHNW
Takanori Isobe , University of Hyogo; NICT; PRESTO
Download:
DOI: 10.1007/978-3-031-30634-1_10 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
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.
BibTeX
@inproceedings{eurocrypt-2023-32823,
  title={Coefficient Grouping: Breaking Chaghri and More},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30634-1_10},
  author={Fukang Liu and Ravi Anand and Libo Wang and Willi Meier and Takanori Isobe},
  year=2023
}