Information theory and zero-knowledge proof
2022 Feb 15-17
1. In essence, information theory characterizes what one learns by acquiring information. The learning process involves elimination of alternatives, uncertainties.
2. Zero-knowledge takes into account privacy, or ownership of information. The prover proves to the verifier only the fact that she knows the information without revealing any extra bits about it. The verifier in the meantime can be certain with high probability that the prover indeed knows the information bit.
- I have a question, does every single bit of information have a zero knowledge proof system?
- All languages in NP have a ZKP.
- How about languages in P?
- P is in NP. It makes no sense to prove ZK for a statement in P, because the verifier can compute the witness or check if the statement is in P himself.
- I think what I actually wanted to ask is that
if I have private knowledge about something with low entropy, e.g., Snoopy's birth month, can I prove it to someone else without revealing extra information? In this case, I felt it's hard to make the witness ensure both soundness and zk (as you mentioned)
I was reading through information theory where one learns things through acquiring information. Then i thought about what happens if the external world cares about ownership of information and does not let you learn freely. Is this correct?: if the knowledge is in NP\P (assuming ...), then it's possible that we do not have actual information gain; if the knowledge is in P, then we most likely learn what we need to learn.
3. Private knowledge is not necessarily structured. P/NP languages are structured and can be decided through algorithms/Turing machines.
I went to read this book again: introduction to theory of computation by Michael Sipser.
I think not all statements are structured in the sense that they can be expressed with explicit starting state, state transitions and terminating states. If I say Snoopy is born in July, the machine has to first encode July in the set of terminating state, which means that proving the statement is not necessary since the machine knows it already. Although the statement carries some information, it is not recognizable by a machine that does not have the knowledge beforehand.
For structured information in P, e.g., "4-1=3", the question is different. I find it hard to resolve what ZK means in this case. Maybe I can compute the witness, embed it in some NP problem (e.g., quadratic residue, 3^2 mod n) then provide the latter as witness, so that the verifier needs to compute the witness itself first then verify. But I don't see much point in doing this.