Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Having some trouble understanding the following line: “Alice conveys zero knowledge to Bob if Bob can sample from a distribution of messages that is computationally indistinguishable from the distribution of messages that Alice would send.”
From Page 122, https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf
Could someone give a practical example of this sentence?
Suppose in some protocol Alice is supposed to send an encryption of her special secret $s$ under a public key $pk$. She is sampling from the distribution of encryptions of $s$.
Bob can choose a random plaintext $r$ and encrypt it under $pk$. He is sampling from the distribution of encryptions of random plaintexts.
Even though Bob doesn't know Alice's special secret $s$, these two distributions are computationally indistinguishable (that's the basic definition of security for the encryption scheme). So this message (Alice's encryption of $s$) is zero-knowledge.
In a real example, you would have to simulate the entire exchange of all messages (called the transcript). It doesn't really work to simulate just one at a time, you have to capture correlations along messages if there are many rounds in the protocol.
Imagine Alice wants to prove to Bob that she is a good archer. The protocol to convince him is for Bob to paint a target on the wall, then Alice will fire an arrow into the bullseye. The "transcript" (the information that Bob leaves with) is a target painted on a wall with an arrow in the bullseye.
But Bob can generate the same distribution of transcripts without Alice's help! He can just put an arrow into the wall first and then paint a target around it. Hence, the protocol is "zero-knowledge."
