Two party protocol using only hash function

Question

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

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)