PaperlayerView exact revision on arXiv

Source-linked AI summary

Post-processing of the oblivious key in quantum private queries

Fei Gao, Bin Liu, Wei Huang, Qiao-Yan Wen

arXiv:1406.0589v1quant-phcs.CR

TL;DR

Noisy channels can introduce errors into QPQ’s shared raw key, while post-processing of the oblivious key remains a challenge. The paper analyzes information leakage in dilution methods and proposes error correction; simulations report database recovery with limited queries and lower final-key error rates under specified conditions.

  • Problem

    Noisy channels create errors in QPQ’s shared raw key, making error correction necessary to avoid Alice receiving incorrect items.

    Source: §IV · p. 7

  • Method

    The paper analyzes security leakage in existing oblivious-key dilution methods and adapts shift-addition to further process the key for error correction.

    Source: §I · p. 2, §IV · p. 8

  • Results

    Simulations show Alice can obtain the whole database with an average of 53.4 queries for N = 104, while the gkN − N method has visibly lower FOK error rates than the original method when e < 30%.

    Source: §I · p. 2, §IV · p. 9

  • Takeaways & Limitations

    The proposed error-correction method completes oblivious-key post-processing and makes QPQ more practical for a real noisy channel.

    Source: §I · p. 2

    The error-rate reduction comes with a sacrifice in failure probability and communication efficiency.

    Source: §IV · p. 9

Abstract

from arXiv · show

Quantum private query (QPQ) is a kind of quantum protocols to protect both users' privacy in their communication. There is an interesting example, that is, Alice wants to buy one item from Bob's database, which is composed of a quantity of valuable messages. QPQ protocol is the communication procedure ensuring that Alice can get only one item from Bob, and at the same time, Bob cannot know which one was taken by Alice. Owing to its practicability, quantum-key-distribution-based QPQ has draw much attention in recent years. However, the post-processing of the key in such protocols, called oblivious key, remains far from being satisfactorily known. Especially, the error correction method for such special key is still missing. Here we focus on the post-processing of the oblivious key, including both dilution and error correction. On the one hand, we demonstrate that the previous dilution method, which greatly reduces the communication complexity, will bring Alice the chance to illegally obtain much additional information about Bob's database. Simulations show that by very limited queries Alice can obtain the whole database. On the other hand, we present an effective error-correction method for the oblivious key, which completes its post-processing and makes such QPQ more practical.

I. INTRODUCTION

QPQ aims to let Alice retrieve an item without Bob learning its address, while limiting what Alice learns from Bob’s database. This paper examines oblivious-key post-processing, showing a database-security risk in prior dilution methods and proposing error correction for noisy channels.

I. INTRODUCTION

  • QPQ is a quantum scheme for symmetric private information retrieval, in which Alice’s retrieval address remains hidden from Bob.The paper frames the task as protecting both users’ privacy and says Alice should obtain at most one database item.Source: §I · p. 1
  • Prior N − N and rM − N dilution methods reduce communication complexity, but their parity leakage raises a database-security question.The paper attributes these improved methods to M. V. Panduranga Rao et al.Source: §I · p. 2
  • Channel errors can leave Alice with an incorrect final-key bit, while the additional key information Bob must disclose for correction could let her obtain more bits than expected.The paper says earlier post-processing methods focused on dilution and left error correction unresolved.Source: §I · p. 2
  • For N = 104, simulations show Alice can obtain much more than expected—even the whole database—through an average of 53.4 queries.The paper identifies this as a security risk from the prior dilution methods.Source: §I · p. 2
  • The proposed error-correction method completes oblivious-key post-processing and is intended to make QPQ more practical over real noisy channels.The paper describes dilution and error correction as the two parts of post-processing.Source: §I · p. 2

II. PREVIOUS DILUTION METHODS

The section reviews three dilution methods that transform a raw oblivious key into a final key satisfying the stated requirements.

II. PREVIOUS DILUTION METHODS

  • The kN − N method, given by M. Jakobi et al., is a previous oblivious-key dilution method that aims to dilute a shared raw oblivious key OR into a final oblivious key OF satisfying R1, R2′, and R3.Source: §II · p. 2
  • The N − N method, attributed to M. V. Panduranga Rao et al, is one of two improved dilution methods reviewed.The section assumes Alice and Bob share a raw oblivious key satisfying R1–R3.Source: §II · p. 2
  • The rM − N method, also attributed to M. V. Panduranga Rao et al, is the other improved method reviewed.The stated aim of dilution is a final key satisfying R1, R2’, and R3.Source: §II · p. 2

