5 ms·
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).
by dvt 5y ago
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 https://crypto.stanford.edu/cs355/18sp/lec3.pdf
- saurik 5y agoHence 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.
- c0742e9366 5y agoZKP 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.
- frazbin 5y agoSure 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.
- SilasX 5y agoYes, 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?”
- Dylan16807 5y ago> 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.
- tromp 5y agoIn 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.
- baby 5y agoNote that it's true for any cryptographic algorithm.
- ransom1538 5y agoBut 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.
- Ar-Curunir 5y agoRight, 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.
- mirekrusin 5y agoWith that way of thinking nothing is secure because random byte generator can reveal it.