Editing Interactive proof system (section)

=== Zero knowledge ===
{{main|Zero-knowledge proof}}
Not only can interactive proof systems solve problems not believed to be in '''NP''', but under assumptions about the existence of [[one-way function]]s, a prover can convince the verifier of the solution without ever giving the verifier information about the solution. This is important when the verifier cannot be trusted with the full solution.  At first it seems impossible that the verifier could be convinced that there is a solution when the verifier has not seen a certificate, but such proofs, known as [[zero-knowledge proof]]s are in fact believed to exist for all problems in '''NP''' and are valuable in [[cryptography]]. Zero-knowledge proofs were first mentioned in the original 1985 paper on '''IP''' by Goldwasser, Micali and Rackoff for specific number theoretic languages. The extent of their power was however shown by [[Oded Goldreich]], [[Silvio Micali]] and [[Avi Wigderson]].<ref name="O. Goldreich, S. Micali 1991"/> for all of '''NP''', and this was first extended by [[Russell Impagliazzo]] and [[Moti Yung]] to all '''IP'''.<ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51 [https://link.springer.com/chapter/10.1007%2F3-540-48184-2_4]</ref>