2018/01/31 by Arpita Maitra
Computer Science · Physics and Astronomy · #Alice (programming language) #Alice and Bob #Correctness #Identity (music) #Intersection (aeronautics) #Oblivious transfer #Protocol (science) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum computer #Set (abstract data type) #quant-ph
paper · pdf · doi:10.1007/s11128-018-1968-9
published as Quantum Information Processing, 2018 · 14 pages, almost same as published version
openalex created_date 2018/02/02 · openalex publication_date 2018/06/26 · arxiv created 2018/06/27 · arxiv updated 2018/06/28 · openalex updated_date 2026/08/05
Recently, Shi et al. (Phys. Rev. A, 2015) proposed Quantum Oblivious Set Member Decision Protocol (QOSMDP) where two legitimate parties, namely Alice and Bob, play a game. Alice has a secret k and Bob has a set \k1,k2,⋯ kn\. The game is designed towards testing if the secret k is a member of the set possessed by Bob without revealing the identity of k. The output of the game will be either "Yes" (bit 1) or "No" (bit 0) and is generated at Bob's place. Bob does not know the identity of k and Alice does not know any element of the set. In a subsequent work (Quant. Inf. Process., 2016), the authors proposed a quantum scheme for Private Set Intersection (PSI) where the client (Alice) gets the intersected elements with the help of a server (Bob) and the server knows nothing. In the present draft, we extended the game to compute the intersection of two computationally indistinguishable sets X and Y possessed by Alice and Bob respectively. We consider Alice and Bob as rational players, i.e., they are neither "good" nor "bad". They participate in the game towards maximizing their utilities. We prove that in this rational setting, the strategy profile ((cooperate, abort), (cooperate, abort)) is a strict Nash equilibrium. If ((cooperate, abort), (cooperate, abort)) is strict Nash, then fairness as well as correctness of the protocol are guaranteed.