Kaoru Kurosawa, Wataru Kishimoto, Takeshi Koshiba
IEEE TRANSACTIONS ON INFORMATION THEORY 54(6) 2566-2571 2008年6月 査読有り
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.