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)
“If it had not been for storytelling, the black family would not have survived. It was the responsibility of the Uncle Remus types to transfer philosophies, attitudes, values, and advice, by way of storytelling using creatures in the woods as symbols.”
—Jackie Torrence (b. 1944)