Understanding Zero-knowledge proofs through illustrated examples • Hacker News Board

Re: Understanding Zero-knowledge proofs through illustrated examples

#31

Post by kemyke » Thu, Dec 02, 2021, 9:17 PM UTC

wutbrodo wrote: post #29

kemyke wrote: post #27

In the sudoku exapmle how can Bob be sure that the three face down cards in a cell are three identcal card? Without this knowledge, it is easy to pass the final validations without a correct solution.

Each pile has three solutions in it, and you're asking how we know that all three solutions align to the same number, as required by Sudoku. > Starting with each row, Bob randomly chooses one card in each cell, from the top, the middle, or the bottom The random assignment of solutions from each pile to each of the three problems means that the only way to consistently pass the test is to have the three solutions in e…

Oh, I missed that part, now its clear.

Re: Understanding Zero-knowledge proofs through illustrated examples

#32

Post by wutbrodo » Thu, Dec 02, 2021, 9:19 PM UTC

dcow wrote: post #28

jtsiskin wrote: post #26

Earlier quoted context omitted.

Alice should properly reject that proposal, and only accept pages with totally uniform watermarks.

So in essence, Alice must also verify that, for any given puzzle, it has been constructed in a way such that Bob cannot discern the information that is intended to be private? That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case. What’s the solution, an oligopoly of Proof Authorities?

> That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case.

The general public isn't involved in constructing the proofs, just as they don't manually engage in cryptographic exchanges of any kind. Absent cryptographic expertise, the general public is forced to delegate their trust to cryptographic experts, whose code they execute when making exchanges with tricksters.

Re: Understanding Zero-knowledge proofs through illustrated examples

#33

Post by SilasX » Thu, Dec 02, 2021, 9:27 PM UTC

Kranar wrote: post #14

aan1092j wrote: post #9

Earlier quoted context omitted.

For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then constructing a PCP (Probabilistically checkable proof). T̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶o̶f̶ ̶d̶e̶t̶e̶r̶m̶i̶n̶i̶n̶g̶ ̶w̶h̶e̶t̶h̶e̶r̶ ̶y̶o̶u̶ ̶c̶a̶n̶ ̶f̶o̶r̶c̶e̶ ̶a̶ ̶c̶h̶e̶c̶k̶m̶a̶t̶e̶ ̶i̶n̶ ̶N̶ ̶m̶o̶v̶e̶s̶ ̶i̶s̶ ̶i̶n̶ ̶N̶P̶,̶ ̶s̶i̶n̶c̶e̶ ̶g̶i̶v̶e̶n̶ ̶a̶ ̶c̶a̶n̶d̶i̶d̶a̶t̶e̶ ̶…

Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves. To the best that anyone knows, for a generalized chess board of size WxW, to…

Good catch, I was scratching my head at the parent comment since I was pretty sure chess isn't in NP, so thanks for confirming and explaining why it's not.

Re: Understanding Zero-knowledge proofs through illustrated examples

#34

Post by c0742e9366 » Thu, Dec 02, 2021, 9:29 PM UTC

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

ZKP inherit this definition from the complexity class of interactive proofs (IP) that is usually defined this way. As pointed out in a comment below, IP = PSPACE. Interestingly enough, changing the definition of IP to perfect correctness (1 instead of 2/3) does not make IP any weaker. However, requiring perfect soundness (0 instead of 1/3) would result in IP = NP.

Re: Understanding Zero-knowledge proofs through illustrated examples

#35

Post by debbiedowner » Thu, Dec 02, 2021, 9:30 PM UTC

Is there an analogue for this to show that a person must know something even if they pretend they don't?

Say I'm a middle man escrow service with an untrusted channel, and trusted A has sold a secret X to untrusted B using me, and B now wants to sell X to untrusted C on my platform. Is there a ZKP way to both make sure B doesn't scam C by sending a fake secret, and C doesn't scam B by saying they received a fake secret? Obviously while me and snoopers never knowing what X is?

Re: Understanding Zero-knowledge proofs through illustrated examples

#36

Post by cmehdy » Thu, Dec 02, 2021, 9:41 PM UTC

SilasX wrote: post #6

