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

Multi-Party Indirect Indexing and Applications.

Matthew Franklin, Mark A. Gondree, Payman Mohassel

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest.

Related papers

Communication-efficient multiparty oblivious transfer and applications

Matthew Franklin, Mark A. Gondree

We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. We explore, in depth, some of these applications, including private distributed constraint satisfaction problems, private stable bipartite matching, and private longest common subsequence. In the case of the private bipartite stable matching (stable marriage) problem, we follow-up the work of Golle (Financial Crypto 2006) who motivates the application and introduces a novel framework for the solving the problem. We show that the communication complexity of Golle’s main protocol is substantially greater than what was claimed, in part due to surprising pathological behavior of Golle’s variant of the Gale-Shapley stable matching algorithm. We develop new secure protocols in Golle’s basic framework with greatly reduced communication complexity. In the case of the longest common subsequence problem, we design communication efficient two-party and multi-party protocols for several variants of this and related problems. Our protocols achieve the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol). As such, this result is interesting as a contribution to the theory of communication efficiency for secure two-party and multi-party applications. We benefit from the felicitous interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. We believe this technique will be useful for privately implementing a variety of “efficiently encodable” dynamic programming applications.

•Jan 1, 2009•0 citations

Fast two-party secure computation with minimal assumptions

Abhi A. Shelat, Chih-Hao Shen

Almost all existing protocols for secure two-party computation require a specific hardness assumption, such as DDH, discrete logarithm, or a random oracle, even after assuming oracle access to the oblivious transfer functionality for their correctness and/or efficiency. We propose and implement a Yao-based protocol that is secure against malicious adversaries and enjoys the following benefits:

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Jan 1, 2013•87 citations

Cut-and-Choose Bilateral Oblivious Transfer and Its Application

Chuan Zhao, Han Jiang, Xiaochao Wei +2 more

Oblivious transfer is a fundamental tool in cryptographic protocols, especially in secure two-party computation. In TCC 2011, Lindell and Pinkas proposed a variant called cut-and-choose oblivious transfer, which did a great job in solving the selective failure attack in secure two-party computation protocols based on cut-and-choose paradigm. In this paper, we present a new primitive called cut-and-choose bilateral oblivious transfer. As an extension to cut-and-choose oblivious transfer, in addition to overcoming the selective failure attack, this primitive also makes a contribution to reducing the round number of the protocols that invoke it. This is very important in the scenarios where interactions between parties are limited. Besides, the application of this primitive in the outer protocols enables us to present a more modular and clean high-level description of the protocol framework. Furthermore, we believe that the new primitive is of independent research interest itself and could be useful in many cut-and-choose scenarios. Based on homomorphic encryption, we construct an efficient instantiation of this primitive in malicious model, and present a formal rigorous proof of its security under ideal/real simulation paradigm.

•Aug 20, 2015•5 citations

Cut-and-Choose Bilateral Oblivious Transfer and Its Application

Chuan Zhao, Han Jiang, Xiaochao Wei +2 more

Oblivious transfer is a fundamental tool in cryptographic protocols, especially in secure two-party computation. In TCC 2011, Lindell and Pinkas proposed a variant called cut-and-choose oblivious transfer, which did a great job in solving the selective failure attack in secure two-party computation protocols based on cut-and-choose paradigm. In this paper, we present a new primitive called cut-and-choose bilateral oblivious transfer. As an extension to cut-and-choose oblivious transfer, in addition to overcoming the selective failure attack, this primitive also makes a contribution to reducing the round number of the protocols that invoke it. This is very important in the scenarios where interactions between parties are limited. Besides, the application of this primitive in the outer protocols enables us to present a more modular and clean high-level description of the protocol framework. Furthermore, we believe that the new primitive is of independent research interest itself and could be useful in many cut-and-choose scenarios. Based on homomorphic encryption, we construct an efficient instantiation of this primitive in malicious model, and present a formal rigorous proof of its security under ideal/real simulation paradigm.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Aug 1, 2015•10 citations

