Review: Yao's Protocol
In the last lecture, we learned most parts of Yao's protocol.
The above picture shows what's going on when Yao's protocol is run. The garbled
circuit and the key are not sanitized, but as we learned in the last lecture,
they can be sanitized as follows:
- Randomly shift the rows of each gate encryption table.
- Remove the associated value in each key.
Oblivious Transfer (OT)
What is left to cover the protocol for Oblivious Transfer. As is shown in the
picture, the input and output of OT are as follows:
- Input of Alice: Two messages \(m_0, m_1\).
- Input of Bob: A selection bit \(\sigma\).
- Output of Alice: None
- Output of Bob: \(m_\sigma\), that is, the message chosen according to the
selection bit \(\sigma\),
|
|
Security property of OT
- Alice should not know what Bob's selection \(\sigma\) was.
- Bob should not know what Alice's other input message \(m_{1-\sigma}\).
An OT Protocol Extending the Diffie-Hellman Key Exchange
Review: Diffie-Hellman Key Exhange
- Let \(p\) be a (safe) prime number.
- Let \(g\) be a generator for the multiplicative group \(\mathbb{Z}_p^*\).
Then the protocol proceeds as follows:
- Alice chooses a random exponent \(a\) from \(\{1, ..., p-1\}\), and
computes \(A = g^a \bmod p\). Alice sends \(A\) to Bob.
- Bob also chooses a random exponent \(b\) from \(\{1, ..., p-1\}\), and
computes \(B = g^b \bmod p\). Bob sends \(B\) to Alice.
The common secret key is computed as follows:
- Note that Alice has chosen \(a\), using which she can compute the key as
\(B^a \bmod p\).
- Note that Bob has chosen \(b\), using which he can compute the key as
\(A^b \bmod p\).
Note that \(B^a = (g^b)^a = g^{ab}\), and \(A^b = (g^a)^b = g^{ab}\).
Therefore, Alice and Bob will share the same key.
Extension Step 1: Prepare two different keys for sending \(m_0, m_1\)
We first extend the DH key exchange as follows:
- In addition to the key that DH normally generates (i.e., \(K_0 = B^a\)),
Alice prepares another key \(K_1 = (B/A)^a\).
- This is for the sake of sending two messages \(m_0\) and \(m_1\) with each
encrypted with a different key.
- For now, this is problematic for Bob. He can always reconstruct only
\(K_0\) and receive \(m_0\). As of now, he can never get \(m_1\).
- However, at least, one good thing is that Bob can decrypt only one of
the two messages.
- In the next step, we will see how to change Bob's message \(B\) to reflect
his selection bit \(\sigma\).
Extension Step 2: Change \(B\) to consider Bob's selection bit \(\sigma\)
- We have \(K_1 = (B/A)^a \).
- Note Bob can choose whatever \(B\) he needs to send Alice.
- To recover \(K_1\), it would be probably better to cancel out the
denominator \(1/A\), which will make the calculation simpler.
- So, let's set \(B = g^b \cdot A\).
- Then, we have
\[K_1 = (B/A)^a = (g^b \cdot A / A)^a = (g^b)^a = (g^a)^b = A^b \]
- Of course, in this case, Bob cannot obtain \(K_0\), since
\[K_0 = B^a = (g^b \cdot A)^a = g^{ba} \cdot A^a = A^b \cdot A^a\]
There is not way that Bob can compute \(A^a\), but that's actually great for
the protocol. Bob is supposed not to know this value!
Overall, the protocol proceeds as follows:
Note:
- If \(\sigma = 0\), we have \(B = g^b \), and \(K_0\) is the key as in the
DH key exchange protocol.
- If \(\sigma = 1\), we have \(B = g^b \cdot A\). As we have seen right
above, we have \(K_1 = A^b\)
Review Questions
TRUE/FALSE
- Bob creates a fresh random garbled circuit and evaluates it for privacy.
- For each bit of Bob's input, Alice must send a pair of wire keys so that
Bob can evaluate the garbled circuit correctly.
- For each output wire of the circuit, two wire keys must be sent.
Inverse
- \(5^{-1} \bmod 13 = \)?
Oblivious Transfer
Use the following encryption scheme: \(Enc_k(m) = k \cdot m \bmod p\).
For example, with p = 23, we have \(Enc_4(7) = 5\).
Fill out the numbers.
Note: Fill the space with actual numbers. If you use a symbol, you will get 0 point.
p = 23, g = 2
Alice: [input m0 = 7, m1 = 8] Bob: [input sel_bit = 1]
(random) a = 3 (random) b = 2
____
-------------------------->
____
<-------------------------
K0 = ( )^( ) mod 23 = ____
_____ _____
K1 = ( )^( ) mod 23 = ____ -------------------------> K_ = ( )^( ) mod 23 = ____
m_ = ____
Refer to the following table for inverse values:
1^(-1) mod 23 = 1
2^(-1) mod 23 = 12
3^(-1) mod 23 = 8
4^(-1) mod 23 = 6
5^(-1) mod 23 = 14
6^(-1) mod 23 = 4
7^(-1) mod 23 = 10
8^(-1) mod 23 = 3
9^(-1) mod 23 = 18
10^(-1) mod 23 = 7
11^(-1) mod 23 = 21
|
12^(-1) mod 23 = 2
13^(-1) mod 23 = 16
14^(-1) mod 23 = 5
15^(-1) mod 23 = 20
16^(-1) mod 23 = 13
17^(-1) mod 23 = 19
18^(-1) mod 23 = 9
19^(-1) mod 23 = 17
20^(-1) mod 23 = 15
21^(-1) mod 23 = 11
22^(-1) mod 23 = 22
|
Answer: ans.txt
Activity
Download the starter code: ot_py.txt.
- Fill out the code so that the code works as follows:
- In python,
(1/A), which is \(A^{-1} \bmod{p}\), should be coded as
pow(A, -1, p).
- You must use
pow function for exponentiations, Otherwise,
your code will be extremely slow.
>>> from ot import *
>>> g = 2
>>> p = prime()
## Alice: sample key pair (as two input messages), send A
>>> keys = sample_wirekey_pair()
>>> (a, A) = sendA(g, p)
## Bob: Suppose input selection bit is 1. send B.
>>> sel_bit = 1
>>> (b, B) = sendB(g, p, A, sel_bit)
## Alice: Send two ciphertext c0 and c1 encrypting m0 and m1 respectively
>>> (c0, c1) = send_enc_messages(g, p, a, A, B, keys[0], keys[1])
## Bob: Decrypt two ciphertext. Since sel_bit is 1, the second decryption works.
>>> ot_output(g, p, A, b, c0, c1)
(b'm\x82\xac^\xd4Em\x90\t\xc82\xfe\x9a<\x1dh\xf7T\x08j\x04&\x83{l\xa9<}\x91\xec\x04\x8d',
b'wire key: \x9fX\x84\x1a9\xb5\x9f\x9dH;\x88m\x9e\x06\xa5s\x01]\x0f\xb0\xcb')
## The decrytion indeed matches the second wirekey
>>> keys
[b'wire key: \xca~\x16\x11\x00$\x9f\x0c\xac\xc2\xe5\xa5\x07\xeb]-\x9ce\xff\xd3\x96',
b'wire key: \x9fX\x84\x1a9\xb5\x9f\x9dH;\x88m\x9e\x06\xa5s\x01]\x0f\xb0\xcb']