Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Oblivious Transfer Based on the McEliece Assumptions

Rafael Dowsley, Jeroen van de Graaf, Jörn Müller‐Quade, Anderson C. A. Nascimento

Published Jan 1, 2012• 7 citations
Publisher

Abstract

We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.

DOI
10.1587/transfun.e95.a.567

Related papers

Efficient computational oblivious transfer using interactive hashing

Kirill Morozov, George Savvides

We present two protocols for reducing oblivious transfer (OT) to the security of trapdoor permutations and to the hardness of some coding problems, respectively. The first protocol is the most efficient known to date, while the second one is a theoretical proof-of-concept. Our constructions leverage the power of Interactive Hashing (IH). The first protocol can be viewed as a simple modification of the well-known OT construction by Even, Goldreich and Lem-pel (1985), in which a receiver must send a random domain element to a sender through IH. Alternatively, our protocol can be viewed as a simple modification of the construction by Ostrovsky, Venkatesan and Yung (1993), in which the players substitute the one-way permutation with a trapdoor permutation. We use a similar approach to derive a second OT protocol based on coding assumptions related to security of the McEliece cryptosystem. In our second construction, the receiver inputs a public key into IH while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•Mar 22, 2011•1 citation

Oblivious Transfer Based on the McEliece Assumptions with Unconditional Security for the Sender

Bernardo David, Anderson C. A. Nascimento, Rodrigo Borges Nogueira

In this paper we propose the first code-based oblivious transfer protocol with perfect (unconditional) security for one of the parties. To obtain this result we show that the McEliece cryptosystem is rerandomizable, a property that might be of independent interest.

Simpósio Brasileiro de Cibersegurança (SBSeg)•Oct 11, 2010•2 citations

Computational Oblivious Transfer and Interactive Hashing

Kirill Morozov, George Savvides

We use interactive hashing to achieve the most efficient OT protocol to date based solely on the assumption that trapdoor permutations (TDP) exist. Our protocol can be seen as the following (simple) modification of either of the two famous OT constructions: 1) In the one by Even et al (1985), a receiver must send a random domain element to a sender through IH; 2) In the one by Ostrovsky et al (1993), the players should use TDP instead of one-way permutation. A similar approach is employed to achieve oblivious transfer based on the security of the McEliece cryptosystem. In this second protocol, the receiver inputs a public key into IH, while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.

•Jan 1, 2009•1 citation

Efficient Fully Simulatable Oblivious Transfer from the McEliece Assumptions

Bernardo David, Anderson C. A. Nascimento, Rafael T. de Sousa

We introduce an efficient fully simulatable construction of oblivious transfer based on the McEliece assumptions in the common reference string model. This is the first efficient fully simulatable oblivious protocol based on coding assumptions. Moreover, being based on the McEliece assumptions, the proposed protocol is a good candidate for the post-quantum scenario.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2012•4 citations

A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROM

Paulo S. L. M. Barreto, Bernardo David, Rafael Dowsley +2 more

Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct a round-optimal (2 rounds) universally composable (UC) protocol for oblivious transfer secure against active adaptive adversaries from any OW-CPA secure public-key encryption scheme with certain properties in the random oracle model (ROM). In terms of computation, our protocol only requires the generation of a public/secret-key pair, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In~terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, and three binary strings of roughly the same size as the message. Next, we show how to instantiate our construction under the low noise LPN, McEliece, QC-MDPC, LWE, and CDH assumptions. Our instantiations based on the low noise LPN, McEliece, and QC-MDPC assumptions are the first UC-secure OT protocols based on coding assumptions to achieve: 1) adaptive security, 2) optimal round complexity, 3) low communication and computational complexities. Previous results in this setting only achieved static security and used costly cut-and-choose techniques.Our instantiation based on CDH achieves adaptive security at the small cost of communicating only two more group elements as compared to the gap-DH based Simplest OT protocol of Chou and Orlandi (Latincrypt 15), which only achieves static security in the ROM.

arXiv:1710.08256•Oct 23, 2017•20 citations

reduction of 1 out of n oblivious transfers in random oracle model

Bao Li, Hongda Li, Guangwu Xu +1 more

We first present a protocol which reduces 1-out-of-n oblivious transfer OT m to 1out-of-n oblivious transfer OT k for n > 2 in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.

•Jan 1, 2003•0 citations
We implement one-out-of-two bit oblivious transfer (OT) based on the assumptions used in the McEliece cryptosystem: the hardness of decoding random binary linear codes, and the difficulty of distinguishing a permuted generating matrix of Goppa codes from a random matrix. To our knowledge this is the first OT reduction to these problems only. We present two different constructions for oblivious transfer, one based on cut-and-chose arguments and another one which is based on a novel generalization of Bennett-Rudich commitments which may be of independent interest. Finally, we also present a variant of our protocol which is based on the Niederreiter cryptosystem.
We present two protocols for reducing oblivious transfer (OT) to the security of trapdoor permutations and to the hardness of some coding problems, respectively. The first protocol is the most efficient known to date, while the second one is a theoretical proof-of-concept. Our constructions leverage the power of Interactive Hashing (IH). The first protocol can be viewed as a simple modification of the well-known OT construction by Even, Goldreich and Lem-pel (1985), in which a receiver must send a random domain element to a sender through IH. Alternatively, our protocol can be viewed as a simple modification of the construction by Ostrovsky, Venkatesan and Yung (1993), in which the players substitute the one-way permutation with a trapdoor permutation. We use a similar approach to derive a second OT protocol based on coding assumptions related to security of the McEliece cryptosystem. In our second construction, the receiver inputs a public key into IH while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.
We use interactive hashing to achieve the most efficient OT protocol to date based solely on the assumption that trapdoor permutations (TDP) exist. Our protocol can be seen as the following (simple) modification of either of the two famous OT constructions: 1) In the one by Even et al (1985), a receiver must send a random domain element to a sender through IH; 2) In the one by Ostrovsky et al (1993), the players should use TDP instead of one-way permutation. A similar approach is employed to achieve oblivious transfer based on the security of the McEliece cryptosystem. In this second protocol, the receiver inputs a public key into IH, while privately keeping the corresponding secret key. Two different versions of IH are used: the computationally secure one in the first protocol, and the information-theoretically secure one in the second.
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct a round-optimal (2 rounds) universally composable (UC) protocol for oblivious transfer secure against active adaptive adversaries from any OW-CPA secure public-key encryption scheme with certain properties in the random oracle model (ROM). In terms of computation, our protocol only requires the generation of a public/secret-key pair, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In~terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, and three binary strings of roughly the same size as the message. Next, we show how to instantiate our construction under the low noise LPN, McEliece, QC-MDPC, LWE, and CDH assumptions. Our instantiations based on the low noise LPN, McEliece, and QC-MDPC assumptions are the first UC-secure OT protocols based on coding assumptions to achieve: 1) adaptive security, 2) optimal round complexity, 3) low communication and computational complexities. Previous results in this setting only achieved static security and used costly cut-and-choose techniques.Our instantiation based on CDH achieves adaptive security at the small cost of communicating only two more group elements as compared to the gap-DH based Simplest OT protocol of Chou and Orlandi (Latincrypt 15), which only achieves static security in the ROM.