  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 leveraging
structure paradigm along with its associated challenge space amplification
technique. Our new approach to design PoK brings some improvements over the PoK
with Helper one. Indeed, we show how one can substitute the Helper in these
constructions by leveraging the underlying structure of the considered problem.
This approach does not suffer from the performance overhead inherent to the PoK
with Helper paradigm hence offers different trade-offs between security,
signature sizes and performances. We also present four new post-quantum
signature schemes. The first one is based on a new PoK with Helper for the
Syndrome Decoding problem. It relies on ideas from [BGKM22] and [FJR21] and
improve the latter using a new technique that can be seen as performing some
cut-and-choose with a meet in the middle approach. The three other signatures
are based on our new PoK leveraging structure approach and as such illustrate
its versatility. We provide new PoK related to the Permuted Kernel Problem
(PKP), Syndrome Decoding (SD) problem and Rank Syndrome Decoding (RSD) problem.
In practice, these PoK lead to comparable or shorter signatures than existing
ones. Indeed, considering (public key + signature), we get sizes below 9kB for
our signature related to the PKP problem, below 15kB for our signature related
to the SD problem and below 7kB for our signature related to the RSD problem.
