Henry Bambury – Polytopes in the Fiat-Shamir with Aborts Paradigm

Post-quantum digital signatures have sparked a lot of interest in the cryptographic community in recent years. Both the NIST-selected signature Dilithium and Heatae, winner of the Korean PQC competition, rely on hardness of lattice problems and employ the Fiat-Shamir with Aborts paradigm, in which rejection sampling is used to eliminate a secret’s dependency on a given source distribution. The distribution used to conceal the secret has direct consequences on signature performances, such as size, speed and simplicity. Dilithium uses a simple hypercube uniform sampler, while Haetae improves signature sizes by using a significantly more complex sampler based on Euclidean balls. In this work, we propose a framework relying on uniform sampling in polytopes, and use it to instantiate a new signature scheme: Patronus. Patronus acts as a tradeoff between both standards, offering improved signature sizes compared to Dilithium, while using a sampler that is much simpler than Haetae’s, as it avoids the need for Gaussian sampling.