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

New Communication-Efficient Oblivious Transfer Protocols Based on Pairings.

Helger Lipmaa

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

Abstract. We construct two simple families of two-message (n, 1)-oblivious transfer protocols based on degree-t homomorphic cryptosystems with the communication of respectively 1 + ⌈n/t ⌉ and 3 + ⌈n/(t + 1) ⌉ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case t = 2 can be based on the Boneh-Goh-Nissim cryptosystem. We show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communicationefficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols. Keywords. Computationally-private information retrieval, conditional disclosure of secrets, homomorphic encryption, oblivious transfer. 1

Related papers

An Oblivious Transfer Protocol with Log-Squared Communication.

Helger Lipmaa

Abstract. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for ℓ-bit strings with low-degree polylogarithmic receivercomputation, linear sender-computation and communication Θ(k · log 2 n + ℓ · log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1out-of-n oblivious-transfer protocol for ℓ-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. Keywords. Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer. 1

•Jan 1, 2004•4 citations

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

Optimal secure data retrieval using an oblivious transfer scheme

Behzad Malek, Ali Miri

Oblivious transfer is such a strong cryptographic tool that it is directly used both in private data retrieval techniques and secure, multi-party computation paradigms. We propose an optimal oblivious transfer, where the communication complexity is logarithmic in size of the database with minimum computation overhead - the computational complexity in any oblivious transfer protocol is at least linear in the size of the database. Our communication-efficient oblivious transfer protocol is a non-interactive, single-database scheme that is generally based on homomorphic encryption functions.

IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)•Oct 4, 2006•2 citations

Homomorphic Encryption based k-out-of-n Oblivious Transfer Protocols

Mummoorthy Murugesan, Wei Jiang, Erhan Nergiz +1 more

Oblivious Transfer (OT) is an important cryptographic tool, which has found its usage in many crypto protocols, such as Secure Multiparty Computations [9], Certified E-mail [2] and Simultaneous Contract Signing [20].In this paper, we propose three k-out-of-n OT (OT n k ) protocols based on additive homomorphic encryption.Two of these protocols prohibit malicious behaviors from both sender and receiver.We also achieve efficient communication complexity bounded by O(l • n) in bits, where l is the size of the encryption key.The computational complexity is same or better than the most efficient existing protocols.Due to the semantic security property, the sender cannot get receiver's selection.When the receiver tries to retrieve more than k values, the receiver is caught cheating with 1 -1/m probability (Protocol II) or the receiver is unable to get any value at all (Protocol III).We introduce a novel technique based on the solvability of linear equations, which could find its way into other applications.We also provide an experimental analysis to compare the efficiency of the protocols.

•Jan 1, 2009•2 citations

A New t-out-n Oblivious Transfer with Low Bandwidth

Hui‐Feng Huang, Chin‐Chen Chang

Abstract. The most efficient previously proposed oblivious transfer schemes require t calls of 1-out-n oblivious transfer (OT) to construct the t-out-n OT. Its computational requirements and bandwidth consumption are quite demanding. Therefore, to guarantee the quality of growing popular communication service, an efficient t-out-n OT scheme with low bandwidth is urgently desired. Based on elliptic curve cryptosystems, we propose a new t-out-n OT scheme in this paper. Compared with existing OT schemes based on modular exponentiations, our scheme can reduce many computation and communication loads for both the sender and the receiver. Owing to its smaller bandwidth and faster computation speed, our scheme is very suitable for mobile clients and smart-card users. Moreover, our scheme provides a simple algorithm and fewer parameter requirements. Keywords: Two-lock cryptosystem, private information retrieval, elliptic curve 1.

•Jan 1, 2007•3 citations

A New Design of Oblivious Transfer for Private Information Retrieval

Hui‐Feng Huang

