Paper 2026/2935
A Key Recovery Attack on TRIKE Based on Decoding Failures
Abstract
TRIKE is a code-based Key Encapsulation Mechanism submitted to the Next-Generation Commercial Cryptographic algorithms (NGCC) standardization program currently run in People's Republic of China. TRIKE, similarly to other Quasi Cyclic Moderate Density Parity Check (QC-MDPC) code-based KEMs such as BIKE, is built with a decryption procedure which recovers a sparse error vector (i.e., the message) given its syndrome (i.e., the ciphertext) through a secret sparse parity-check matrix, employing an iterative bit-flipping decoder. Differently from BIKE, TRIKE employs a QC-MDPC matrix with a different structure, allowing them to improve the decoding, and hence the decryption, time. In order to guarantee IND-CCA security, the code length is chosen in order to reduce the Decoding Failure Rate (DFR) below $2^{-\lambda}$, where $\lambda$ is the bit security level; such a DFR is estimated with extrapolation techniques. In this work, we show that the QC-MDPC codes employed in TRIKE are affected by the so-called near codewords phenomenon. We provide a lower bound on the DFR given by such near codewords, showing that the DFR of TRIKE is significantly higher than the required value for all parameter sets. This alone constitutes a breach of IND-CCA security requirements. We propose a key recovery attack based on near codeword-induced decoding failures. For NGCC security level $1$, $\lambda=128$, the attack requires less than $2^{80}$ (random) ciphertexts and lowers the hardness of the static key recovery step down to $2^{65.52}$ bit operations. We validate our attack strategy and complexity estimation on a toy parameter set with extrapolated DFR below $2^{-80}$, recovering the secret key with $2^{29.50}$ decryption queries.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Code-based cryptographyDecoding Failure RateTRIKE
- Contact author(s)
-
alessandro annechini @ polimi it
alessandro barenghi @ polimi it
gerardo pelosi @ polimi it - History
- 2026-11-22: approved
- 2026-11-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2935
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2935,
author = {Alessandro Annechini and Alessandro Barenghi and Gerardo Pelosi},
title = {A Key Recovery Attack on {TRIKE} Based on Decoding Failures},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2935},
year = {2026},
url = {https://eprint.iacr.org/2026/2935}
}