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

Simpósio Brasileiro de Cibersegurança (SBSeg)

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

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

Published Oct 11, 2010• 2 citations
Publisher

Abstract

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.
DOI
10.5753/sbseg.2010.20584

Related papers

Oblivious Transfer Based on the McEliece Assumptions

Rafael Dowsley, Jeroen van de Graaf, Jörn Müller‐Quade +1 more

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.

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

Obtaining Efficient Fully Simulatable Oblivious Transfer from General Assumptions

Bernardo David, Anderson C. A. Nascimento, Rafael Tonicelli

We introduce a general construction of fully simulatable oblivious transfer based on lossy encryption. Furthermore, we extend the common definition of lossy encryption by introducing the notion of computationally lossy encryption. If the cryptosystem used is computationally lossy, our general construction yields oblivious transfer protocols with computational security for both parties. Otherwise, when regular statistically lossy cryptosystems are employed in this construction, it yields oblivious transfer protocols with statistical security for the sender. The construction introduced in this paper is realizable from rerandomizable, homomorphic and lossy cryptosystems in general. Thus, it yields specific constructions based on different assumptions, such as DDH, LWE and McEliece. Moreover, it proves the equivalence of fully simulatable oblivious transfer and lossy encryption.

Simpósio Brasileiro de Cibersegurança (SBSeg)•Nov 6, 2011•0 citations

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 general model for oblivious transfer

Hossein Ghodosi

Naor and Pinkas (1999a) pointed out that 'this is of interest, given the possibility of implementing Oblivious Transfer using physical means, e.g., via a noisy channel or quantum cryptography. However, some of these reductions are not particularly efficient. .. '. Using tamper-proof smart cards, we propose some radically different approaches to the Oblivious Transfer problem. Despite the simplicity of our model, we achieve unconditional security and privacy for both the sender and receiver. In contrast to all known oblivious transfer protocols, which require extensive computations, the proposed schemes are very computationally efficient.

•Jan 1, 2007•3 citations

Oblivious transfer with a memory-bounded receiver

Christian Cachin, Claude Crépeau, Julien Marcil

We propose a protocol for oblivious transfer that is unconditionally secure under the sole assumption that the memory size of the receiver is bounded. The model assumes that a random bit string slightly larger than the receiver's memory is broadcast (either by the sender or by a third party). In our construction, both parties need memory of size in /spl theta/(n/sup 2-2/spl alpha//) for some /spl alpha//spl beta/>0, whereas a malicious receiver can have up to /spl gamma/N bits of memory for any /spl gamma/<1. In the course of our analysis, we provide a direct study of an interactive hashing protocol closely related to that of M. Naor et al. (1998).

Annual Symposium on Foundations of Computer Science•Nov 27, 2002•110 citations

Unconditional secure cooperation on real-world networks : the case of oblivious transfer

Paolo Palmieri

Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.

•Jan 1, 2013•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 introduce a general construction of fully simulatable oblivious transfer based on lossy encryption. Furthermore, we extend the common definition of lossy encryption by introducing the notion of computationally lossy encryption. If the cryptosystem used is computationally lossy, our general construction yields oblivious transfer protocols with computational security for both parties. Otherwise, when regular statistically lossy cryptosystems are employed in this construction, it yields oblivious transfer protocols with statistical security for the sender. The construction introduced in this paper is realizable from rerandomizable, homomorphic and lossy cryptosystems in general. Thus, it yields specific constructions based on different assumptions, such as DDH, LWE and McEliece. Moreover, it proves the equivalence of fully simulatable oblivious transfer and lossy encryption.
Naor and Pinkas (1999a) pointed out that 'this is of interest, given the possibility of implementing Oblivious Transfer using physical means, e.g., via a noisy channel or quantum cryptography. However, some of these reductions are not particularly efficient. .. '. Using tamper-proof smart cards, we propose some radically different approaches to the Oblivious Transfer problem. Despite the simplicity of our model, we achieve unconditional security and privacy for both the sender and receiver. In contrast to all known oblivious transfer protocols, which require extensive computations, the proposed schemes are very computationally efficient.
We propose a protocol for oblivious transfer that is unconditionally secure under the sole assumption that the memory size of the receiver is bounded. The model assumes that a random bit string slightly larger than the receiver's memory is broadcast (either by the sender or by a third party). In our construction, both parties need memory of size in /spl theta/(n/sup 2-2/spl alpha//) for some /spl alpha//spl beta/>0, whereas a malicious receiver can have up to /spl gamma/N bits of memory for any /spl gamma/<1. In the course of our analysis, we provide a direct study of an interactive hashing protocol closely related to that of M. Naor et al. (1998).
Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multi-party computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.\n\nIn this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.