Could you not use zk-STARK for a post-quantum signature scheme?

Your private key is a random symmetric encryption key, your public key is the hash of the encryption key.

To sign you run an algorithm to encrypt a hash of data-to-be-signed with your private key and hash your private key to obtain the public key.

The signature consists of the encrypted hash, and zk-STARK proof of the algorithm execution trace and output.

Even if the signature size would be greater than SPHINCS+, verification of signature should be much faster?


1 Answer 1


What you describe is not that different from the Picnic signature algorithm that was entered into the NIST PQC process. Here a signature is zero-knowledge proof of block cipher encryption performed using "in the head" multi-party encryption. The signing key is the key for the block cipher.

Picnic was selected as a third round alternate in the digital signature part of the NIST process and although (to my knowledge) no serious security issues have been found with concept of ZKP of MPC-in-the-head signature schemes, the block cipher LowMC that was selected for Picnic for efficiency reasons was not felt to be mature in its security. The NIST 3rd round report states

Overall assessment. Picnic and SPHINCS+ were the two candidate signature schemes that relied mostly on the security of symmetric primitives. NIST chose SPHINCS+ largely because it could not confidently quantify the security of LowMC and because future cryptosystems that evolve out of the multi-party-computation-in- the-head paradigm may eventually prove significantly superior to the third-round Picnic design.

Additionally, although the signing/verification key sizes are very small in Picnic, the signature size is very large indeed (see table 9 in appendix D of the NIST document).

  • $\begingroup$ Note that using a zk-STARK, the signature size would likely be one or two orders of magnitude bigger than what you get using MPCitH. In general, a good rule of thumb is that succinct arguments (STARKs & friends) are preferred for medium to large circuits, where their sublinearity "kicks in" and compensates the large constants, while methods such as MPCitH (linear communication but small constants) will be much better for small circuits. For signatures, where we just want to prove knowledge of a preimage to a OWF, a small circuit typically suffices. $\endgroup$ Commented Oct 29, 2023 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.