Efficient distributed 1 out of n oblivious transfer

Yael Gertner, Tal Malkin

Published Apr 1, 1997• 2 citations

Abstract

In this paper, we present a new application for , n 1 oblivious transfer, which i s a n i n teractive protocol between two parties Alice and Bob, where Alice has n secrets and Bob has a query i.A t the end of the protocol Bob has the ith secret and no other information about Alice's other secrets, while Alice does not get any information about i.This new application is the Secure Database Access problem.Motivated by this application, we propose an OT scheme which a c hieves low communication complexity and information theoretic security.We use a distributed model for , n 1 oblivious transfer, where Bob interacts with multiple \Alices".In this model, we base our scheme on any PIR scheme, which i s a s c heme where only the privacy of Bob is considered, and use it to construct an OT scheme, private for both parties, without paying too much i n communication complexity.This results in the rst sublinear information theoretic scheme for , n 1 OT.Further motivated by the application of , n 1 OT for polynomial n, w e raise the issue of repetition in , n 1 OT, where both security and eciency are important.We show that previous protocols for , n 1 oblivious transfer fail in this setting.

Related papers

Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters

Wen-Guey Tzeng

We propose efficient and secure (string) oblivious transfer (OT/sup 1//sub n/) schemes for any n/spl ges/2. We build our OT/sup 1//sub n/ scheme from fundamental cryptographic techniques directly. The receiver's choice is unconditionally secure and the secrecy of the unchosen secrets is based on the hardness of the decisional Diffie-Hellman problem. Some schemes achieve optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. We extend our OT/sup 1//sub n/ schemes to distributed oblivious transfer schemes. Our distributed OT/sup 1//sub n/ schemes take full advantage of the research results of secret sharing. For applications, we present a method of transforming any (single-database) PIR protocol into a symmetric PIR protocol by slightly increasing the communication cost only.

IEEE Transactions on ComputersFeb 1, 200493 citations

Oblivious transfer and polynomial evaluation

Moni Naor, Benny Pinkas B

We describe efficient constructions for two oblivious twoparty computation problems: l-out-of-N Oblivious Transfer &d 'Oblivious Poly&nial Evaluation.The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial re construction.A direct corollary of the l-out-of-N OT protccol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) prc-tow1 without increasing the number of databases.The new construction for l-out-of-N OT is highly efficient -it requires only log N executions of a l-out-of-2 OT protocol.We also present a construction for k-out-of-N OT which is more efficient than k repetitions of l-out-of-N OT.The efficiency of the new OT protocols makes them useful for a variety of applications.These include oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.

ACM Symposium on Theory of Computing (STOC)May 1, 1999635 citations

The Capacity of Oblivious Transfer with Replicated Databases and Binary Erasure Multiple Access Channel

Tianyou Pei, Wei Kang, Nan Liu

Both the oblivious transfer (OT) problem and the symmetric private information retrieval (SPIR) problem studies the scenario where a client retrieves information privately and securely from databases, i.e., the privacy of the client is protected from the databases, and the undesired information is protected from the client. The OT problem studies the case of one database plus additional noisy resources between the database and the client. The SPIR problem studies the case of multiple replicated and non-colluding databases. In this paper, we combine the two models and propose a new problem of oblivious transfer (OT) with two replicated databases and a binary erasure multiple access channel connecting the databases and the client. We first provide an upper bound on the OT capacity. We then propose a protocol which achieves the upper bound. Therefore, we obtain the capacity of OT for this model. In our achievability and converse proofs, we utilized the techniques from both traditional OT and PIR. Compared to schemes that utilizes only techniques from OT, we see a 100% increase in the achieved OT rate.

IEEE International Symposium on Information Theory (ISIT)Jun 25, 20232 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, 20062 citations

A Computationally Secure Quantum Oblivious Transfer Scheme

Xin Lü, Zhi Ma, Dengguo Feng

Oblivious transfer is an important primitive in modern cryptography and is widely utilized in designing more complex protocols. In a one-out-of-two oblivious transfer, a party Alice has two messages x0, x1send to another party Bob in such a way that he can decide to obtain one of them at his choice but not both. In the literature (A. Kawachi et al., EUROCRYPT 2005, 268-284), the quantum states ppi+and ppi-are used as public keys to construct an encryption algorithm. In the paper, we further demonstrate that, for pi ne thetas, the quantum states ppiplusmnand pthetasplusmncan't been distinguished by quantum computers. Using this result, we devise a one-out-of-two oblivious transfer scheme, in which any cheating of the entities are detected at the end of the protocol. Correctness and privacy of this protocol are analyzed and results show that the proposed scheme is computationally secured

International Conference on Advanced Communication TechnologyJan 1, 20062 citations

Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and Non-Adaptive Queries.

Cheng‐Kang Chu, Wen-Guey Tzeng

Abstract: Oblivious transfer is an important cryptographic protocol in various security applications. For example, in on-line transactions, a k-out-of-n oblivious transfer scheme allows a buyer to privately choose k out of n digital goods from a merchant without learning information about other n−k goods. In this paper, we propose several efficient two-round k-out-of-n oblivious transfer schemes, in which the receiver R sends O(k) messages to the sender S, andS sends O(n) messages back to R. The schemes provide unconditional security for either sender or receiver. The computational security for the other side is based on the Decisional Diffie-Hellman (DDH) or Chosen-Target Computational Diffie-Hellman (CT-CDH) problems. Our schemes have the nice property of universal parameters, that is, each pair of R and S need not hold any secret before performing the protocol. The system parameters can be used by all senders and receivers without any trapdoor specification. In some cases, our OT k n schemes are the most efficient ones in terms of the communication cost, either in rounds or the number of messages. Moreover, one of our schemes is extended to an adaptive oblivious transfer scheme. In that scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, onlyO(1) messages are exchanged and O(1) operations are performed. The preliminary version of this paper was published at PKC ’05 [Chu and Tzeng 2005].

Jan 1, 20040 citations