Plum: SNARK-Friendly Post-Quantum Signature Based on Power Residue PRFs
摘要
We design a SNARK-friendly post-quantum signature scheme based on the Power Residue PRF, called PLUM, which improves upon the Legendre PRF-based signature scheme known as Loquat. In particular, we introduce three key optimizations. Firstly, by replacing the Legendre PRF with a t-th power residue PRF, which reduces the number of public key symbols that need to be checked, the maximum degree of the polynomials involved in the univariate sumcheck is hence dropped by half. Secondly, we adopt STIR, a more advanced low-degree testing protocol, leveraging its lower query complexity and reduced code rate after folding to shorten signature size and runtime. Thirdly, we carefully select the prime which directly supports a large enough smooth subgroup for STIR, eliminating the need for field conversions in Loquat. Overall, we demonstrate that the t-th power residue PRF enables significantly more efficient in-SNARK verification compared to the Legendre PRF. We evaluate PLUM against Loquat across three security levels (80-bit,100-bit,128-bit), demonstrating consistent and significant improvements in signature size, signing/verification time, and SNARK-friendliness. Targeting 128-bit security, signature size of PLUM is 1.5 times smaller than that of Loquat. In both signing and verification time, PLUM is expected to be up to 4 times faster than Loquat; Verifying a PLUM signature requires approximately 116K R1CS constraints, which is 1.28 times fewer than Loquat, making it more SNARK-friendly. These improvements make PLUM a drop-in replacement for Loquat, offering strictly better performance while maintaining the same security guarantees.