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)
“Canst thou not minister to a mind diseased,
Pluck from the memory a rooted sorrow,
Raze out the written troubles of the brain,
And with some sweet oblivious antidote
Cleanse the fraught bosom of that perilous stuff
Which weighs upon the heart?”
—William Shakespeare (1564–1616)
“I have proceeded ... to prevent the lapse from ... the point of blending between wakefulness and sleep.... Not ... that I can render the point more than a point—but that I can startle myself ... into wakefulness—and thus transfer the point ... into the realm of Memory—convey its impressions,... to a situation where ... I can survey them with the eye of analysis.”
—Edgar Allan Poe (1809–1849)