Rabin's Oblivious Transfer Protocol
In Rabin's oblivious transfer protocol, the sender generates an RSA public modulus N=pq where p and q are large prime numbers, and an exponent e relatively prime to (p-1)(q-1). The sender encrypts the message m as me mod N.
- The sender sends N, e, and me mod N to the receiver.
- The receiver picks a random x modulo N and sends x2 mod N to the sender. Note that gcd(x,N)=1 with overwhelming probability, which ensures that there are 4 square roots of x2 mod N.
- The sender finds a square root y of x2 mod N and sends y to the receiver.
If the receiver finds y is neither x nor -x modulo N, the receiver will be able to factor N and therefore decrypt me to recover m (see Rabin encryption for more details). However, if y is x or -x mod N, the receiver will have no information about m beyond the encryption of it. Since every quadratic residue modulo N has four square roots, the probability that the receiver learns m is 1/2.
Read more about this topic: Oblivious Transfer
Famous quotes containing the words rabin, oblivious and/or transfer:
“Not only [are] our states ... making peace with each other,... you and I, your Majesty, are making peace here, our own peace, the peace of soldiers and the peace of friends.”
—Yitzhak Rabin (b. 1922)
“Better than mortal flowers,
Thy moon-kissed roses seem: better than love or sleep,
The star-crowned solitude of thine oblivious hours!”
—Ernest Christopher Dowson (1867–1900)
“No sociologist ... should think himself too good, even in his old age, to make tens of thousands of quite trivial computations in his head and perhaps for months at a time. One cannot with impunity try to transfer this task entirely to mechanical assistants if one wishes to figure something, even though the final result is often small indeed.”
—Max Weber (1864–1920)