Source-linked AI summary
Flexible quantum private queries based on quantum key distribution
Fei Gao, Bin Liu, Qiao-Yan Wen, Hui Chen
TL;DR
Private information retrieval seeks to let Alice retrieve a database item without revealing her query, while SPIR also limits her access to other items. This paper proposes a flexible QKD-based query protocol whose tunable parameters control Alice’s expected known key bits. It reports that smaller θ can improve database security, while θ < π/4 generally permits smaller k and fewer transmitted qubits.
Problem
Private information retrieval aims to let Alice obtain a chosen database item without revealing her query, while SPIR also seeks to prevent her from obtaining other items.
Source: §I · p. 1Method
The paper generalizes J-protocol with a QKD-based QPQ scheme that uses a tunable θ and key postprocessing to control Alice’s known key bits.
Source: §I · p. 2, A. The protocol · p. 2Results
For θ < π/4, fewer substrings k are generally needed than in J-protocol, reducing transmitted qubits, and choosing smaller θ improves database security.
Source: B. The features of our protocol · p. 3, A. Database security · p. 5Takeaways & Limitations
Adjusting θ lets users set Alice’s expected number of known key bits to a chosen value for any database size.
Source: §I · p. 2, B. The features of our protocol · p. 3The protocol has no effective error-correction or privacy-amplification method for achieving high final-key correctness when Alice knows only part of the key and Bob does not know which bits she knows.
Source: B. The features of our protocol · p. 4
Abstract
from arXiv · showhide
We present a flexible quantum-key-distribution-based protocol for quantum private queries. Similar to M. Jakobi et al's protocol [Phys. Rev. A 83, 022301 (2011)], it is loss tolerant, practical and robust against quantum memory attack. Furthermore, our protocol is more flexible and controllable. We show that, by adjusting the value of $\theta$, the average number of the key bits Alice obtains can be located on any fixed value the users wanted for any database size. And the parameter $k$ is generally smaller (even $k=1$ can be achieved) when $\theta<\pi/4$, which implies lower complexity of both quantum and classical communications. Furthermore, the users can choose a smaller $\theta$ to get better database security, or a larger $\theta$ to obtain a lower probability with which Bob can correctly guess the address of Alice's query.
I. INTRODUCTION
Quantum private queries address how Alice can retrieve a database item without revealing her query while limiting what she learns about Bob’s database. This paper proposes a more flexible QKD-based protocol building on J-protocol.
I. INTRODUCTION
- SPIR seeks to let Alice retrieve her chosen item without revealing which item she obtained, while preventing her from accessing other database items.The introduction notes that ideal SPIR cannot be implemented, motivating a practical requirement that Alice learn sufficiently little of the database.Source: §I · p. 1
- Quantum private queries (QPQ) are quantum schemes for the SPIR problem.The GLM protocol uses separate query states for retrieval and checking Bob’s potential attack; it is cheat-sensitive for Alice’s privacy and limits dishonest retrieval to at most two items.Source: §I · p. 1
- O-protocol combines retrieval and attack checking in one query state, and Bob’s answer may reveal an attack if he tries to learn Alice’s privacy.Its attack check is not real-time, and it can further reduce communication complexity.Source: §I · p. 1
- GLM and O-protocol are difficult to implement for large databases because their oracle operations have very high dimension.The cited J-protocol offers a QKD-based alternative designed to generalize to large databases.Source: §I · pp. 1–2
- J-protocol uses SARG04 QKD to distribute an asymmetric key, enabling Alice to obtain limited database items while supporting large databases and loss tolerance.Earlier GLM and O-protocol designs are difficult to implement for large databases because their oracle operations have high dimension.Source: §I · pp. 1–2
- The proposed QKD-based QPQ generalizes J-protocol and lets users tune Alice’s expected key bits to a chosen value for databases of any size.The authors also report lower communication complexity and higher security when suitable parameters are selected.Source: §I · p. 2
II. QPQ PROTOCOL BASED ON QKD
The protocol is introduced for a database with N items, where Alice has bought one item and wants to retrieve it secretly from Bob.
II. QPQ PROTOCOL BASED ON QKD
- The setting assumes Bob’s database contains N items.The two users then execute the protocol described in the following section.Source: §II · p. 2
- Alice has bought one of Bob’s database items and seeks to obtain it secretly.The passage states this as the protocol’s use case.Source: §II · p. 2
- The users execute the protocol for Alice’s private retrieval from Bob’s database.The protocol is framed for a database of arbitrary size N.Source: §II · p. 2
A. The protocol
Bob sends randomly prepared photons, and Alice measures them before Bob reveals a bit that helps her infer the encoded key. They postprocess the shared raw key and use a known key bit to retrieve her chosen database item.
A. The protocol
- Bob randomly prepares photons in four states, while Alice randomly measures each received photon in basis B or B′.The primed and unprimed states encode bits 1 and 0, respectively, and θ can be selected continuously.Source: A. The protocol · p. 2
- Alice’s loss declarations do not help her cheat because she has no information about the sent bits at that stage, making the protocol loss tolerant.Lost photons are disregarded; the passage describes this feature as similar to J-protocol.Source: A. The protocol · p. 2
- Bob announces one bit for each successfully measured qubit, indicating whether its original state was |0⟩ or |0′⟩, or |1⟩ or |1′⟩.Alice first reports which instances she detected successfully; lost-photon bits are disregarded.Source: A. The protocol · p. 2
- Alice’s measurement and Bob’s bit declaration yield conclusive results with probability p = sin^2 θ/2, while the remaining results are inconclusive.The resulting raw key is fully known to Bob and only partly known to Alice; the bit inference process is described as similar to B92 QKD.Source: A. The protocol · p. 2
- Alice and Bob combine k raw-key substrings of length N bitwise to form a final N-bit key, generally leaving Alice with only several known bits.If Alice has no known bits after this step, the protocol restarts; the authors say this occurs with small probability for suitable parameters.Source: A. The protocol · p. 2
- Bob encrypts the database with a shifted key so Alice can use a known bit to retrieve her chosen item.If Alice knows key bit K_j and wants database item X_i, she declares s = j − i; Bob shifts the key by s and encrypts the database using the resulting key.Source: A. The protocol · p. 2
B. The features of our protocol
The protocol generalizes J-protocol while allowing users to tune Alice’s expected number of known key bits for any database size. It retains J-protocol’s practical, loss-tolerant features and can reduce communication with suitable parameter choices.
B. The features of our protocol
- Like J-protocol, the scheme resists Alice’s quantum memory attack, is loss tolerant, and can scale to huge databases without a high-dimensional oracle.At θ = π/4, it becomes J-protocol.Source: B. The features of our protocol · pp. 2–3
- For θ < π/4 with p = 0.15, N = 50000 requires 5 substrings rather than J-protocol’s 7, saving at least 2N = 10^5 qubits.The text also says k = 1 is feasible for database sizes that are not too large.Source: B. The features of our protocol · p. 3
- By selecting θ and k, users can set Alice’s expected known-key-bit count to a chosen value for any database size N.The figure illustrates ¯n = 3 for any N, and the text says similar results hold for other targets.Source: B. The features of our protocol · p. 3, Figure 1 · p. 3
- For large N, pursuing k = 1 requires very small θ and may be technically difficult, so k > 1 may be needed.The text says suitable θ and k can still achieve a chosen ¯n for any N; for example, θ > 0.2 can achieve ¯n = 3 by adjusting k.Source: B. The features of our protocol · p. 3
- Additional known key bits can help Alice obtain other database items or publicly check the key’s error rate.The text notes that such checks indicate correctness only to some extent; effective error correction or privacy amplification is not yet available for this setting.Source: B. The features of our protocol · pp. 3–4
- With suitable parameters, Bob sends Alice 1 bit per qubit instead of the 2 bits required in J-protocol.Source: B. The features of our protocol · p. 4
III. SECURITY ANALYSIS
The security analysis adapts the analysis of J-protocol because this protocol generalizes it. The discussion focuses on how security changes when θ differs from π/4.
III. SECURITY ANALYSIS
- The authors state that J-protocol’s security analysis can be adapted because their protocol generalizes J-protocol.Source: §III · p. 4
- At θ = π/4, the protocol is the J-protocol case used as the security-analysis reference point.Source: §III · p. 4
- The analysis focuses on how security degree changes when θ ≠ π/4.Source: §III · p. 4
A. Database security
The protocol’s database security depends on θ: choosing θ < π/4 improves security relative to J-protocol, while small θ reduces Alice’s success in obtaining final-key bits. Alice’s individual and joint measurement strategies, including delayed measurement after storing qubits, bound the security analysis.
A. Database security
- Alice’s quantum-memory strategy is to store received qubits and measure them after Bob’s declaration to seek more raw-key bits.The analysis also considers individual USD measurements on each received qubit.Source: A. Database security · p. 4
- 3.21 key bits by USD versus 3.02 by projective measurement at θ = 0.284, N = 50000, and k = 3; J-protocol yields 9.3 at the same target.The passage describes the USD advantage over projective measurement as negligible, especially for small θ.Source: A. Database security · p. 4, Figure 3 · p. 5
- For small θ, joint USD yields fewer final-key bits, and choosing θ < π/4 improves database security relative to J-protocol.The θ = π/4 curve represents J-protocol.Source: Figure 4 · p. 5, A. Database security · p. 5
- For small θ, Helstrom guessing approaches a random 1/2 chance of correctly identifying a final key bit.Joint USD success declines rapidly with k.Source: A. Database security · pp. 4–5
B. User privacy
The protocol keeps user privacy cheat-sensitive: Bob cannot deterministically learn Alice’s query address and give the correct answer at the same time. The choice of θ tunes how likely Bob is to predict Alice’s conclusive bits and query address, without letting him answer with certainty.
B. User privacy
- Bob cannot simultaneously learn Alice’s query address and give the correct answer deterministically, preserving cheat-sensitive user privacy.If Bob learns whether a raw-key bit is conclusive, he loses knowledge of that bit’s value; the authors ground this protection in the no-signaling principle.Source: B. User privacy · p. 5
- For θ < π/4, Bob can more readily predict Alice’s conclusive bits, but loses the corresponding key-bit value and cannot answer with certainty.The optimal attack sends |0′′⟩ or |1′′⟩ and announces 1 or 0, respectively.Source: B. User privacy · p. 5
- A larger θ can lower the probability that Bob correctly guesses Alice’s query address, while a suitable θ can permit k = 1.The figure plots Alice’s conclusive-result probability against θ, with the dashed line marking the J-protocol at θ = π/4.Source: B. User privacy · p. 6, Figure 5 · p. 6
IV. CONCLUSIONS
The paper presents a flexible QKD-based QPQ protocol as a generalization of the J-protocol.
IV. CONCLUSIONS
- The proposed flexible QKD-based QPQ protocol generalizes the J-protocol.Source: §IV · p. 6