I have been told by my professor to compare two passwords as we do it in Yao's two-party protocol but without using any crypto functions. We are only allowed to use a hash function. The passwords are taken from the dictionary so we can't even send the hash of that word as we can't risk a dictionary attack. I am thinking of changing the alphabets to ASCII code and then pass it down the garbled circuit using Yao's protocol but don't know whether it will work. Any suggestions? Thanks


1 Answer 1


That is impossible (at least as I understand your question) because:

  • The ability to privately test whether two strings are equal (even if just 2 bits, even with security only against semi-honest parties) implies oblivious transfer. (Kilian: A general completeness theorem for two party games)

  • It's impossible to realize oblivious transfer from hash functions alone. More formally, the "Minicrypt" model is that all parties have access to a random oracle and are computationally unbounded -- this model captures all the things you can get from one-way functions, hash functions, "without any other stronger kinds of crypto." Oblivious transfer is impossible in Minicrypt. (OT implies all secure function evaluation which implies key agreement which is impossible in Minicrypt: Impagliazzo-Rudich Limits on the provable consequences of one-way permutations)

  • $\begingroup$ Design a protocol to solve each of the following problems, using only a hash algorithm.but they do not have access to any other cryptographic primitives (no public-key encryption, for example.) Alice and Bob have both chosen an English word as a password and they both want to determine if they have chosen the same word, without revealing their words. Sharing hashes of their words could brute-force attack. Find a way that the two can decide if their words are the same, but without allowing either party to guess the other’s word if they are not the same. $\endgroup$ Commented Feb 29, 2020 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.