International Association
for Cryptologic Research

Many signature applications---such as root certificates, secure software updates, and authentication protocols---involve long-lived public keys that are transferred or installed once and then used for many verifications. This key longevity makes post-quantum signature schemes with conservative assumptions (e.g., structure-free lattices) attractive for long-term security. But many such schemes, especially those with short signatures, suffer from extremely large public keys. Even in scenarios where bandwidth is not a major concern, large keys increase storage costs and slow down verification. We address this with a method to replace large public keys in GPV-style signatures with smaller, private verification keys. This significantly reduces verifier storage and runtime while preserving security. Applied to the conservative, short-signature schemes \Wave and \Squirrels, our method compresses \Squirrels[-I] keys from \SI{665}{\kilo\byte} to \SI{20.7}{\kilo\byte} and \Wave[822] keys from \SI{3.5}{\mega\byte} to \SI{207.97}{\kilo\byte}.