Abstract

By adding a parameter θ in M. Jakobi et al’s protocol [Phys. Rev. A 83, 022301 (2011)], we present a flexible quantum-key-distribution-based protocol for quantum private queries. We show that, by adjusting the value of θ, 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 θ < π/4, which implies lower complexity of both quantum and classical communications. Furthermore, the users can choose a smaller θ to get better database security, or a larger θ to obtain a lower probability with which Bob can correctly guess the address of Alice’s query.

© 2012 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science, (Santa Fe, New Mexico, 1994), 124–134.
    [CrossRef]
  2. L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing, (New York, 1996), 212–219.
  3. C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing, (Bangalore, 1984), 175–179.
  4. N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
    [CrossRef]
  5. B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
    [CrossRef]
  6. Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
    [CrossRef]
  7. H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A56, 1154–1162 (1997).
    [CrossRef]
  8. V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
    [CrossRef] [PubMed]
  9. V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
    [CrossRef]
  10. F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
    [CrossRef]
  11. L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A84, 022313 (2011).
    [CrossRef]
  12. M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
    [CrossRef]
  13. V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
    [CrossRef] [PubMed]
  14. C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett.68, 3121–3124 (1992).
    [CrossRef] [PubMed]
  15. P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.
  16. U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005).
    [CrossRef]
  17. C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.
  18. C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

2011

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A84, 022313 (2011).
[CrossRef]

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

2010

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
[CrossRef]

2009

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

2008

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
[CrossRef] [PubMed]

2005

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005).
[CrossRef]

2004

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

2002

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

2000

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

1998

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

1997

H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A56, 1154–1162 (1997).
[CrossRef]

1992

C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett.68, 3121–3124 (1992).
[CrossRef] [PubMed]

Acín, A.

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

Bancal, J.D.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

Bennett, C. H.

C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett.68, 3121–3124 (1992).
[CrossRef] [PubMed]

Bennett, C.H.

C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing, (Bangalore, 1984), 175–179.

Bergou, J. A.

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005).
[CrossRef]

Branciard, C.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

Brassard, G.

C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing, (Bangalore, 1984), 175–179.

Chor, B.

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

Fuchs, C. A.

C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.

Gertner, Y.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

Giovannetti, V.

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
[CrossRef]

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
[CrossRef] [PubMed]

Gisin, N.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

Goldreich, E.

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

Grover, L. K.

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing, (New York, 1996), 212–219.

Helstrom, C. W.

C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

Herzog, U.

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005).
[CrossRef]

Ishai, Y.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

Jakobi, M.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

Kushilevitz, E.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

Kushilevitz, O.

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

Lloyd, S.

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
[CrossRef]

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
[CrossRef] [PubMed]

Lo, H. K.

H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A56, 1154–1162 (1997).
[CrossRef]

Maccone, L.

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
[CrossRef]

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
[CrossRef] [PubMed]

Malkin, T.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

Martini, F. D.

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

Nagali, E.

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

Olejnik, L.

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A84, 022313 (2011).
[CrossRef]

Raynal, P.

P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.

Ribordy, G.

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

Sansoni, L.

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

Scarani, V.

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

Sciarrino, F.

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

Shor, P. W.

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science, (Santa Fe, New Mexico, 1994), 124–134.
[CrossRef]

Simon, C.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

Sudan, M.

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

Tittel, W.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

Walenta, N.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

Zbinden, H.

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

IEEE T. Inform. Theory

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries: securety analysis,” IEEE T. Inform. Theory56, 3465–3477 (2010).
[CrossRef]

J. ACM

B. Chor, E. Goldreich, O. Kushilevitz, and M. Sudan, “Private Information Retrieval,” J. ACM45, 965–981 (1998).
[CrossRef]

J. Comput. Syst. Sci.

Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting data privacy in private information retrieval schemes,” J. Comput. Syst. Sci.60, 592–629 (2000).
[CrossRef]

Phys. Rev. A

H. K. Lo, “Insecurity of quantum secure computations,” Phys. Rev. A56, 1154–1162 (1997).
[CrossRef]

