Improved OT Extension for Transferring Short Secrets

We propose an optimization and generalization of OT extension of Ishai et al. of Crypto 2003. For computational security parameter

k

, our OT extension for short secrets offers

O

(log

k

) factor performance improvement in communication and computation, compared to prior work. In concrete terms, for today’s security parameters, this means approx. factor 2-3 improvement.

This results in corresponding improvements in applications relying on such OT. In particular, for two-party semi-honest SFE, this results in

O

(log

k

) factor improvement in communication over state of the art Yao Garbled Circuit, and has the same asymptotic complexity as the recent multi-round construction of Kolesnikov and Kumaresan of SCN 2012. For multi-party semi-honest SFE, where their construction is inapplicable, our construction implies

O

(log

k

) factor communication and computation improvement over best previous constructions. As with our OT extension, for today’s security parameters, this means approximately factor 2 improvement in semi-honest multi-party SFE.

Our building block of independent interest is a novel IKNP-based framework for 1-out-of-

n

OT extension, which offers

O

(log

n

) factor performance improvement over previous work (for

n

 ≤ 

k

), and concrete factor improvement of up to 5 for today’s security parameters (

n

=

k

=128).

Our protocol is the first practical OT with communication/ computation cost sublinear in the security parameter (prior sublinear constructions Ishai et al. [15,16] are not efficient in concrete terms).