How can Peggy prove she knows one of Victor's passwords in zero knowledge?

Question

Say Peggy wants to prove to Victor that she knows one of his passwords. She doesn't want Victor to know which password she knows, because she knows that some passwords are more valuable to Victor than others, and wants to keep the advantage that Victor doesn't know which of his passwords she knows.

Victor wants to verify that Peggy knows one of his passwords to ensure she's not lying, but he also doesn't want Peggy to trick him into giving her any knowledge of what passwords he has/doesn't have. That is, he doesn't want to send her anything that she could use to verify that she actually does have one of his passwords, or that she could use to perform a brute force attack and reveal any additional information about his passwords.

Is there a way to prove this in zero knowledge?

Answer 1

Yes, there is.

Assuming Peggy and Victor will be honest about their inputs, they can achieve exactly this functionality with garbled circuits. Victor can generate a circuit which will check for equality between Peggy's input and his list of passwords, then he proceeds to garble the circuit. Victor and Peggy cooperate in oblivious transfers for Peggy to get the circuit keys related to her input and she proceeds to evaluate the garbled circuit. She returns her output to Victor who can then clearly see whether or not the input Peggy provided is actually equal to one of his passwords, and he does not know which one. Such a protocol can be made maliciously secure as well.

It can also be implemented with secret sharing as well as other secure multiparty computation algorithms, but garbled circuits is usually one that is fairly intuitive for many.