F. D. Martini, V. Giovannetti, S. Lloyd, L. Maccone, E. Nagali, L. Sansoni, and F. Sciarrino, “Experimental quantum private queries with linear optics,” Phys. Rev. A80, 010302 (2009).
[CrossRef]

L. Olejnik, “Secure quantum private information retrieval using phase-encoded queries,” Phys. Rev. A84, 022313 (2011).
[CrossRef]

M. Jakobi, C. Simon, N. Gisin, J.D. Bancal, C. Branciard, N. Walenta, and H. Zbinden, “Practical private database queries based on a quantum-key-distribution protocol,” Phys. Rev. A83, 022301 (2011).
[CrossRef]

U. Herzog and J. A. Bergou, “Optimum unambiguous discrimination of two mixed quantum states,” Phys. Rev. A71, 050301 (2005).
[CrossRef]

Phys. Rev. Lett.

V. Scarani, A. Acín, G. Ribordy, and N. Gisin, “Quantum cryptography protocols robust against photon number splitting attacks for weak laser pulse implementations,” Phys. Rev. Lett.92, 057901 (2004).
[CrossRef] [PubMed]

C. H. Bennett, “Quantum cryptography using any two nonorthogonal states,” Phys. Rev. Lett.68, 3121–3124 (1992).
[CrossRef] [PubMed]

V. Giovannetti, S. Lloyd, and L. Maccone, “Quantum Private Queries,” Phys. Rev. Lett.100, 230502 (2008).
[CrossRef] [PubMed]

Rev. Mod. Phys.

N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, “Quantum cryptography,” Rev. Mod. Phys.74, 145–195 (2002).
[CrossRef]

Other

C. A. Fuchs, “Distinguishability and Accessible Information in Quantum Theory,” e-print arXiv:quant-ph/9601020.

C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, New York, 1976).

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on the Foundations of Computer Science, (Santa Fe, New Mexico, 1994), 124–134.
[CrossRef]

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in 28th Annual ACM Symposium on Theory of Computing, (New York, 1996), 212–219.

C.H. Bennett and G. Brassard, “Quantum cryptography: public-key distribution and coin tossing,” in IEEE Int. Conf. on Computers, Systems, and Signal Processing, (Bangalore, 1984), 175–179.

P. Raynal, “Unambiguous State Discrimination of two density matrices in Quantum Information Theory,” e-print arXiv:quant-ph/0611133.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1
Fig. 1

How to achieve n̄ = 3 for any N. Similar result also exists when we pursue n̄ other than 3.

Fig. 2
Fig. 2

Any n̄ ≪ N can be achieved for N = 10000.

Fig. 3
Fig. 3

Comparison between Alice’s success probability by USD measurement and projective one on a qubit. The dashed line represents the result for USD measurement and the solid line is for projective one.

Fig. 4
Fig. 4

Alice’s success probabilities to obtain the final key bits by joint USD measurement for different θ. Among them the line denoted as θ = π/4 is the result of J-protocol. It can be seen that when θ is small, Alice will get less bits in the final key, which implies a higher security degree for the database under this kind of attack.

Fig. 5
Fig. 5

The relation between the probability pc, with which Alice gets conclusive result, and the value of θ under Bob’s attack. The dashed line denotes the result in J-protocol (i.e. θ = π/4).

Tables (4)

Tables Icon

Table 1 Example of possible choice of k and the values P0 and n̄ for different database sizes N (p = 0.15).

Tables Icon

Table 2 For different N, θ can be selected so that k = 1 and n̄ = 3.

Tables Icon

Table 3 For different N, θ can be selected so that k = 1 and n̄ = 5.

Tables Icon

Table 4 For different N, θ (> 0.2) can be selected so that n̄ = 3 and P0 ≈ 0.05.

Equations (2)

Equations on this page are rendered with MathJax. Learn more.

| 0 = cos θ | 0 + sin θ | 1 , | 1 = sin θ | 0 cos θ | 1 ,
| 0 = cos ( θ / 2 ) | 0 + sin ( θ / 2 ) | 1 , | 1 = sin ( θ / 2 ) | 0 cos ( θ / 2 ) | 1 .

Metrics