We define the following problem termed n × 1-out-of-n oblivious transfer (n × 1-out-of-n OT): in a system with one server and n clients, how to securely and efficiently assign n secrets to n clients by the server, with each client getting a unique secret from the server, and the server and clients remain unknown of how the secrets are distributed? This is a novel problem that is fundamentally different than 1-out-of-n OT repeated n times, and is different than k-out-of-n OT as well. Nevertheless, the proposed OT has many practical applications such as privacy-preserving data aggregation in smart grids. It can also be employed to design crypto protocols for anonymous communications and group signatures. In this paper, we propose the first algorithm to efficiently and effectively implement the n × 1-out-of-n OT. We construct hidden permutation circuits to obliviously assign n secrets to n clients by the server within O(lg(n)) time. A rigorous theoretical analysis is also carried out to investigate the security strength and performance of the protocol.
We define the following problem termed n × 1-out-of-n oblivious transfer (n × 1-out-of-n OT): in a system with one server and n clients, how to securely and efficiently assign n secrets to n clients by the server, with each client getting a unique secret from the server, and the server and clients remain unknown of how the secrets are distributed? This is a novel problem that is fundamentally different than 1-out-of-n OT repeated n times, and is different than k-out-of-n OT as well. Nevertheless, the proposed OT has many practical applications such as privacy-preserving data aggregation in smart grids. It can also be employed to design crypto protocols for anonymous communications and group signatures. In this paper, we propose the first algorithm to efficiently and effectively implement the n × 1-out-of-n OT. We construct hidden permutation circuits to obliviously assign n secrets to n clients by the server within O(lg(n)) time. A rigorous theoretical analysis is also carried out to investigate the security strength and performance of the protocol.
Oblivious Transfer (OT) is a fundamental cryptographic primitive enabling privacy-preserving computation and constitutes a core building block for secure multi-party computation while supporting a wide range of security-sensitive applications: private information retrieval, zero-knowledge proofs, and password-authenticated key exchange, to cite a few. While recent advances in OT extension have significantly reduced amortised costs, their reliance on batches of random base OTs and substantial pre-computation phases limits their practicality in scenarios where the number of transfers is modest or where communication latency and client-side computation are critical constraints. In such settings, efficient base OT protocols remain both relevant and necessary. In this work, we introduce I-(OT)2, a novel base 1-out-of-2 OT protocol grounded in the quadratic residuosity problem, specifically designed to minimise receiver-side computation and interaction. Our construction is particularly appealing on client--server architectures in which the receiver operates on low-power hardware, such as Internet of Things (IoT) devices. Through a lightweight offline pre-computation phase, I-(OT)2 shifts the on-transfer computational burden almost entirely to the Sender, while reducing online communication to only six messages and four digests exchanged. We provide a detailed description of the protocol, accompanied by a formal proof of its security. Moreover, to demonstrate the viability of I-(OT)2, we also present an open-source proof-of-concept implementation (in C language) evaluated on real IoT hardware. Results are staggering: for 128-bit security using a 3072-bit RSA modulus, the receiver incurs an average online cost per OT as low as 2.80 μs on desktop platforms and 39.90 μs on IoT devices, more than 10× faster than the well known SimplestOT.
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.
Oblivious Transfer (OT), a fundamental primitive in cryptography and a cornerstone of Secure Multi-Party Computation (SMPC), is widely applied in privacy-preserving domains. Constructing efficient and secure OT protocols remains an active research area. To address the limitations of existing OT protocols, such as high time complexity and poor scalability, this paper proposes a secure and efficient k-out-of-n oblivious transfer protocol based on the Paillier homomorphic encryption algorithm . The protocol employs a system of multivariate equations to enable the receiver to select k messages from n messages held by the sender. By integrating multi-threaded parallel processing, the computational speed of ciphertext matrix-vector operations is significantly improved. Additionally, plaintext-ciphertext computation replaces traditional encryption methods to optimize the Paillier algorithm’s efficiency for batch data encryption. Experimental results demonstrate that, compared to recent k-out-of-n OT schemes: when n exceeds 30,000 with k=1, the protocol achieves a 200% performance improvement; when n=512 and k=256, it outperforms existing protocols by approximately 100% in overall efficiency.
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.
The security of digital goods buyers and sellers is unbalanced. Of course, the property of sellers is protected; for example, when customers acquire digital books or films from Internet's merchants, they only receive the products they have paid for. Unfortunately, the buyers' privacy is rarely respected: purchases are often — without the buyers' knowledge — monitored, recorded, analysed, and sometimes sold to marketing companies. As a consequence, even if the customers do not intend to acquire additional products, their computer screens are later invaded with targeted advertisements. The main purpose of this thesis is to propose some methods to restore the balance and guarantee the buyers' privacy, while protecting the interests of the sellers. To this end, it is worth looking into the area of cryptography and more specifically, it is worth studying and designing some protocols called distributed oblivious transfer (DOT) protocols. A DOT protocol allows a party A to obtain one of the secret pieces of information (a secret for short) held by a party B so that the following two fundamental conditions are satisfied: • A chooses the secrets she wishes to obtain and does not obtain anything on the secrets she has not chosen, • B does not learn which secret was obtained by A. Furthermore, to improve the availability of the information, the protocol is distributed. That is, the party B transmits his secret information to m servers and the party A needs to contact at least k of these servers to obtain the chosen secret. The servers are not fully trusted, neither by A, nor by B. Therefore, from the information exchanged with A and B, no coalition of servers should be able to learn the secrets of B or the choice of A. The results of a preliminary literature review are surprising. In fact, the number of publications on DOT protocols is small (fewer than 20) compared to, for example, the number of publications on a similar concept, secret sharing (100s of publications). And yet, oblivious transfer is a fundamental component of more complex cryptographic protocols such as multi-party computation protocols, which allow a group of participants to securely calculate any function of their joint secret inputs. So, one could expect many variants, for example of the original DOT protocol introduced in 2002 by Naor and Pinkas [74], to fulfil the requirements of specific scenarios. The design of variants of DOT protocols in traditional cryptography has been the guiding thread of my research. My contribution mainly consists in (a) a critical analysis of the existing protocols, demonstrating their limitations, weaknesses, and in some cases, flaws; and (b) the design of the following protocols,well adapted to some specific situations: A Strongly Secure DOT Protocol. This DOT protocol addresses the most important weakness of unconditionally secure, one-round, polynomial interpolation-based DOT protocols: after the protocol has been executed, if the party A corrupts only one server, she can learn all the secrets of the party B. The protocol is secure even if A corrupts up to k - 1 servers. A Verifiable DOT Protocol. The party A should obtain the secret she has chosen, even when some servers are controlled by a malicious adversary whose objective is to sabotage the protocol. This is the case with this protocol, assuming that the adversary cannot control more than k - 1 servers. A Multiple Secrets DOT Protocol. When the party A wishes to obtain n > 1 secrets, the current protocols have to be executed n times. In this context, they are inefficient. The DOT protocol introduced here allows the party A, by contacting in the same session k - 1 + n servers, to collect n secrets. Adaptive DOT Protocols. The previous protocol allows the party A to request several secrets. However, the request of one secret may depend on the values of secrets already obtained. Two efficient protocols are presented in this scenario. The first one allows A to receive a limited number of secrets and therefore, is well adapted to a single receiver. For several receivers, a second protocol is proposed. This second protocol accepts an unlimited number of queries, but requires communications amongst the servers. A Threshold DOT protocol. Most existing DOT protocols rely on threshold secret sharing schemes. In a k-threshold protocol or scheme, security is guaranteed not only when k parties are contacted, but also when more than k parties are contacted. However, the existing DOT protocols based on k-threshold secret sharing schemes require an additional mechanism to control that exactly k servers are contacted, which is an under-utilisation of the underlying functionality. The proposed protocol is the first k-threshold DOT protocol which allows the party A to contact as many servers as she wishes to obtain the chosen secret, provided that at least k servers are contacted. This research is limited to unconditionally secure protocols, i.e., protocols whose security does not depend on mathematical (unproven) assumptions; within the limits of the given security models, the protocols are secure even against an adversary with unlimited computing power and time. In brief, the results presented in this thesis are a significant advance to the state of the art research on DOT protocols because on one hand, they point out the weaknesses of the DOT protocols most commonly accepted by the cryptographic community and on the other hand, they contribute to the cryptographic field through the design of new protocols, secure and efficient.
Oblivious Transfer (OT) has been regarded as one of the most significant cryptography tools in recent decades.Since the mechanism of OT is widely used in many applications such as e-commerce, secret information exchange, and games, various OT schemes have been proposed to improve its functionality and efficiency.In 2001, Naor and Pinkas proposed a secure 1-out-of-n OT protocol, in which the sender has n messages and the chooser can get one of these n messages in each protocol run.What is more, the sender cannot find which message has been chosen by the chooser and the chooser knows only the correct message.In 2004, Wakaha and Ryota proposed a secure t-out-of-n OT protocol, which is an extension of the 1-out-of-n OT protocol proposed by Naor and Pinkas.Wakaha and Ryota's tout-of-n OT protocol allows the chooser to get t messages from the sender simultaneously in each protocol run.Besides, the sender cannot know what the chooser has chosen and the chooser can only know the exact t messages.However, getting deep understanding of Wakaha and Ryota's protocol, it could be concluded that it still lacks efficiency such that it is hard to be applied in real-world applications.In this article, a secure and efficient t-out-of-n OT protocol based on the Generalized Chinese Remainder Theorem is proposed, in which the chooser can securely get t messages from the sender simultaneously in each protocol run.The efficiency of the proposed t-out-of-n OT protocol is higher than that of Wakaha and Ryota's protocol in terms of practical application.