Paper 2025/1330 Original: eprint.iacr.org/2025/1330 ↗

Exploring Core Monomial Prediction Further: Weak-Key Superpoly Recovery for 852-Round Trivium

Abstract

The cube attack is one of the most powerful attacks on stream ciphers, with recovering the superpoly as its key step. The core monomial prediction is the state-of-the-art technique for superpoly recovery, which can reach 851 rounds for Trivium thus far (EUROCRYPT 2024). The core monomial prediction heavily relies on the trail enumeration which is the bottleneck for its efficiency. This paper further explores the potential of the core monomial prediction for Trivium by constructing a composite representation for the superpoly. This representation allows us to detect the algebraic structure of the superpoly under specific conditions on the intermediate variables, without the computational burden of trail enumerations. Leveraging these discovered conditions, we successfully recovered weak-key superpolies for 852-round Trivium, establishing the first cryptanalytic result against 852-round Trivium in the literature to date.