Score:0

A cryptographic proof system which uses rewinding to argue soundness but is not a proof of knowledge?

sn flag

Are there any cryptographic proof systems that rewind the prover to argue soundness but are not proofs of knowledge? In particular, I would be very curious to see examples of proof systems where rewinding is useful for arguing soundness but does not seem to suffice for witness extraction.

To give some nonexamples, Schnorr's discrete log proof of knowledge rewinds the prover to extract the discrete log, proving soundness. The classic 3-coloring ZK does not rewind to prove soundness and also does not extract the witness (I think it is possible to rewind and extract the witness, although it is not entirely trivial).

rozbb avatar
br flag
I believe the purpose of rewinding in general is to extract something and then use it later in the protocol. [Here's](https://www.iacr.org/archive/tcc2007/43920157/43920157.pdf) an example that uses rewinding for information theoretic MPC. See section 3
Matan Shtepel avatar
sn flag
@rozbb Thank you for your comment. I understand that, in general, rewinding is used for extraction. I was interested if it can be used in more interesting ways...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.