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

Threshold Fully Homomorphic Encryption and Secure Computation.

Steven Myers, Mona Sergi, Abhi A. Shelat

Cramer, Damgard, and Nielsen [CDN01] show how to construct an efficient secure multiparty computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim [NN01a] show how to construct secure multi-party protocols for a function f whose communication is proportional to the communication required to evaluate f without security, albeit at the cost of computation that might be exponential in the description of f . Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function f using communication that is independent of the circuit description of f and computation that is polynomial in | f |. This paper addresses the major drawback’s of Gentry’s approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim’s compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zeroknowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f .

•Jan 1, 2011•30 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

Secure multi-party computation made simple

MaurerUeli

Known secure multi-party computation protocols are quite complex, involving non-trivial mathematical structures and sub-protocols. The purpose of this paper is to present a very simple approach to ...

Discrete Applied Mathematics•Feb 1, 2006•5 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.

IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)•Aug 1, 2015•10 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.
Cramer, Damgard, and Nielsen [CDN01] show how to construct an efficient secure multiparty computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim [NN01a] show how to construct secure multi-party protocols for a function f whose communication is proportional to the communication required to evaluate f without security, albeit at the cost of computation that might be exponential in the description of f . Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function f using communication that is independent of the circuit description of f and computation that is polynomial in | f |. This paper addresses the major drawback’s of Gentry’s approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim’s compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zeroknowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f .
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.