Computer Security and Cryptography

17.13 THE OBLIVIOUS TRANSFER

I attended a lecture by Professor Manuel Blum while at IBM Research in which he described this problem as follows; the Californians Alice and Bob are contemplating divorce and decide to toss coins to determine which of them receives the car, the child, the house, the dog, and so forth. Although Alice and Bob are now divorced, their names continue to be used in describing many two-party authentication protocols. I believe the idea first appeared in a report by Michael Rabin [1981]. In another variant [Blum, 1983] Alice and Bob wish to electronically fairly toss a coin.

17.13.1 Oblivious Transfer Protocol: Who Gets the Dog?

Step #1:    Alice chooses primes p, q and sends Bob their product N = pq. Bob's task is to factor N:

• If he is successful, the outcome of coin toss is in Bob's favor
• Otherwise, Alice wins.

Step #2:    Bob chooses randomly computes y = x² (modulo N) and sends y to Alice.

Step #3:    As Alice knows the factors of N, she can find all of the solutions of y² = n (module N) x, −x, z, −z. Alice randomly chooses one of the solutions with probability of ¼ and returns its value to Bob.

Step #4: If the solution returned to Bob is x or −x, then Bob has received no new information. If the solution returned to Bob is z or −z, then Bob computes gcd{x + z, N} (or gcd{x − z, N}) and determines the factors of N.

The probability of Bob's winning is ...