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

International Conference on Availability, Reliability and Security (ARES)

Generalized Robust Combiners for Oblivious Transfer

Ganugula Umadevi, Sarat C. Addepalli, Kannan Srinathan

Published Jan 1, 2009• 0 citations
Publisher

Abstract

A robust combiner for a cryptographic primitive gives a secure implementation of the primitive when at least some of the input candidates are secure. Such constructions provide robustness against insecure implementations and incorrect assumptions underlying the candidate schemes. Robust combiners are useful tools for ensuring better security in applied cryptography. Combiners from the perspective of threshold schemes have been previously studied. However, such threshold schemes typically fail to capture all possible scenarios. In this paper, we characterize the possibility of a transparent black-box combiner for oblivious transfer (OT), given an access structure over the candidate implementations. We also propose a circuit-based framework for the construction of such combiners, and hence reduce the problem of optimal OT combiners to circuit optimization.

DOI
10.1109/ares.2009.160

Related papers

Robust Combiners for Cryptographic Primitives

Christian G. Sommer, Bartosz Przydatek

In cryptography, we do not know which computational assumptions are the most secure to rely on. Robust combiners attempt to solve this problem. Given several implementations of a certain primitive, e.g., of a commitment scheme, a combiner merges them into a new implementation that is secure if a minimum number of the input implementations are secure. A (k;n)-robust combiner merges n implementations, where k of them are required to remain secure. In this thesis, we investigate combiners for various primitives. We show which combiners for commitment schemes are possible and which combiners do not exist. We show that a certain combiner construction is impossible if only half of the input implementations are secure (technically speaking, we prove that transparent black-box (1; 2)-robust combiners for commitment schemes do not exist). Furthermore, we give explicit constructions for combiners where the majority of the input implementations are assumed to be secure. We make further investigations about combiners for interactive proof systems. However, this scenario is far more complicated and therefore, the statements made are somewhat crude. For oblivious transfer, a yet unpublished paper of Meier et al. proposes more tolerant constructions using a “swap” operation. We show that such an operation is necessary for certain types of combiners. Zusammenfassung Combiners werden in der Kryptographie verwendet, um sich gegen ungewisse berechenmassige Annahmen abzusichern. Gegeben sind Implementationen einer Primitive, zum Beispiel Bit Commitment. Ein Combiner verknupft diese Implementationen so, dass die Kombination sicher ist, wenn mindestens eine gewisse Anzahl der gegebenen Implementationen sicher ist. In dieser Arbeit befassen wir uns mit Combinern fur verschiedene Primitiven. Wir untersuchen, welche Combiners fur Commitment Schemes existieren und welche unmoglich sind. Wir zeigen, dass transparent black-box Combiner Konstruktionen nur moglich sind, falls die Mehrheit der gegebenen Implementationen sicher ist und konstruieren einen solchen Combiner. Weiter haben wir uns mit Combinern fur interaktive Beweissysteme befasst. Diese Ausgangslage ist viel komplizierter und die gemachten Aussagen sind eher einfacher Natur. Fur Oblivious Transfer werden in einer noch unveroffentlichten Arbeit von Meier et al. tolerantere Konstruktionen vorgeschlagen, welche nur mit einer “swap”-Operation funktionieren. Wir zeigen, dass eine Operation dieser Art notwendig ist.

•Jan 1, 2006•0 citations

Resource-Efficient OT Combiners with Active Security

Ignacio Cascudo, Ivan Damgård, Oriol Farràs +1 more

An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.

Lecture notes in computer science•Jan 1, 2017•6 citations

Reducing Complexity Assumptions for Oblivious Transfer.

Kai-Yuen Cheong, Takeshi Koshiba

Reducing the minimum assumptions needed to construct various cryptographic primitives is an important andinteresting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.

•Jan 1, 2008•0 citations

Black-Box Constructions of Protocols for Secure Computation

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz +2 more

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.

SIAM Journal on Computing•Jan 1, 2011•45 citations

Arithmetic Cryptography

Benny Applebaum, Jonathan Avron, Chris Brzuska

We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F . In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.

Journal of the ACM•Apr 15, 2017•10 citations

One-Out-of-q OT Combiners

Oriol Farràs, Jordi Ribes-González

In 1-out-of-$q$Oblivious Transfer (OT) protocols, a sender Alice is able to send one of$q\ge 2$messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take$n$instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the$n$original OT instances are secure. We present new 1-out-of-$q$OT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an$\mathbb {F}_{q}$-linear secret sharing scheme on a set of$n$participants and adversary structure$\mathcal {A}$, we can construct an$n$-server, 1-out-of-$q$OT combiner that is secure against an adversary corrupting either Alice and a set of servers in$\mathcal {A}$, or Bob and a set of servers$B$with$\bar {B}\notin \mathcal {A}$. If the normalized total share size of the scheme is$\ell $, then the resulting OT combiner requires$\ell $calls to OT protocols, and the total amount of bits exchanged during the protocol is$(q^{2}+q+1)\ell \log q$. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power$q\geq n$, there are$n$-server, 1-out-of-$q$OT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchanging$O(qn\log q)$bits in total.

