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.

Problem 81

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.