More Balanced Polynomials: Cube Attacks on 810- And 825-Round Trivium with Practical Complexities

The key step of the cube attack is to recover the special polynomial, the superpoly, of the target cipher. In particular, the balanced superpoly, in which there exists at least one secret variable as a single monomial and none of the other monomials contain this variable, can be exploited to reveal one-bit information about the key bits. However, as the number of rounds grows, it becomes increasingly difficult to find such balanced superpolies. Consequently, traditional methods of searching for balanced superpolies soon hit a bottleneck. Aiming at performing a cube attack on more rounds of Trivium with a practical complexity, in this paper, we present three techniques to obtain sufficient balanced polynomials. To illustrate the power of our techniques, we search for balanced polynomials for 810- and 825-round Trivium. As a result, we can mount cube attacks against 810- and 825-round Trivium with the time complexity of \(2^{44.17}\) and \(2^{53.17}\) round-reduced Trivium initializations, respectively, which can be verified in 48 min and 18 days on a PC with one A100 GPU. For the same level of time complexity, this improves the previous best results by 2 and 5 rounds, respectively.