A. The kN −N method

The kN − N method dilutes a raw oblivious key to a final key and reduces Alice’s known bits in the illustrated case.

A. The kN − N method

  • The method converts a kN-bit raw oblivious key into an N-bit final oblivious key.The passage describes the key bits as ROK and FOK, respectively.Source: A. The kN −N method · p. 2
  • The cited passage signals that this method specifies a relation between OR and OF and defines L as addition modulo 2, but it does not provide the relation itself.Source: A. The kN −N method · p. 2
  • In the example, Alice’s known bits decrease from 6 to 1 after dilution.Source: A. The kN −N method · p. 3

B. The N −N method

The N − N method dilutes a raw oblivious key to a final key and reduces Alice’s known bits in the illustrated case.

B. The N − N method

  • The method relates an N-bit raw oblivious key to an N-bit final oblivious key.The passage identifies the two keys as ROK and FOK.Source: B. The N −N method · p. 3
  • The supplied example specifies the raw and final key formats but does not state their relation’s operation in the provided passages.Source: B. The N −N method · p. 3
  • In the example, Alice’s known bits decrease from 3 to 1 after dilution.Source: B. The N −N method · p. 3

C. The rM −N method

The rM−N method extends each ROK sub-key with parities of all k-bit combinations, then combines the extended keys using chosen relative shifts. This reuses ROK bits while limiting Alice’s knowledge of the final key without increasing the probability that she knows no final-key bit.

C. The rM −N method

  • Each of the r sub-keys is extended with the parities of all possible k-bit combinations, producing a new key.The rM-bit ROK is divided into r sub-keys of length M.Source: C. The rM −N method · p. 3
  • The extended keys are combined bitwise using relative shifts that Alice can choose to form the FOK.Each output bit combines positions in the extended keys offset by their respective shifts.Source: C. The rM −N method · p. 3
  • Shift-addition reduces Alice’s known bits in the final key without increasing her probability of knowing no final-key bit.The preceding extension reuses ROK bits to reduce communication, but can leave Alice knowing more bits in each extended key than expected.Source: C. The rM −N method · p. 3

III. SECURITY ANALYSIS ON THE IMPROVED DILUTION METHODS

The improved dilution methods reduce communication by reusing ROK bits, but this makes parity information about some FOK bits easier for Alice to obtain. Across multiple queries, the resulting almost-known sets can combine and expose the database.

III. SECURITY ANALYSIS ON THE IMPROVED DILUTION METHODS

  • Improved N−N and rM−N dilution reuse ROK bits to reduce communication, but make some FOK parity information easier for Alice to obtain.For N−N, Alice can know the parity of adjacent FOK bits without knowing their individual values.Source: §III · p. 3
  • A database item encrypted with a key bit in an AKS becomes known when Alice learns any one bit in that set.This connects the key-parity leakage to the corresponding secret messages.Source: §III · p. 4
  • Almost Known Sets (AKSs) can combine across queries, and learning one bit in a set reveals all its database items.Overlapping sets can link into larger sets; the authors state that enough queries can ultimately expose the whole database.Source: §III · p. 4
  • The leakage can let Alice obtain the whole database with substantially fewer than N queries, even without using AKS information.The text says Alice can obtain the whole database in at most N queries without AKSs, while leaked parity information can make the attack much quicker.Source: §III · p. 4

A. Analysis on the N −N method

Simulations of the N−N method show that parity leakage can let Alice recover the database in far fewer queries than expected from the items she obtains per query. The simulated attack repeats queries and chooses later shifts to minimize unknown database information.

