Private set intersection is an important problem with implications in many areas, ranging from remote diagnostics to private contact discovery. In this work, we consider the case of two-party PSI in the honest-but-curious setting. We propose a protocol that solves the server-aided PSI problem using delegated blind quantum computing. More specifically, the proposed protocol allows Alice and Bob (who do not have any quantum computational resources or quantum memory) to interact with Steve (who has a quantum computer) in order for Alice and Bob to obtain set intersection such that privacy is preserved. In particular, Steve learns nothing about the clients' input, output, or desired computation. The proposed protocol is correct, secure and blind against a malicious server, and characterized by a quantum communication complexity that is linear in the input size.
We study K-out-of-N oblivious transfer (OT) over a binary erasure channel (BEC) and a public noiseless channel, under an honest-but-curious model. In this setting, a client retrieves K out of N messages stored by a server; the protocol must guarantee that the unselected messages remain private to the server and that the client’s choices remain hidden from the server. We show that the K-out-of-N OT capacity over a BEC with erasure probability ϵ is
C=min(N−KKε,1−ε). This characterization recovers the known capacity for 1-out-of-2 OT and, for 1-out-of-N OT, recovers the established capacity when $\frac{{N - 1}}{N} \leq \varepsilon $ while further establishing the capacity for all ϵ ∈ [0,1]. We also show that the naive K-out-of-N OT construction obtained by repeating an optimal 1-out-of-N OT protocol K times is suboptimal.
In this paper we focus on protocols for private set intersection (PSI), through which two parties, each holding a set of inputs drawn from a ground set, jointly compute the intersection of their sets. Ideally, no further information than which elements are actually shared is compromised to the other party, yet the input set sizes are often considered as admissible leakage.In the unconditional setting we evidence that PSI is impossible to realize and that unconditionally secure size-hiding PSI is possible assuming a set-up authority is present in an set up phase. In the computational setting we give a generic construction using smooth projective hash functions for languages derived from perfectly-binding commitments. Further, we give two size-hiding constructions: the first one is theoretical and evidences the equivalence between PSI, oblivious transfer and the secure computation of the AND function. The second one is a twist on the oblivious polynomial evaluation construction of Freedman et al. from EUROCRYPT 2004. We further sketch a generalization of the latter using algebraic-geometric techniques. Finally, assuming again there is a set-up authority (yet not necessarily trusted) we present very simple and efficient constructions that only hide the size of the client's set.
Recently, we proposed a quantum solution to the problem of private set intersection cardinality (PSI-CA) (Information Sciences 370–371 (2016) 147–158). Compared to classical solutions, the proposed quantum PSI-CA protocol achieves an exponential reduction in communication complexity, since it only needs
O(1)communication cost. However, this protocol requires two additional assumptions about the cardinalities of the sets, which may limit its wider applications. In this paper, we successfully discard these assumptions and present a stronger quantum PSI-CA protocol without any limitation. The new protocol ensures the parties’ private security, i.e., unconditionally secure server privacy and statistically secure client privacy, and it achieves the constant computation and communication complexities, which are independent of the size of the sets. Therefore, it is more suitable for practical applications with big data sets.
We study the problem of private set intersection (PSI). In this problem, there are two entities
Ei, for
i=1,2, each storing a set
Pi, whose elements are picked from a finite set
SK, on
Nireplicated and non-colluding databases. It is required to determine the set intersection
P1∩P2without leaking any information about the remaining elements to the other entity, and to do this with the least amount of downloaded bits. We first show that the PSI problem can be recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with certain added restrictions. Next, as a stand-alone result, we derive the information-theoretic sum capacity of MM-SPIR,
CMM−SPIR. We show that with
Kmessages,
Ndatabases, and a given size of the desired message set
P, the exact capacity of MM-SPIR is
CMM−SPIR=1−N1when
P≤K−1, provided that the entropy of the common randomness
Ssatisfies
H(S)≥N−1Pper desired symbol. When
P=K, the MM-SPIR capacity is trivially 1 without the need for any common randomness
S. This result implies that there is no gain for MM-SPIR over successive single-message SPIR (SM-SPIR). For the MM-SPIR problem, we present a novel capacity-achieving scheme which builds seamlessly over the near-optimal scheme of Banawan-Ulukus originally proposed for the multi-message PIR (MM-PIR) problem without any database privacy constraints. Surprisingly, our scheme here is exactly optimal for the MM-SPIR problem for any
P, in contrast to the scheme for the MM-PIR problem, which was proved only to be near-optimal. Our scheme is an alternative to the successive usage of the SM-SPIR scheme of Sun-Jafar. Based on this capacity result for the MM-SPIR problem, and after addressing the added requirements in its conversion to the PSI problem, we show that the optimal download cost for the PSI problem is given by
min{⌈N2−1P1N2⌉,⌈N1−1P2N1⌉}, where
Piis the cardinality of set
Pi.
We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.