Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

When initiating an oblivious transfer, why would someone use a 1-2 oblivious transfer rather than going for an 1 out of n oblivious transfer? Perhaps a slight time overhead for the extra message encrypts, but with everything as fast as it is these days is that a concern?

share|improve this question
    
I'm not entirely sure, but I believe you wouldn't. 1-2 was the original idea, and is easy to explain/prove things about -- I believe 1-n or even k-n would be more likely to be used in practice. As with most things in mathematics, you look at the basic case and then generalize out. –  TJ Ellis Jul 12 '11 at 19:15
add comment

2 Answers 2

up vote 9 down vote accepted

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation).

The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic properties (number of rounds) or advanced security properties (full simulatability, plain model, UC-secure, etc), as opposed to being designed for real-life implementations. Although some proposals claim to be "efficient", that typically means they are efficient for the level of security they realize, and this level is usually much higher than something you would need for implementation.

A second reason for the interest in 1-2 OT is that OT is often used to securely evaluate boolean circuits. In this particular application, the circuit in constructed from binary gates have only two outputs: so 1-2 OT suffices. However if gates were replaced with more complicated truth tables or if transfers were batched together, 1-N OT might be of interest.

OT is a primitive that rarely finds its way into an implemented/deployed tool. The only application I know of is two-party computation tools based on Yao's garbled circuits, for which some implementations exist. One example is FairPlay and it its original paper, there is some interesting discussion on the overall efficiency of switching between different types of OT. It does however leave implementing 1-N OT for future work.

A MPC tool was also used to run a Danish beets auction however it did not employ OT. Many two-party or multi-party computations try to avoid using the general construction based on OT since it is very inefficient, the OTs themselves are usually the most expensive part, and typically the jump from two-party to multi-party computation means using a different blueprint based on secret sharing instead of OT.

share|improve this answer
add comment

the securty of 1-n OT is a function of the security of a 1-2 OT. So in analysis it is easy to use 1-2 OT for security proofs.

A 1-n OT is essentially a multiple run of a 1-2 OT. (somewhat like a byte is made of 8 bits)

So IMO the question is like asking why use bits when you can use bytes for communication. [it depends on the application]

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.