HAWK with Hint: Algebraic Key Recovery from Side-Channel Leakage

We investigate how partial physical leakage can be amplified through public algebraic relations, using HAWK as a concrete case study of implementation security in an algebraically structured post-quantum signature scheme. HAWK is a lightweight, floating-point-free lattice-based signature scheme whose discrete Gaussian sampler can expose side-channel information during signing. We formalize such leakage as HAWK with Hint and study full-coefficient, exact-sign, and noisy-sign leakage. Our polynomial-time recovery algorithms combine sampler hints with public signing information and HAWK's Gram-matrix public-key structure, showing that complete sampler-output recovery is not necessary for full key recovery. For HAWK-1024, we obtain the following results under the stated threat models. With full coefficient leakage, a single signature suffices for secret-key recovery by directly solving the induced linear system. On the HAWK-1024 reference implementation, we identify all 2,048 coefficient-sampler invocations in each of 14 measured signing traces, extract all 28,672 coefficient signs without error, and recover the fixed key using the Category II attack. In separate controlled experiments over 100 independently generated keys, Category II achieves 100% success using 14 exact-sign signatures in approximately 157 seconds. Under the independent sign-error model, Category III achieves 100% success using 420 signatures at a 10% error rate and 13,397 signatures at a 40% error rate. The latter setting requires approximately 178 seconds. These results show that coarse and even erroneous sampler leakage can become sufficient for full key recovery when combined with HAWK's public algebraic structure.