Talk:Proof of knowledge

Well, I'm just starting, and this is a complicated issue. I believe however that this is a important concept of modern cryptography, which requires some attention. I'm using it as an exercise for my technical writing skills, which may be contested, but everyone is welcome to improve on it. Markulf 23:53, 17 August 2006 (UTC)[reply]

It seems that completeness (termed non-triviality by Goldreich) is the same for both zero knowledge and proof of knowledge. Is this correct? It seems to me that proof of knowledge is zero knowledge with the additional property of validity (which is a stronger def of ZK soundness). Thus, ZK \subset PK. Am I correct? —Preceding unsigned comment added by 147.188.192.41 (talk) 16:00, 5 March 2008 (UTC)[reply]

PK does not say which hiding properties need to hold for the proof. i.e. it could we e.g. zero-knowledge or witness hiding. So I would rather say "sound interactive proof" \subset PK. --134.58.253.57 (talk) 16:24, 5 August 2009 (UTC)[reply]

Please provide more context for non-expert readers

Could somebody please add a link or an explanation of the concept of "witness"?

It may seem a burden having to write a general introduction to cryptography in every article about cryptographic concepts. However, sooner or later, some thought must be given to what knowledge you expect your readers to have, and where they may acquire it.

What should the lay reader understand by "if this something can be computed, given the machine as an input"? What machine? And how do you provide a machine as an input? Input to what? What does that imply, what can the prover or verifier do with a machine given as an input? What kind of knowledge are you even talking about? Obviously not names of celebrities...:) Cacadril (talk) 00:28, 23 April 2010 (UTC)[reply]

Non-interactive proofs of knowledge

This article opens with "In cryptography, a proof of knowledge is an interactive proof", however in other articles (e.g. Fiat-Shamir heuristic) we also refer to "non-interactive proofs of knowledge" (e.g. "More generally, the Fiat–Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into a non-interactive proof of knowledge. If the interactive proof is an identification protocol, then the non-interactive version can be used directly as a digital signature.").

So it seems to me that proofs of knowledge are not necessarily interactive and this article should be made more general to include discussions of both interactive and non-interactive proofs of knowledge. However, I am not a cryptographer so I won't change anything myself. Vegard (talk) 07:43, 16 March 2016 (UTC)[reply]

(Also, for a bit of context, an example of a non-interactive proof of knowledge that I had in mind was if I publish a hash of some secret document on twitter. When the document is later published, the twitter message with the hash of that document is a "proof" (intuitively) that I had access to the document (or, admittedly, just its hash) at the moment of the tweet.) Vegard (talk) 07:50, 16 March 2016 (UTC)[reply]

proof

how does a prover convince a verifier for the example in the Sigma protocol? Jackzhp (talk) 13:34, 11 May 2016 (UTC)[reply]

use pairing, it is doable. do we have to use pairing? Jackzhp (talk) 13:47, 11 May 2016 (UTC)[reply]

Origin of "sigma"

The notion that the name "sigma protocol" comes from the shape looking like the Greek letter sigma is, as far as I can tell, an urban myth. The origin of "sigma protocol" is Cramer's thesis (https://ir.cwi.nl/pub/21438) which states on page 29 in the footnote that Sigma refers to "zig-zag", symbolizing the three moves, with MA an abbreviation of "Merlin-Arthur" 145.116.136.63 (talk) 14:04, 5 December 2023 (UTC)[reply]