Lesson 6

Under certain additional cryptographic assumptions (the existence of one-way functions), it can be shown that for all problems in the class NP, there is an interactive proof that convinces the verifier but does not reveal any information (about the proof of membership itself). This was proven by Oded Goldreich, Silvio Micali, and Avi Wigderson in 1991.

Zero-knowledge interactive proofs are the basis for the operation of some cryptocurrencies: when making a payment, it is necessary to prove that there are funds in the account without revealing anything about the amount or the sources of the funds.