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 world still wants its poet-priest, a reconciler, who shall not trifle with Shakspeare the player, nor shall grope in graves with Swedenborg the mourner; but who shall see, speak, and act, with equal inspiration. For knowledge will brighten the sunshine; right is more beautiful than private affection; and love is compatible with universal wisdom.”
—Ralph Waldo Emerson (1803–1882)
“If we consider what happens in conversation, in reveries, in remorse, in times of passion, in surprises, in the instructions of dreams, wherein often we see ourselves in masquerade,—the droll disguises only magnifying and enhancing a real element, and forcing it on our distinct notice,—we shall catch many hints that will broaden and lighten into knowledge of the secret of nature.”
—Ralph Waldo Emerson (1803–1882)