I am trying to understand how signature scheme proposed to NIST, Picnic, works.

The proposal uses $\textsf{ZKboo}$ and $\textsf{ZKboo++}$ as their basis. I can see how the ZKPoK works, where the witness $x$ is some key for any block-cipher. A prover and a verifier can run a game based on MPC in the head such that they can re-encrypt some pre-define bitstring using $x$.

However, this is not quite intuitable translatable to Digital Signatures. For instance, the propossal suggests that I should use $H(r||m)$ as the protocols challenge. It is not clear however, what the response $z$ actually is?

In the presentations they cite easy examples such as the Fiat-Shamir transform to signal that a Signature Scheme can be easily (and naively) obtained. They even use the same terminology as when the transform is applied to the Schnorr protocol, signaling that it is enough to use the message as the challenge $e$. However it is not clear to me how this can be done, because I do not understand how to plug the challenge in. I think I am struggling to see the role of the challenge as a hash of the message during both Signing ($\textsf{Prove}$) and Verification ($\textsf{Verify}$).

How is this challenge being incorporated into $z$ (say, as an encryption using the witness as key)? What is actually $z$? And what is the equation being verified to check the validity of the signature?

Finally Kudos to the designers, I love the basic idea, I hope I manage to understand it better with your help!


1 Answer 1


There are a few steps involved in the design:

  1. design a sigma protocol with special soundness.
  2. transform the above sigma protocol to a nizkpok.
  3. use the above nizkpok to prove the possession of $x$, such that $F(0) = y$, where $y$ is the public key, $x$ is the private key, $F$ is a One Way Function (OWF).

The encryption is a Pseudo-Random Function (PRF) used to sample an OWF.

When talking about $H(r,m)$, $H$ is a (quantum) random oracle used in step 2 to obtain a nizkpok based on FS-transformation (Uhruh transformation).

The feature of Picnic is the use of MPC-in-the-head to obtain a sigma protocol with special soundness. This is done in few steps:

  1. prover emulate a number of semi-honest execution of MPC where each party has input as a secret share of the witness.
  2. prover commits to all views and states of all parties in all executions.
  3. verifier open a selected subset of parties from each execution and check that the parties are behaving honestly.

Intuitively, is the prover misbehave for some parties, it will be caught with some probability; on the other hand, the semi-honest security of the MPC protocol ensures that even if some parties are opened, no information on other parties inputs (and thus the witness) is revealed.

Given the above, one can see that the challenge is the set of parties to open, and the response are the decommitments to open the views of these parties.

  • $\begingroup$ Thanks so much for the answer. A short clarificiation that you may be albe to help me with: From the point of view of a Signature Scheme, how could I use the challenge c= H(r||m) to create the challenge i.e, to go from c to the set of parties whos View I want to open. $\endgroup$
    – DaWNFoRCe
    May 8, 2019 at 14:31
  • $\begingroup$ @DaWNFoRCe The challenge space is finite, so you can always assign an integer to each distinct challenge. Then use H() to derive a random integer to indicate which challenege it is. $\endgroup$
    – redplum
    May 8, 2019 at 20:15
  • $\begingroup$ So then I just generate k r's (random strings) for some security parameter k. Then calculate something like P_i = H(r_i||m) mod |P|. And thats it right? Then I send the commitments on the r's? Thnkas so much! Now I see why everybody said it was trivial. $\endgroup$
    – DaWNFoRCe
    May 9, 2019 at 6:38

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.