Paper 1996/010
Oblivious Transfers and Intersecting Codes
Gilles Brassard, Claude Crepeau, and Miklos Santha
Abstract
Assume A owns t secret k-bit strings. She is willing to disclose one of them to B, at his choosing, provided he does not learn anything about the other strings. Conversely, B does not want A to learn which secret he chose to learn. A protocol for the above task is said to implement One-out-of-t String Oblivious Transfer. An apparently simpler task corresponds to the case k=1 and t=2 of two one-bit secrets: this is known as One-out-of-two Bit OT. We address the question of implementing the former assuming the existence of the later. In particular, we prove that the general protocol can be implemented from O(tk) calls to One-out-of-two Bit OT. This is optimal up to a small multiplicative constant. Our solution is based on the notion of self-intersecting codes. Of independent interest, we give several efficient new constructions for such codes. Another contribution of this paper is a set of information-theoretic definitions for correctness and privacy of unconditionally-secure oblivious transfer.
Metadata
- Available format(s)
- PS
- Publication info
- Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Appeared in IEEE Transactions on Information Theory, Nov. 1996.
- Keywords
- Oblivious TransferIntersecting CodesProtocolsInformation Theory.
- Contact author(s)
- crepeau @ iro umontreal ca
- History
- 1996-07-26: received
- Short URL
- https://ia.cr/1996/010
- License
-
CC BY
BibTeX
@misc{cryptoeprint:1996/010,
author = {Gilles Brassard and Claude Crepeau and Miklos Santha},
title = {Oblivious Transfers and Intersecting Codes},
howpublished = {Cryptology {ePrint} Archive, Paper 1996/010},
year = {1996},
url = {https://eprint.iacr.org/1996/010}
}