Zeta-Transform Evaluation for Higher-Order Vanishing Key Recovery

Abstract

Hemmert's key-recovery algorithm for Classic McEliece is based on higher-order vanishing. It computes a basis of $\ker ({\tilde{\phi }}_A^{(p)})$, where $A=H^{\prime \prime \prime }$ is the shortened parity-check matrix used in the attack. For Classic McEliece parameters, this kernel computation is the dominant cost of the attack. We show that the sums defining ${\tilde{\phi }}_A^{(p)}$ can be evaluated, column by column, as weighted upper zeta transforms on the Boolean lattice. Since only selected levels of these transforms are required by ${\tilde{\phi }}_A^{(p)}$, restricting their evaluation to the band between level $p$ and the lowest required level yields exact evaluations of both ${\tilde{\phi }}_A^{(p)}$ and its transpose. Using the resulting truncated zeta-transform evaluation in the Wiedemann-based kernel computation reduces the cost of the repeated matrix--vector products without changing the overall key-recovery algorithm. The exact cost depends on the weight distribution of the non-pivot columns of $H^{\prime \prime \prime }$. We therefore consider two models: an all-one model, in which every relevant binary coordinate is active, and a Bernoulli$(1/2)$ model, in which the coordinates are independently active with probability $1/2$. For the five Classic McEliece parameter sets, our method reduces the estimated key-recovery cost by $14.09$--$41.19$ bits in the all-one model and by $7.25$--$22.48$ bits in the Bernoulli$(1/2)$ model.

arXiv comment7 pages