Oblivious Transfer à la Merkle
Gilles Brassard, Louis Salvail, Alain Tapp · 2009
Oblivious transfer (OT) is a fundamental primitive in cryptography. It is known that unconditionally secure OT is impossible, even with the help of quantum mechanics. Furthermore, no classical OT scheme has been proven to offer computational security in the usual super-polynomial model, and there is evidence that such schemes cannot be based on one-way permutations. Nevertheless, inspired by Ralph Merkle's 1974 key distribution scheme, we offer a novel classical OT scheme based on one-way permutations and prove its polynomial security: the effort to cheat it scales as t3/2, where t is the legitimate effort needed to implement it. Unfortunately, our scheme melts down under the onslaught of a quantum adversary after an effort merely in the order of t5/6, so that it is actually easier to subvert it than to use it legitimately! By allowing the honest parties to use quantum computation as well, however, it may be that our OT scheme can be repaired so as to resist modest quantum attacks.