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
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
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
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.
Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications such as secure multi-party computation, private information retrieval, private set intersection, contract signing, and privacy-preserving location-based services. The OT protocol has different variants such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. In the OT (one-out-of-2, one-out-of- n , and OT extension) protocol, the sender has a set of messages, whereas the receiver has a key. The receiver sends that key to the sender in a secure way; the sender cannot get any information about the received key. The sender encrypts every message by operating on every message using the received key and sends all the encrypted messages to the receiver. The receiver is able to extract only the required message using his key. However, in the k -out-of- n OT protocol, the receiver sends a set of k keys to the sender, and in replay, the sender sends all the encrypted messages. The receiver uses his keys and extracts the required messages, but it cannot gain any information about the messages that it has not requested. Generally, the OT protocol requires high communication and computation cost if we transfer millions of oblivious messages. The OT extension protocol provides a solution for this, where the receiver transfers a set of keys to the sender by executing a few numbers of OT protocols. Then, the sender encrypts all the messages using cheap symmetric key cryptography with the help of a received set of keys and transfers millions of oblivious messages to the receiver. In this work, we present different variants of OT protocols such as one-out-of-2, one-out-of- n , k -out-of- n , and OT extension. Furthermore, we cover various aspects of theoretical security guarantees such as semi-honest and malicious adversaries, universally composable, used techniques, computation, and communication efficiency aspects. From the analysis, we found that the semi-honest adversary-based OT protocols required low communication and computation costs as compared to malicious adversary-based OT protocols.
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].
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.
Oblivious Transfer (OT) is an important cryptographic tool, which has found its usage in many crypto protocols, such as Secure Multiparty Computations, Certified E-mail and Simultaneous Contract Signing . In this paper, we propose three k-out-of-n OT (OT_k^n) protocols based on additive homomorphic encryption. Two of these protocols prohibit malicious behaviors from a 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 comparable to 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.