A Framework For T-out-of-n Oblivious Transfer With Security Against Covert Adversaries

Oblivious transfer (OT) may be the most important cryptographic primitive. Seen from the view of theoretical cryptography, it is a fundamental role. This follows the fact that if there exists an protocol which securely computes OT, then for any efficiently computable functionality, there exists an protocol which securely computes it. Seen from the view of applied cryptography, it is a basic tool in the field of database search and electronic com-merce.In literature, malicious adversaries are generally considered. A malicious adversary may arbitrarily deviate from the prescribed protocol and is ready to do any cheating if a chance is available. However, this is too pessimistic to design efficient and practical pro-tocols. In this paper, we consider covert adversaries which are presented by Aumann and Lindell. A covert adversary will not always do cheating because of its loss caused by be-ing caught. Security against covert adversaries does not rule out all successful cheating of covert adversaries. However, this security guarantees that honest participants catch covert adversaries' cheating with a desirable probability.In this paper, we are concerned with t-out-of-n oblivious transfer (OTtn) protocols deal-ing with the following scenario. A database/sender holds n private values m1,m2,..,mn and a client/receiver holds t private indices i1, i2,..., it. The objective of the receiver is to recover the t database values corresponding to his index set (i.e. mi1, mi2,..., mit) without leaking any information about any of those indexes. In parallel, the sender do not want the receiver to learn anything but the t values it queried about.In this paper, we use smooth projective hashing (SPH) to construct a framework for OTtn with security against covert adversaries. Since previous SPH does not suffice for our application, we define another variant of SPH. The most essential difference between the two SPH variants is that previous SPH provides witnesses only to projective instances while ours provides witnesses to both projective and smooth instances. The modification made by the latter version solves the problem of how to gain the simulation-based security in the case that only the receiver is corrupted and it solves the question of how to deal with general OTtn.There is a folklore before us that it is technically difficult to instantiate SPH under the learning with errors (LWE) assumption. However, we observe that, the algorithm which computes the hash values can be viewed as a encryption algorithm, and the algorithm which computes the projection values can be viewed as a decryption algorithm. Naturally, we can take public-private key pairs as instance-witness pairs. Based on this observation, we in-stantiate the new variant under the LWE assumption. Besides the LWE assumption, we also show that the new variant can be instantiated under the decisional Diffie-Hellman (DDH) assumption, the decisional N-th residuosity (DNR) assumption and the decisional quadratic residuosity (DQR) assumption as previous SPH.Using the new variant SPH, we construct a practical framework for ottn with security against covert adversaries. Our framework has the following features.●It is realizable under generic mathematical assumptions. This follow the fact that we realize the new SPH variant under the DDH assumption, the DNR assumption, the DQR assumption and the LWE assumption, respectively.●It is usable in practice as it works in the plain model where there is no trusted set-up such as a trusted common reference string or a tamper-proof hardware. It only needs an authenticated channel between both participants.●It is computationally efficient. It needs only 4 communication rounds. The main computational overhead is (K-g)n encryptions at the sender and (K-g)t decryp-tions at the receiver. When compared to existing practical protocols with security against covert adversaries or security against malicious adversaries, our framework is generally more efficient, where K, g are two positive integers such that K>g.●In the case that the sender is corrupted, the honest receiver catches the adversaries' cheating with probability 1. In the case that the receiver is corrupted, the honest sender catches the adversaries' cheating with probability 1-1(K-gK).One of our theoretical contributions is that we reduce the existence of OTtn to the ex-istence of SPH. This follows the fact that our framework only employs one cryptographic primitive, i.e., the new SPH variant. Before this paper, only such a half-simulatable reduc-tion, which is hard to make sense in the field of secure multi-party computation, is known.As additional contributions, we present several lemmas about indistinguishability based on multiple samples. These lemmas simplify our security proof very much. We believe that they are as useful in security proof somewhere else as in this paper.