5 ms·

Remedial question about zero-knowledge proof. Isn't "proof" a misnomer since the concept is about just making it incredibly likely to be true?

eruleman 5y ago
No — the word 'proof' is accurate, it establishes with certainty that you know the value of x.
- Kranar 5y ago
  I thought you were right until I decided to look into it myself, turns out we were both wrong. Zero-knowledge proofs are probabilistic and contain a soundness error which is the probability of guessing the correct answer. This can, in some but not all cases, be brought down arbitrarily close to 0, but it can never be 0 exactly. https://en.wikipedia.org/wiki/Zero-knowledge_proof#Definition https://en.wikipedia.org/wiki/Zero-knowledge_proof#Definitio...
pcmonk 5y ago
That's why it's sometimes called an "argument" or specifically a "cryptographic proof". You can construct the statement such that it can be "proven" in a traditional sense by adding qualifiers such as "with probability more than 1-1/(2^256)". You'll generally need an assumption like knowledge-of-exponent or at least hash soundness.
db_admin 5y ago
In cryptography you prove security through showing that an adversary has a negligible [1] chance of winning a game of guess the secret. [1] https://crypto.stackexchange.com/questions/5832/what-exactly-is-a-negligible-and-non-negligible-function#5833 https://crypto.stackexchange.com/questions/5832/what-exactly...
dlubarov 5y ago
In the literature [*], the "proof" is an actual proof, but that's not what the prover sends to the verifier. Rather, the verifier queries random pieces of the proof, eventually convincing themselves that with high probability, the prover knows a valid proof. [*] At least in most of the older literature descending from the PCP literature. Modern papers sometimes abandon that distinction and just use "proof" and "argument" interchangeably.

eruleman 5y ago

No — the word 'proof' is accurate, it establishes with certainty that you know the value of x.

Kranar 5y ago
I thought you were right until I decided to look into it myself, turns out we were both wrong. Zero-knowledge proofs are probabilistic and contain a soundness error which is the probability of guessing the correct answer. This can, in some but not all cases, be brought down arbitrarily close to 0, but it can never be 0 exactly. https://en.wikipedia.org/wiki/Zero-knowledge_proof#Definition https://en.wikipedia.org/wiki/Zero-knowledge_proof#Definitio...

pcmonk 5y ago

That's why it's sometimes called an "argument" or specifically a "cryptographic proof". You can construct the statement such that it can be "proven" in a traditional sense by adding qualifiers such as "with probability more than 1-1/(2^256)". You'll generally need an assumption like knowledge-of-exponent or at least hash soundness.

db_admin 5y ago

In cryptography you prove security through showing that an adversary has a negligible [1] chance of winning a game of guess the secret. [1] https://crypto.stackexchange.com/questions/5832/what-exactly-is-a-negligible-and-non-negligible-function#5833 https://crypto.stackexchange.com/questions/5832/what-exactly...

dlubarov 5y ago

In the literature [*], the "proof" is an actual proof, but that's not what the prover sends to the verifier. Rather, the verifier queries random pieces of the proof, eventually convincing themselves that with high probability, the prover knows a valid proof. [*] At least in most of the older literature descending from the PCP literature. Modern papers sometimes abandon that distinction and just use "proof" and "argument" interchangeably.