Oblivious Transfer (OT)Oblivious Transfer allows Bob to select data from Alice, but for Alice not to know which value has been selected.
|
Basic Method
So, we are Bob the Investigator and investigating a serious crime, and we suspect that Eve is the person who is involved in the crime. We now need to approach her employer (Alice) and ask for some information on her. So how do we do this without Alice knowing that we suspect Eve? Well oblivious transfer (OT) performs this. Let's say that HackerZForU employ Eve and Trent, and we are only interested in getting information on Eve. Alice runs the company.
Now the method we will use is based on the Diffie-Hellman key exchange (DHE) method, but is modified so that we generated two keys for Alice to pass the data. One will work and the other will be useless. Alice will have no idea which of the keys will work, and the information that we can look at. In this case we'll ask for data from both Eve and Trent, and Alice will not know which of them is the suspect.
First Alice and Bob generate random numbers (\(a\) and \(b\)) and agree on a prime number (\(N\)). Alice then takes a generator value of \(g\) and raises it to the power of \(a\) [1]:
\(A = g^a \pmod N \)
She passes this to Bob. If Bob is interested in the first record he calculates \(g\) to the power \(b\), else if it is the second record, he calculates the value passed from Alice (A), and multiplies this value with \(g\) to the power of \(b\). Bob then sends one of these back:
\( if (c==0): B = g^b \pmod N \)
\( if (c==1): B = A \times g^b \pmod N \)
Alice receives the value from Bob (\(B\)). She then calculates two keys: the hash of \(B\) to the power of \(a\), and the hash of \(\frac{B}{A}\) to the power of \(a\).
\( K_0 = \text{Hash}(B^a \pmod N )\)
\( K_1 = \text{Hash}((B/A)^a \pmod N )\)
In this case, we can determine the inverse of \(A \pmod N\) and then multiple the value with \(B\). She then encrypts the two messages (\(M_0\) and \(M_1\)) with each of the keys, and returns the ciphers to Bob.
\( e_0 = E_{K_0}(M_0)\)
\( e_1 = E_{K_1}(M_1)\)
Bob calculates the decryption key (which will only work for one of the them) as the hash of \(A\) to the power of \(b\):
\( K_{bob} = \text{Hash}(A^b \pmod N )\)
Bob will then try to decrypt the two ciphers with \( K_{bob}\) and only one will work.
Presentation
References
[1] Chou, T., & Orlandi, C. (2015, August). The simplest protocol for oblivious transfer. In International Conference on Cryptology and Information Security in Latin America (pp. 40–58). Springer, Cham.