IEEE Transactions on Information Theory•Dec 7, 2023•2 citations
A robust combiner for a cryptographic primitive gives a secure implementation of the primitive when at least some of the input candidates are secure. Such constructions provide robustness against insecure implementations and incorrect assumptions underlying the candidate schemes. Robust combiners are useful tools for ensuring better security in applied cryptography. Combiners from the perspective of threshold schemes have been previously studied. However, such threshold schemes typically fail to capture all possible scenarios. In this paper, we characterize the possibility of a transparent black-box combiner for oblivious transfer (OT), given an access structure over the candidate implementations. We also propose a circuit-based framework for the construction of such combiners, and hence reduce the problem of optimal OT combiners to circuit optimization.
In cryptography, we do not know which computational assumptions are the most secure to rely on. Robust combiners attempt to solve this problem. Given several implementations of a certain primitive, e.g., of a commitment scheme, a combiner merges them into a new implementation that is secure if a minimum number of the input implementations are secure. A (k;n)-robust combiner merges n implementations, where k of them are required to remain secure. In this thesis, we investigate combiners for various primitives. We show which combiners for commitment schemes are possible and which combiners do not exist. We show that a certain combiner construction is impossible if only half of the input implementations are secure (technically speaking, we prove that transparent black-box (1; 2)-robust combiners for commitment schemes do not exist). Furthermore, we give explicit constructions for combiners where the majority of the input implementations are assumed to be secure. We make further investigations about combiners for interactive proof systems. However, this scenario is far more complicated and therefore, the statements made are somewhat crude. For oblivious transfer, a yet unpublished paper of Meier et al. proposes more tolerant constructions using a “swap” operation. We show that such an operation is necessary for certain types of combiners. Zusammenfassung Combiners werden in der Kryptographie verwendet, um sich gegen ungewisse berechenmassige Annahmen abzusichern. Gegeben sind Implementationen einer Primitive, zum Beispiel Bit Commitment. Ein Combiner verknupft diese Implementationen so, dass die Kombination sicher ist, wenn mindestens eine gewisse Anzahl der gegebenen Implementationen sicher ist. In dieser Arbeit befassen wir uns mit Combinern fur verschiedene Primitiven. Wir untersuchen, welche Combiners fur Commitment Schemes existieren und welche unmoglich sind. Wir zeigen, dass transparent black-box Combiner Konstruktionen nur moglich sind, falls die Mehrheit der gegebenen Implementationen sicher ist und konstruieren einen solchen Combiner. Weiter haben wir uns mit Combinern fur interaktive Beweissysteme befasst. Diese Ausgangslage ist viel komplizierter und die gemachten Aussagen sind eher einfacher Natur. Fur Oblivious Transfer werden in einer noch unveroffentlichten Arbeit von Meier et al. tolerantere Konstruktionen vorgeschlagen, welche nur mit einer “swap”-Operation funktionieren. Wir zeigen, dass eine Operation dieser Art notwendig ist.
An OT-combiner takes n candidate implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. We see an OT-combiner as a 2-party protocol that can make several black-box calls to each of the n OT candidates, and we want to protect against an adversary that can corrupt one of the parties and a certain number of the OT candidates, obtaining their inputs and (in the active case) full control of their outputs. In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on minimizing the number of calls to the candidate OTs. First, we construct a single-use (one call per OT candidate) OT-combiner which is perfectly secure against active adversaries corrupting one party and a constant fraction of the OT candidates. This extends a previous result by Ishai et al. (ISIT 2014) that proves the same fact for passive adversaries. Second, we consider a more general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions for the existence of an OT combiner with a given number of calls to the candidate OTs in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows in some cases to determine the optimal number of calls to the OT candidates which are needed to construct an OT combiner secure against a given adversary.
Reducing the minimum assumptions needed to construct various cryptographic primitives is an important andinteresting task in theoretical cryptography. Oblivious Transfer, one of the most basic cryptographic building blocks, is also studied under this scenario. Reducing the minimum assumptions for Oblivious Transfer seems not an easy task, as there are a few impossibility results under black-box reductions. Until recently, it is widely believed that Oblivious Transfer can be constructed with trapdoor permutations but not trapdoor functions in general. In this paper, we enhance previous results and show one Oblivious Transfer protocol based on a collection of trapdoor functions with some extra properties. We also provide reasons for adding the extra properties and argue that the assumptions in the protocol are nearly minimum.
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-black-box since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semihonest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which make only a black-box use of semihonest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make its actions appear to be honest, then it is guaranteed that it learned nothing more than its prescribed output. We then show how to construct defensible oblivious transfer from semihonest oblivious transfer, and malicious oblivious transfer from defensible oblivious transfer, all in a black-box way.
We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F . In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.
In 1-out-of-qqqOblivious Transfer (OT) protocols, a sender Alice is able to send one ofq≥2q\ge 2q≥2messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners takennninstances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of thennnoriginal OT instances are secure. We present new 1-out-of-qqqOT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given anFq\mathbb {F}_{q}Fq​-linear secret sharing scheme on a set ofnnnparticipants and adversary structureA\mathcal {A}A, we can construct annnn-server, 1-out-of-qqqOT combiner that is secure against an adversary corrupting either Alice and a set of servers inA\mathcal {A}A, or Bob and a set of serversBBBwithBˉ∉A\bar {B}\notin \mathcal {A}Bˉ∈/A. If the normalized total share size of the scheme is$\ell ,thentheresultingOTcombinerrequires, then the resulting OT combiner requires,thentheresultingOTcombinerrequires\ell callstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocoliscalls to OT protocols, and the total amount of bits exchanged during the protocol iscallstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocolis(q^{2}+q+1)\ell \log q.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepower. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepowerq\geq n,thereare, there are,therearen−server,1−out−of−-server, 1-out-of-−server,1−out−of−qOTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingOT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchangingOTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingO(qn\log q)$bits in total.