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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Plum: SNARK-Friendly Post-Quantum Signature Based on Power Residue PRFs

  • Xinyu Zhang,
  • Qishuang Fu,
  • Ron Steinfeld,
  • Joseph K. Liu,
  • Tsz Hon Yuen,
  • Man Ho Au

摘要

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.