Hacker News new | ask | show | jobs
by CDokolas 3687 days ago
Am I wrong or the phrase "a type of mathematical protocol for convincing someone that something is true without revealing any details of why it is true" is wrong and should be "a type of mathematical protocol for allowing someone to verify that something is true without revealing any details of how it is calculated to be true?"
2 comments

No, that's what a zero knowledge proof is; at the end of the protocol, you are convinced that some statement is either true or false, and learn nothing else about the "proof".

In NP-terms, you learn whether the NP instance is true (eg a 3SAT clause is satisfiable), but learn nothing about the witness (eg the assignment to the clause's variables).

So, which statement is right/better?
Not completely clear to me what you mean by "calculated to be true", but you may want to look at the difference between computational and statistical zero knowledge. A computational ZK proof hides the witness from computationally bounded (i.e. probabilistic polynomial time) adversaries. Statistical ZK, on the other hand, hides the witness from any adversary, even if they can carry out an unbounded amount of computations (there are slight subtleties there depending on the precise security model but that's the basic idea).
Also, why isn't "homomorphic encryption" mentioned at all since that's what this is all about?
Obfuscation is different from homomorphic encryption, and in some sense much more powerful.

With homomorphic encryption, Alice can send some secret data to Bob in encrypted form, and let Bob carry out computation on that encrypted data. However, the result of the computation remains encrypted, and only Alice's private key can decrypt the result.

By contrast, obfuscation allows Alice to give Bob a program that contains some secret information (such as cryptographic keys) in such a way that Bob can run it (without any further interaction with Alice) on any inputs of his choice, and get the result in the clear. However, he cannot learn anything about the hidden secret information other than what is revealed by the input-output pairs he has obtained.

It's not hard to see that obfuscation gives you homomorphic encryption for free (you can probably get a rough idea of how to do it based on the somewhat imprecise descriptions above), but we don't know how to go in the other direction. (Current obfuscation candidates do use fully homomorphic encryption under the hood, but they need to rely on much more than that).