Databases associated with keywords, can be public, private or hybrid, as a result the solutions to keyword search protocols for each type are different. In this paper, we study the problem of privacy-preserving keyword search in the public database model where the data-item is public but a client wishes to retrieve some data-item or search data-item, without revealing to the server which item it is. The contribution of this paper is of three fold. In the first fold, an efficient implementation of oblivious linear function evaluation protocols for secure two-party computation of a linear function over a finite field that does not emulate the circuit for computing oblivious linear function while at the same time it is provably secure against malicious adversary is presented. We show our implementation is provably secure assuming that the underlying Fujisaki-Okamoto's commitment scheme is informational hiding and computational binding as well Paillier's encryption scheme is semantically secure in the common reference string model. In the second fold, we further extend the techniques to non-linear polynomials and thus provide a secure reduction of OPE protocols of a polynomial of degree m, to m OPEs of linear polynomials. In the third fold, we use the OPEs for solving the oblivious keyword search problem along the Ogata and Kurosawa's ad hoc methodology, and show that our implementation is provably secure assuming that the underlying Fujisaki-Okamoto's commitment scheme is informational hiding and computational binding, Paillier's encryption scheme is semantically secure, G is a pseudo-random function in the common reference string model.
Databases associated with keywords, can be public, private or hybrid, as a result the solutions to keyword search protocols for each type are different. In this paper, we study the problem of privacy-preserving keyword search in the public database model where the data-item is public but a client wishes to retrieve some data-item or search data-item, without revealing to the server which item it is. The contribution of this paper is of three fold. In the first fold, an efficient implementation of oblivious linear function evaluation protocols for secure two-party computation of a linear function over a finite field that does not emulate the circuit for computing oblivious linear function while at the same time it is provably secure against malicious adversary is presented. We show our implementation is provably secure assuming that the underlying Fujisaki-Okamoto's commitment scheme is informational hiding and computational binding as well Paillier's encryption scheme is semantically secure in the common reference string model. In the second fold, we further extend the techniques to non-linear polynomials and thus provide a secure reduction of OPE protocols of a polynomial of degree m, to m OPEs of linear polynomials. In the third fold, we use the OPEs for solving the oblivious keyword search problem along the Ogata and Kurosawa's ad hoc methodology, and show that our implementation is provably secure assuming that the underlying Fujisaki-Okamoto's commitment scheme is informational hiding and computational binding, Paillier's encryption scheme is semantically secure, G is a pseudo-random function in the common reference string model.
In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.
In this study, the authors design efficient protocols for a number of ‘oblivious decision program (DP) evaluation’ problems. Consider a general form of the problem where a client who holds a private input interacts with a server who holds a private DP (e.g. a decision tree or a branching program) with the goal of evaluating his input on the DP without learning any additional information. Many known private database query problems such as symmetric private information retrieval and private keyword search can be formulated as special cases of this problem. Most of the existing works on the same problem focus on optimising communication. However, in some environments (supported by a few experimental studies), it is the computation and not the communication that may be the performance bottleneck. In this study, we design ‘computationally efficient’ protocols for the above general problem, and a few of its special cases. In addition to being one‐round and requiring a small amount of work by the client (in the RAM model), the proposed protocols only require a small number of exponentiations (independent of the server's input) by both parties. The proposed constructions are, in essence, efficient and black‐box reductions of the above problem to 1‐out‐of‐2 oblivious transfer. It is proved that the proposed protocols secure (private) against ‘malicious’ adversaries in the standard ideal/real‐world simulation‐based paradigm.
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.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
A lot of interest has been drawn recently into public-key encryption with keyword search (PEKS), which keeps publickey encrypted documents amendable to secure keyword search. However, PEKS resist against keyword guessing attack by assuming that the size of the keyword space is beyond the polynomial level. But this assumption is ineffective in practice. PEKS are insecure under keyword guessing attack. As we observe, the key to defend such attack is to avoid the availability of the exact search trapdoor to adversaries. Accordingly, we compromise the exactness of search trapdoor by mapping at least two different keywords into a fuzzy search trapdoor. We propose a novel concept called public-key encryption with fuzzy keyword search (PEFKS), by which the un-trusted server only obtains the fuzzy search trapdoor instead of the exact search trapdoor, and define its semantic security under chosen keyword attack (SS-CKA) and indistinguishability of keywords under non-adaptively chosen keywords and keyword guessing attack (IK-NCK-KGA). For the keyword space with and without uniform distribution, we respectively present two universal transformations from anonymous identity-based encryption to PEFKS, and prove their SSCKA and IK-NCK-KGA securities. To our knowledge, PEFKS is the first scheme to resist against keyword guessing attack on condition that the keyword space is not more than the polynomial level.
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