A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (usually desirable) property that it's only convincing to Bob. You instead have Bob randomly choose whether Alice must a) pull off the screen, revealing the original page, or b) punch a hole through to Waldo, but not both. Then you can do any number of rounds of…

After reading your post I understand that the challenge to show the picture is to test for a fake picture (one with only Waldo for example), so that makes more sense to me. Bob is just allowed to make sure the hidden image that Alice uses is the original (and she can still cheat when Bob choses the other option but the probabilities of succeeding the tricks become vanishingly small with tries, which is the point).

And I assume the screen is meant to always cover the picture (i.e. MUST be much larger than the picture) and only Alice can know the actual coordinates of the picture behind the larger screen (otherwise Bob can infer the position of the Waldo), right? It is also possible that I have not understood something from your interesting proof there.

Thanks for sharing the discussion about the finer points of ZKP being only between Alice and Bob.

Re: Understanding Zero-knowledge proofs through illustrated examples

#37

Post by dcow » Thu, Dec 02, 2021, 9:43 PM UTC

wutbrodo wrote: post #32

dcow wrote: post #28

Earlier quoted context omitted.

So in essence, Alice must also verify that, for any given puzzle, it has been constructed in a way such that Bob cannot discern the information that is intended to be private? That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case. What’s the solution, an oligopoly of Proof Authorities?

> That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case. The general public isn't involved in constructing the proofs, just as they don't manually engage in cryptographic exchanges of any kind. Absent cryptographic expertise, the general public is forced to delegate their trust to cryptographic experts, whose code they execute when making excha…

Sounds like you are saying ZKPs won’t be generally applicable and instead that these proofs have to be specifically crafted for a given application use case much like how you choose an acceptable cipher suite today?

Like I go to website A and they want me to authenticate that I have access to a unique email address without revealing which one and they offer a zkp-email-ident challenge, I’d have to use OpenZKP which supports zkp-email-ident because the cryptography community vetted it and thus it’s included as a supported auth challenge? So the implication here would be that the protocol specifies the exact nature of the (back to the cutout example) image such that it’s impossible for Bob to apply an adversarial watermark?

So generally ZKPs are more like a cryptography primitive and protocols must be developed that apply them in ways that mitigate adversaries.

Re: Understanding Zero-knowledge proofs through illustrated examples

#38

Post by Dylan16807 » Thu, Dec 02, 2021, 9:44 PM UTC

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

> In other words, you could theoretically have no knowledge and just get astronomically lucky to an arbitrary degree (whatever degree it would take to cross that proof threshold).

Even if you remove all the statistical nature from the system: They're trying to prove they have a piece of knowledge of finite size. If astronomical luck is a real concern, then you have to worry that even a non-probabilistic prover could have just guessed the knowledge.

Or as an analogy, even if you had a perfect and magically irreversible hash, someone could still guess the password first try.

Re: Understanding Zero-knowledge proofs through illustrated examples

#39

Post by frazbin » Thu, Dec 02, 2021, 9:48 PM UTC

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

Sure but by the same token I could guess a 256 bit key and decrypt anything I want. The placement of the statistical boundary vs a given adversary compute power is the part we care about, every time.

Re: Understanding Zero-knowledge proofs through illustrated examples

#40

Post by SilasX » Thu, Dec 02, 2021, 9:54 PM UTC

cmehdy wrote: post #36

SilasX wrote: post #6

A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (usually desirable) property that it's only convincing to Bob. You instead have Bob randomly choose whether Alice must a) pull off the screen, revealing the original page, or b) punch a hole through to Waldo, but not both. Then you can do any number of rounds of…

After reading your post I understand that the challenge to show the picture is to test for a fake picture (one with only Waldo for example), so that makes more sense to me. Bob is just allowed to make sure the hidden image that Alice uses is the original (and she can still cheat when Bob choses the other option but the probabilities of succeeding the tricks become vanishingly small with tries, which is the point). An…

That's correct. Ideally you'd want a screen with double the dimensions so that you can designate a portion of it with uniform probability of any location having Waldo.

And my model has it so that (for the second challenge) Bob learns the position of Waldo relative to the screen, but not the position of Waldo relative to the page, which is what we mean by "finding Waldo". And, of course, on that challenge, Bob would not get to learn the position of the page relative to the screen (which would allow him to "find Waldo").