Cryptology ePrint Archive: Report 2007/215

Extending Oblivious Transfers Efficiently - How to get Robustness Almost for Free

Jesper Buus Nielsen

Abstract: At Crypto 2003 Ishai et al. gave a protocol which given a small number of (possibly extremely inefficient) oblivious transfers implements an essentially unbounded number of oblivious transfers for an additional overhead, per oblivious transfer, of computing and sending only two hash values. This highly efficient protocol is however only passive secure. To get active security, except with probability $2^{-m}$, the protocol had to suffer an additional overhead of a factor $1+m$. We introduce a new approach to adding robustness. For practical security parameters this approach allows to add robustness while suffering only a small constant overhead over the passive secure protocol. As an example we can generate one million oblivious transfers with security $2^{-42}$ with an amortized cost of just $9$ hash values per oblivious transfer.

Category / Keywords: cryptographic protocols / oblivious transfer

Date: received 6 Jun 2007, last revised 11 Jul 2007

Contact author: buus at daimi au dk

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20070711:072311 (All versions of this report)

Short URL: ia.cr/2007/215