A. Analysis on the N −N method

  • The attack simulates repeated N−N queries using ROK bits known independently with probability p, with p = 0.25 or 0.29 for the tested attacks.The simulations cover multiple database sizes and report average queries to recover the whole database.Source: A. Analysis on the N −N method · pp. 4–5
  • For later queries, Alice chooses the shift that minimizes unknown database information, counting both unknown items and AKSs.The simulation tracks item states after dilution and updates them as ciphertext arrives.Source: A. Analysis on the N −N method · p. 4
  • 53.4 queries on average (p = 0.25) let Alice steal a database of N = 104 items, versus an expected minimum of 4098.4 queries; at p = 0.29, the DQA is 40.0.The simulations averaged 10 runs; the expected minimum is based on 2.44 items obtained per query.Source: Table I · p. 4, A. Analysis on the N −N method · p. 5

B. Analysis on the rM −N method

Analysis shows that the rM−N method leaves the Final Oblivious Key determined by a basis of T bits, enabling Alice to recover the whole database in at most rM queries.

B. Analysis on the rM −N method

  • The rM−N method generates an N-bit Final Oblivious Key from rM Raw Oblivious Key bits, so its key entropy is at most rM.The paper states that this means the FOK is not strictly secure in theory.Source: B. Analysis on the rM −N method · p. 5
  • Alice can obtain the total database by at most rM queries using the rM−N dilution method.The analysis also notes that she may need fewer queries when she knows multiple key bits per query or selects a basis containing more known bits.Source: B. Analysis on the rM −N method · pp. 5, 7
  • For N=104 and k=6, Alice needs 53 queries at p=0.25 and 40 at p=0.29 to obtain the whole database.The figure caption reports these query counts for the two instances shown.Source: Figure 2 · p. 5
  • In the described matrix construction, each row of G(si) has k ones and M−k zeros, while shifts change the row order.The method represents the extended, shifted sub-keys through G(si) applied to the sub-key vector.Source: B. Analysis on the rM −N method · pp. 5–6
  • The Final Oblivious Key is determined by T basis bits, which Alice can use to calculate the remaining key bits and decrypt the database.Those T bits are sufficient because the corresponding vectors linearly express all rows of the extended-key matrix.Source: B. Analysis on the rM −N method · p. 6

IV. POST-PROCESSING OF THE OBLIVIOUS KEY WITH ERROR CORRECTION

This section addresses the missing error-correction step in QKD-based QPQ by combining correction with dilution. The combined method lowers final-key error under stated conditions, while shift-addition limits the extra key information a dishonest Alice can obtain.

IV. POST-PROCESSING OF THE OBLIVIOUS KEY WITH ERROR CORRECTION

  • Bob encodes four random bits with a [7,4,3] code and encrypts the codeword using seven ROK bits; Alice corrects it and takes its parity if she knows all seven bits.If she does not know all seven ROK bits, she labels the corresponding FOK bit unknown.Source: §IV · pp. 7–8
  • With N=10^5 and p=0.25, dishonest Alice knows 7055.66 FOK bits if she skips correction, versus 6.10 expected bits for an honest Alice.The code can let her infer a FOK bit when she correctly knows at least four of the seven ROK bits.Source: §IV · p. 8
  • Shift-addition across multiple middle keys reduces dishonest Alice’s known FOK bits without increasing failure probability, but lowers communication efficiency.In the N=10^5, k=7, p=0.25 simulation, g=6 gives nA=5, below the original method’s honest expectation of 6.10.Source: §IV · pp. 8–9
  • For e < 30%, the gkN−N method has visibly lower FOK error than the original kN−N method, at a sacrifice in failure probability and communication efficiency.The comparison is shown in Fig. 5.Source: §IV · p. 9, Figure 5 · p. 9
  • For scenarios beyond N=10^5, k=7, and p=0.25, the method’s error rates, privacy, failure probability, and g must be re-analyzed.The authors state that the method can be used in different scenarios with an appropriate error-correction code.Source: §IV · pp. 9–10

V. CONCLUSIONS

The paper presents QKD-based QPQ as a practical example of quantum cryptography, but its oblivious-key post-processing remains unclear and limits practicability. It studies both dilution and error correction.

V. CONCLUSIONS

  • QKD-based QPQ is presented as a practical example of quantum cryptography and a way to study cryptographic aims achievable via QKD.Source: §V · p. 10
  • Unclear post-processing of the oblivious key limits the practicability of QKD-based QPQ; the paper studies both dilution and error correction.Source: §V · p. 10
  • The dilution methods under discussion can significantly reduce communication complexity.Source: §V · p. 10
Loading 1406.0589v1…