Hacker News Reader

Comment by dvt | Hacker News Reader

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 completeness in the metamathematical sense. That's a statistical boundary on what it takes to "convince" someone (or "gain knowledge"). But that's a stochastic redefinition of a pretty hard-line property of proof systems. 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).

[1] https://crypto.stanford.edu/cs355/18sp/lec3.pdf

View on HN

> 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.

In many applications of zero knowledge proofs, you prove knowledge of solution to a puzzle that need not have a solution. E.g. graph isomorphism, a 3-coloring, a Sudoko puzzle. So the probability of guessing the solution can be 0, while there's a nonzero probability of convincing a verifier.

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.

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.

Yes, these proof protocols allow you to get arbitrary certainty very quickly, so there’s little practical difference.

Scott Aaronson (of quantum computing and P=NP blogging fame) likes to joke that, “okay, fine fine, so these statistical proofs are good enough for the launch codes, military encryption, and multi-billion dollar financial transactions… but what about theorem proving, where you just can’t take any chances?”

Hence why this is a completeness "probability". In practice this is fine as alternative mechanisms to prove such things as identity involve mechanisms like signatures and hashes, which also can be guessed.

But isn't that how RSA works? Generate pseudoprimes - prove that they "should" be primes. That doesn't sound like "completeness" either but all modern asymmetric encryption uses public keys.

Right, but that astronomical probability is, as you say astronomical. In fact, it’s even better: even i have you a number of trials equal to the number of atoms in the h overs, your expected number of wins would still be astronomically small.

With that way of thinking nothing is secure because random byte generator can reveal it.

Note that it's true for any cryptographic algorithm.

Reply on news.ycombinator.com