Questions: Oblivious Transfer

Question 1

Why can't oblivious transfer be achieved using only symmetric cryptography (without any public-key assumptions)?

Model answer: OT requires an inherent asymmetry: the receiver must learn one message while being provably unable to learn the other, AND the sender must be unable to learn which message was chosen. With symmetric cryptography alone, any information the sender transmits is either decryptable by the receiver (who holds the symmetric key) or not — there is no mechanism for the sender to 'not know' which key the receiver has without public-key techniques. Impagliazzo and Rudich showed that OT cannot be built from one-way functions in a black-box way, suggesting it genuinely requires public-key-type assumptions.

This separation result is fundamental: OT (and therefore general MPC without honest majority) requires strictly stronger assumptions than private-key cryptography. One-way functions suffice for encryption, MACs, signatures, and ZK proofs, but OT needs something like CDH, RSA, or LWE. This is the theoretical boundary between what symmetric and public-key cryptography can achieve.

Question 2

OT is 'complete' for secure computation. What does completeness mean in this context?

• A. OT can compute any function by itself without additional communication
• B. Any efficiently computable function can be securely evaluated by a protocol that uses only OT as its cryptographic building block (plus local computation). This was proven by Kilian (1988): OT plus garbled circuits gives general two-party secure computation, and extensions handle the multi-party case
• C. OT is the most efficient building block for any computation
• D. OT can replace all other cryptographic primitives, including encryption and signatures

Answer: (B)

Completeness means OT is sufficient for all of secure computation, not that it replaces all crypto primitives. Kilian's result shows: given access to OT, the parties can securely compute any function. The garbler sends the garbled circuit; the evaluator obtains their input labels via OT (one OT per input bit). This requires no additional cryptographic assumptions beyond what OT provides. Other primitives (encryption, signatures) serve different purposes and are not subsumed.

Question 3

OT extension allows computing millions of OTs from a small number (say 128) of 'base' OTs using only hash function evaluations. Why is this important for practical MPC?

• A. Hash functions are more secure than public-key operations
• B. Base OTs require expensive public-key operations (one per OT). For a garbled circuit with millions of input bits, millions of public-key OTs would be prohibitively slow. OT extension (Ishai-Kilian-Nissim-Orlandi) bootstraps 128 base OTs into any number of additional OTs using only symmetric-key operations (hashing), reducing the amortized cost per OT to a few hash evaluations — orders of magnitude faster
• C. OT extension eliminates the need for computational assumptions
• D. Hash functions provide information-theoretic security for OT

Answer: (B)

OT extension is one of the most important practical optimizations in MPC. The base OTs (128 or 256, matching the security parameter) use expensive public-key crypto, but this cost is amortized over millions of extended OTs. The extension protocol uses a matrix transposition trick: the receiver sends a matrix of bits, and the sender uses the base OT keys to 'switch' rows, generating correlated random OT pairs. The cost drops from one RSA/ECC operation per OT to one hash evaluation per OT.

Question 4

In a 1-out-of-2 OT, the sender is guaranteed to learn nothing about the receiver's choice bit b, even if the sender is malicious and deviates from the protocol.

• T. True
• F. False

Answer: True

This is the receiver's privacy guarantee and must hold against a malicious sender. In Naor-Pinkas OT (based on DDH), the receiver sends a specially constructed message that information-theoretically hides b — the sender cannot determine which of the two messages the receiver will be able to decrypt, regardless of the sender's computational power. The sender's privacy (receiver learns only m_b) holds computationally against a malicious receiver.

Question 5

Random OT (where the sender does not choose the messages — both parties receive correlated random values) is equivalent to chosen-message OT. Why is random OT useful as a building block?

Model answer: Random OT can be converted to chosen-message OT: after a random OT produces random values (r0, r1) for the sender and r_b for the receiver, the sender sends (m0 XOR r0, m1 XOR r1). The receiver computes m_b = (m_b XOR r_b) XOR r_b. Random OT is useful because it can be precomputed in an offline phase (before the parties know their actual inputs), and then converted to chosen-message OT cheaply in the online phase. This offline/online split is a key optimization in practical MPC protocols.

The preprocessing model separates expensive cryptographic operations (done offline when inputs are unknown) from lightweight operations (done online with actual inputs). Random OTs are input-independent and can be stockpiled. When the real computation begins, converting them to chosen-message OTs requires only XOR operations — essentially free. This amortization strategy is fundamental to achieving practical MPC performance.