Content
In this article, the reliability of the NIZK “proof” system we constructed belongs to “Statistical Soundness”, and zero knowledge belongs to “Computational Zero-Knowledge”. What does this mean? This means that no matter how powerful the prover Alice is (or even hyperpolynomial), Alice still cannot cheat. However, if the verifier Bob has super computing power, then there is such a possibility: Bob extracts valuable "knowledge" from the proof.
What does this mean?
This means that for NIZK Proofs, its length must be longer than "knowledge", which is the witness in the NP problem. As long as Bob has enough computing power, he can decrypt the proof. For the "extractor", it also needs to extract the witness without interaction. The shortest NIZK Proofs proved to be the NIZK scheme constructed by Greg Gentry et al. using "fully homomorphic encryption" technology [GGI+14], and the length of the proof is only slightly larger than the length of the witness.
Can you construct a NIZK that proves that the size is smaller than the witness? The answer is YES!
There is also a type of NIZK system called NIZK Arguments: their reliability is "Computational Soundness", and zero knowledge belongs to "Perfect Zero-Knowledge" or "Statistical Zero-Knowledge". This shows that if Alice has strong computing power, then she has room for cheating, but because in the real world, we can greatly reduce the possibility of Alice cheating by increasing the security parameters, but it can achieve very extreme The zero-knowledge feature of Since the reliability is weakened, then we can continue to reduce the size of the proof.
Note: In this series, we do not deliberately distinguish between the two words "proof" and "argument". If you need to specify Arguments instead of Proofs, it will be specifically emphasized.
If we want to publish a NIZK proof to Github, if a hundred years later, the Github website is still there, and the computing power of the future computer has already made a qualitative leap, at this time, a NIZK Proof may be breached by computing power. , Leaking knowledge, and NIZK Argument is likely to remain safe.
The popular hot word-AR in zkSNARK refers to Argument.
NIZK Argument can realize O(1) constant-level length proof, that is, it has nothing to do with the length of the witness. However, this requires hiding more secrets in the CRS.