Non-interactive zero-knowledge proof

Non-interactive zero-knowledge proofs are a variant of zero-knowledge proofs in which no interaction is necessary between prover and verifier. Blum, Feldman, and Micali showed that a common reference string shared between the prover and the verifier is enough to achieve computational zero-knowledge without requiring interaction. Goldreich and Oren gave impossibility results for one shot zero-knowledge protocols in the standard model. In 2003, Goldwasser and Kalai published an instance of an identification scheme for which any hash function will yield an insecure digital signature scheme. These results are not contradictory, as the impossibility result of Goldreich and Oren does not hold in the common reference string model or the random oracle model. Non-interactive zero-knowledge proofs however show a separation between the cryptographic tasks that can be achieved in the standard model and those that can be achieved in 'more powerful' extended models.

The model influences the properties that can be obtained from a zero-knowledge protocol. Pass showed that in the common reference string model non-interactive zero-knowledge protocols do not preserve all of the properties of interactive zero-knowledge protocols; e.g., they do not preserve deniability.

Non-interactive zero-knowledge proofs can also be obtained in the random oracle model using the Fiat–Shamir heuristic. The article introduced the acronym zk-SNARK for zero-knowledge Succinct Non-interactive ARgument of Knowledge that are the backbone of the Zcash protocol.

In 2017, Bulletproofs was released, which enable proving that a committed value is in a range using a logarithmic (in the bit length of the range) number of field and group elements.

Originally, non-interactive zero-knowledge was only defined as a single theorem proof system. In such a system each proof requires its own fresh common reference string. A common reference string in general is not a random string. It may, for instance, consist of randomly chosen group elements that all protocol parties use. Although the group elements are random, the reference string is not as it contains a certain structure (e.g., group elements) that is distinguishable from randomness. Subsequently, Feige, Lapidot, and Shamir introduced multi-theorem zero-knowledge proofs as a more versatile notion for non-interactive zero knowledge proofs.

...
Wikipedia