Choosing t-out-of-n Secrets by Oblivious Transfer

Publication Type:

Journal Article


Information & Security: An International Journal, Volume 18, p.67-84 (2006)


Communications, Generalized Chinese Remainder Theorem, Oblivious Transfer, Secrets Exchange.


Oblivious Transfer (OT) has been regarded as one of the most significant cryptography tools in recent decades. Since the mechanism of OT is widely used in many applications such as e-commerce, secret information exchange, and games, various OT schemes have been proposed to improve its functionality and efficiency. In 2001, Naor and Pinkas proposed a secure 1-out-of-n OT protocol, in which the sender has n messages and the chooser can get one of these n messages in each protocol run. What is more, the sender cannot find which message has been chosen by the chooser and the chooser knows only the correct message. In 2004, Wakaha and Ryota proposed a secure t-out-of-n OT protocol, which is an extension of the 1-out-of-n OT protocol proposed by Naor and Pinkas. Wakaha and Ryota’s t-out-of-n OT protocol allows the chooser to get t messages from the sender simultaneously in each protocol run. Besides, the sender cannot know what the chooser has chosen and the chooser can only know the exact t messages. However, getting deep understanding of Wakaha and Ryota’s protocol, it could be concluded that it still lacks efficiency such that it is hard to be applied in real-world applications. In this article, a secure and efficient t-out-of-n OT protocol based on the Generalized Chinese Remainder Theorem is proposed, in which the chooser can securely get t messages from the sender simultaneously in each protocol run. The efficiency of the proposed t-out-of-n OT protocol is higher than that of Wakaha and Ryota’s protocol in terms of practical application.