A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions

Kaoru Kurosawa; Wataru Kishimoto; Takeshi Koshiba

doi:10.1109/TIT.2008.921704

A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions

Kaoru Kurosawa^*, Wataru Kishimoto, Takeshi Koshiba

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds.

Original language	English
Pages (from-to)	2566-2571
Number of pages	6
Journal	IEEE Transactions on Information Theory
Volume	54
Issue number	6
DOIs	https://doi.org/10.1109/TIT.2008.921704
Publication status	Published - 2008 Jun
Externally published	Yes

Keywords

Combinatorial approach
Lower bound
Oblivious transfer
Reduction

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2008.921704

Cite this

@article{ef06e966688a4a41b73690616e0a6e26,

title = "A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions",

abstract = "Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds.",

keywords = "Combinatorial approach, Lower bound, Oblivious transfer, Reduction",

author = "Kaoru Kurosawa and Wataru Kishimoto and Takeshi Koshiba",

year = "2008",

month = jun,

doi = "10.1109/TIT.2008.921704",

language = "English",

volume = "54",

pages = "2566--2571",

journal = "IRE Professional Group on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "6",

}

TY - JOUR

T1 - A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions

AU - Kurosawa, Kaoru

AU - Kishimoto, Wataru

AU - Koshiba, Takeshi

PY - 2008/6

Y1 - 2008/6

N2 - Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds.

AB - Consider the scenario where we are given an ideal functionality of oblivious transfer (OT), and we wish to construct a larger OT by invoking the above functionality as a black box. How many invocations of an ideal OT functionality are necessary? In tackling this problem, some lower bounds were derived using entropy previously. In this paper, we manage to achieve tighter lower bounds by employing a combinatorial approach. This new approach yields lower bounds which are two times larger than the existing bounds.

KW - Combinatorial approach

KW - Lower bound

KW - Oblivious transfer

KW - Reduction

UR - http://www.scopus.com/inward/record.url?scp=45249091424&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45249091424&partnerID=8YFLogxK

U2 - 10.1109/TIT.2008.921704

DO - 10.1109/TIT.2008.921704

M3 - Article

AN - SCOPUS:45249091424

SN - 0018-9448

VL - 54

SP - 2566

EP - 2571

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

IS - 6

ER -

A combinatorial approach to deriving lower bounds for perfectly secure oblivious transfer reductions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this