Zero Knowledge
Not only can interactive proof systems solve problems not believed to be in NP, but under assumptions about the existence of one-way functions, 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 proofs 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, but the extent of their power was shown by Oded Goldreich, Silvio Micali and Avi Wigderson.
Read more about this topic: Interactive Proof System
Famous quotes containing the word knowledge:
“The endless cycle of idea and action,
Endless invention, endless experiment,
Brings knowledge of motion, but not of stillness;
Knowledge of speech, but not of silence;
Knowledge of words, and ignorance of the Word.
All our knowledge brings us nearer to our ignorance.”
—T.S. (Thomas Stearns)
“After I discovered the real life of mothers bore little resemblance to the plot outlined in most of the books and articles I’d read, I started relying on the expert advice of other mothers—especially those with sons a few years older than mine. This great body of knowledge is essentially an oral history, because anyone engaged in motherhood on a daily basis has no time to write an advice book about it.”
—Mary Kay Blakely (20th century)