How to Derive Lower Bound on Oblivious Transfer Reduction

Kaoru Kurosawa; Wataru Kishimoto; Takeshi Koshiba

Paper 2007/065 Original: eprint.iacr.org/2007/065 ↗

How to Derive Lower Bound on Oblivious Transfer Reduction

Kaoru Kurosawa

Wataru Kishimoto

Takeshi Koshiba

Abstract

Suppose that we are given an ideal oblivious transfer protocol (OT). We wish to construct a larger OT by using the above OT as a blackbox. Then how many instances of the given ideal OT should be invoked ? For this problem, some lower bounds were derived using entropy. In this paper, we show more tight lower bounds by using combinatorial techniques. Roughly speaking, our lower bounds are two times larger than the previous bounds.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
History: 2007-03-13: last updated; 2007-02-28: published
Short URL: https://ia.cr/2007/065
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2007/065,
      author = {Kaoru Kurosawa and Wataru Kishimoto and Takeshi Koshiba},
      title = {How to Derive Lower Bound on Oblivious Transfer Reduction},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/065},
      year = {2007},
      url = {https://eprint.iacr.org/2007/065}
}