In the PICNIC post-quantum signature scheme, a zero-knowledge proof of the secret key for a symmetric encryption is produced by implementing the encryption as a Yao garbled circuit of a three-party computation. The proof is to divide the key into three shares notionally split between three parties and produce transcripts of each party's actions in the computation and provided commitments to several such transcripts. A challenge is to pick two of the parties for each commitment and a response is to provide their transcripts so that the verifier can check that the computation is consistent. As the multi-party computation should not reveal anything about other parties' shares, the proof is zero knowledge.

There's no reason to limit to three parties and the framework would still hold with $m$ parties and revealing $m-1$ transcripts. What are the tradeoffs? Presumably fewer transcripts are required, but the transcripts are correspondingly more complex. Is this analysed somewhere?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.