This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

# 1 out of n OT

Due: April 12
Points: 2

In class we saw a protocol to perform 1-2 Oblivious Transfer, with the following properties: Alice has two messages $$m_0$$ and $$m_1$$, Bob has a bit $$b \in \{0,1\}$$, and after the protocol Bob receives $$m_b$$ only. Alice doesn't know which message Bob received, and Bob doesn't know anything about the other message he didn't receive.

Modify this protocol so that Alice starts instead with $$n$$ messages instead of just 2, and Bob selects one out of the $$n$$ messages.

Then do some basic analysis of your protocol, by modifying the analysis below according to your modified protocol.

In standard 1-2 OT, Alice and Bob each do the following work:

Alice Bob
Create 2 random nonces Create 1 random nonce
Generate public/private key
Perform 2 decryptions Perform 1 encryption
Perform 4 XORs Perform 2 XORs
Send 5 values to Bob. Send 1 value to Alice

This is $$O(1)$$ work and $$O(1)$$ communication in total.