Two round multiparty computation via Multi-key fully homomorphic encryption with faster homomorphic evaluations.

Ningbo Li, Tanping Zhou, Xiaoyuan Yang +3 more

•Jan 1, 2018•2 citations

Secure and fair two-party computation

Mehmet Sabır Kiraz

Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.

•Jan 1, 2007•19 citations
We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest.
We develop a new multi-party generalization of Naor-Nissim indirect indexing, making it possible for many participants to simulate a RAM machine with only poly-logarithmic blow-up. Underlying our approach is a new multi-party variant of oblivious transfer which may be of independent interest. Our most efficient instantiation (built from length-flexible additively homomorphic public key encryption) improves the communication complexity of secure multi-party computation for a number of problems in the literature. We explore, in depth, some of these applications, including private distributed constraint satisfaction problems, private stable bipartite matching, and private longest common subsequence. In the case of the private bipartite stable matching (stable marriage) problem, we follow-up the work of Golle (Financial Crypto 2006) who motivates the application and introduces a novel framework for the solving the problem. We show that the communication complexity of Golle’s main protocol is substantially greater than what was claimed, in part due to surprising pathological behavior of Golle’s variant of the Gale-Shapley stable matching algorithm. We develop new secure protocols in Golle’s basic framework with greatly reduced communication complexity. In the case of the longest common subsequence problem, we design communication efficient two-party and multi-party protocols for several variants of this and related problems. Our protocols achieve the first improvement to the communication complexity for this application over generic results (such as Yao’s garbled circuit protocol). As such, this result is interesting as a contribution to the theory of communication efficiency for secure two-party and multi-party applications. We benefit from the felicitous interplay of an efficient block-retrieval PIR (Gentry-Ramzan, ICALP 2005) with the classic “four Russians” algorithmic design. We believe this technique will be useful for privately implementing a variety of “efficiently encodable” dynamic programming applications.
Oblivious transfer is a fundamental tool in cryptographic protocols, especially in secure two-party computation. In TCC 2011, Lindell and Pinkas proposed a variant called cut-and-choose oblivious transfer, which did a great job in solving the selective failure attack in secure two-party computation protocols based on cut-and-choose paradigm. In this paper, we present a new primitive called cut-and-choose bilateral oblivious transfer. As an extension to cut-and-choose oblivious transfer, in addition to overcoming the selective failure attack, this primitive also makes a contribution to reducing the round number of the protocols that invoke it. This is very important in the scenarios where interactions between parties are limited. Besides, the application of this primitive in the outer protocols enables us to present a more modular and clean high-level description of the protocol framework. Furthermore, we believe that the new primitive is of independent research interest itself and could be useful in many cut-and-choose scenarios. Based on homomorphic encryption, we construct an efficient instantiation of this primitive in malicious model, and present a formal rigorous proof of its security under ideal/real simulation paradigm.
Oblivious transfer is a fundamental tool in cryptographic protocols, especially in secure two-party computation. In TCC 2011, Lindell and Pinkas proposed a variant called cut-and-choose oblivious transfer, which did a great job in solving the selective failure attack in secure two-party computation protocols based on cut-and-choose paradigm. In this paper, we present a new primitive called cut-and-choose bilateral oblivious transfer. As an extension to cut-and-choose oblivious transfer, in addition to overcoming the selective failure attack, this primitive also makes a contribution to reducing the round number of the protocols that invoke it. This is very important in the scenarios where interactions between parties are limited. Besides, the application of this primitive in the outer protocols enables us to present a more modular and clean high-level description of the protocol framework. Furthermore, we believe that the new primitive is of independent research interest itself and could be useful in many cut-and-choose scenarios. Based on homomorphic encryption, we construct an efficient instantiation of this primitive in malicious model, and present a formal rigorous proof of its security under ideal/real simulation paradigm.
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.