In a t-out-n oblivious transfer, the receiver can only receive t messages out of n messages sent by the sender; and the sender has no idea about which ones have been received. Majority of the existing of previous efficient oblivious transfer schemes require t calls of 1-out-n oblivious transfer to construct the t-out-n oblivious transfer. Its computational requirements and bandwidth consumption are quite demanding. Therefore, to guarantee the quality of electronic commercial service, an efficient t-out-n oblivious transfer scheme is urgently desired. Based on the RSA, we propose a new t-out-n oblivious transfer protocol for private information retrieval in this paper. In our method, only several modular multiplications and t hash functions are performed by a user (receiver) to obtain t messages. It is very suitable for the limited computation capacities of receivers such as smart cards or mobile units. Key words: Private information retrieval, security, RSA

•Jan 1, 2008•0 citations
Abstract. We construct two simple families of two-message (n, 1)-oblivious transfer protocols based on degree-t homomorphic cryptosystems with the communication of respectively 1 + ⌈n/t ⌉ and 3 + ⌈n/(t + 1) ⌉ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case t = 2 can be based on the Boneh-Goh-Nissim cryptosystem. We show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communicationefficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols. Keywords. Computationally-private information retrieval, conditional disclosure of secrets, homomorphic encryption, oblivious transfer. 1
Abstract. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for ℓ-bit strings with low-degree polylogarithmic receivercomputation, linear sender-computation and communication Θ(k · log 2 n + ℓ · log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1out-of-n oblivious-transfer protocol for ℓ-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. Keywords. Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer. 1
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 such a strong cryptographic tool that it is directly used both in private data retrieval techniques and secure, multi-party computation paradigms. We propose an optimal oblivious transfer, where the communication complexity is logarithmic in size of the database with minimum computation overhead - the computational complexity in any oblivious transfer protocol is at least linear in the size of the database. Our communication-efficient oblivious transfer protocol is a non-interactive, single-database scheme that is generally based on homomorphic encryption functions.
Oblivious Transfer (OT) is an important cryptographic tool, which has found its usage in many crypto protocols, such as Secure Multiparty Computations [9], Certified E-mail [2] and Simultaneous Contract Signing [20].In this paper, we propose three k-out-of-n OT (OT n k ) protocols based on additive homomorphic encryption.Two of these protocols prohibit malicious behaviors from both sender and receiver.We also achieve efficient communication complexity bounded by O(l • n) in bits, where l is the size of the encryption key.The computational complexity is same or better than the most efficient existing protocols.Due to the semantic security property, the sender cannot get receiver's selection.When the receiver tries to retrieve more than k values, the receiver is caught cheating with 1 -1/m probability (Protocol II) or the receiver is unable to get any value at all (Protocol III).We introduce a novel technique based on the solvability of linear equations, which could find its way into other applications.We also provide an experimental analysis to compare the efficiency of the protocols.
Abstract. The most efficient previously proposed oblivious transfer schemes require t calls of 1-out-n oblivious transfer (OT) to construct the t-out-n OT. Its computational requirements and bandwidth consumption are quite demanding. Therefore, to guarantee the quality of growing popular communication service, an efficient t-out-n OT scheme with low bandwidth is urgently desired. Based on elliptic curve cryptosystems, we propose a new t-out-n OT scheme in this paper. Compared with existing OT schemes based on modular exponentiations, our scheme can reduce many computation and communication loads for both the sender and the receiver. Owing to its smaller bandwidth and faster computation speed, our scheme is very suitable for mobile clients and smart-card users. Moreover, our scheme provides a simple algorithm and fewer parameter requirements. Keywords: Two-lock cryptosystem, private information retrieval, elliptic curve 1.
In a t-out-n oblivious transfer, the receiver can only receive t messages out of n messages sent by the sender; and the sender has no idea about which ones have been received. Majority of the existing of previous efficient oblivious transfer schemes require t calls of 1-out-n oblivious transfer to construct the t-out-n oblivious transfer. Its computational requirements and bandwidth consumption are quite demanding. Therefore, to guarantee the quality of electronic commercial service, an efficient t-out-n oblivious transfer scheme is urgently desired. Based on the RSA, we propose a new t-out-n oblivious transfer protocol for private information retrieval in this paper. In our method, only several modular multiplications and t hash functions are performed by a user (receiver) to obtain t messages. It is very suitable for the limited computation capacities of receivers such as smart cards or mobile units. Key words: Private information retrieval, security, RSA