Compact Post-Quantum Signatures from Proofs of Knowledge leveraging Structure for the PKP, SD and RSD Problems. (arXiv:2204.02915v2 [cs.CR] UPDATED)

The MPC-in-the-head introduced in [IKOS07] has established itself as an
important paradigm to design efficient digital signatures. It has been
leveraged in the Picnic scheme [CDG+ 20] that reached the third round of the
NIST PQC Standardization process. It has also been used in [Beu20] to introduce
the Proof of Knowledge (PoK) with Helper paradigm. This construction permits to
design shorter signatures but induces a non negligible performance overhead as
it uses cut-and-choose. In this paper, we introduce the PoK …

post-quantum problems quantum signatures