Abstract
We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings.
Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded-quantum-storage model according to new strong security definitions.
As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model).
Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Series in Discrete Mathematics and Optimization. Wiley, Chichester (2000)
Azuma, K.: Weighted sums of certain dependent random variables. Tôhoku Mathematical Journal 19, 357–367 (1967)
Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, pp. 175–179. IEEE Computer Society Press, Los Alamitos (1984)
Bennett, C.H., Brassard, G., Crépeau, C., Maurer, U.M.: Generalized privacy amplification. IEEE Transactions on Information Theory 41, 1915–1923 (1995)
Bennett, C.H., Brassard, G., Robert, J.-M.: Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988)
Bialynicki-Birula, I.: Formulation of the uncertainty relations in terms of the Rényi entropies. Physical Review A 74, 52101 (2006)
Bialynicki-Birula, I., Mycielski, J.: Uncertainty relations for information entropy. Communications in Mathematical Physics 129(44) (1975)
Cachin, C.: Smooth entropy and Rényi entropy. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 193–208. Springer, Heidelberg (1997)
Carter, J.L., Wegman, M.N.: Universal classes of hash functions. In: STOC. 9th Annual ACM Symposium on Theory of Computing, pp. 106–112. ACM Press, New York (1977)
Crépeau, C., Savvides, G., Schaffner, C., Wullschleger, J.: Information-theoretic conditions for two-party secure function evaluation. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 538–554. Springer, Heidelberg (2006)
Csiszár, I., Körner, J.: Broadcast channels with confidential messages. IEEE Transactions on Information Theory 24(3), 339–348 (1978)
Damgård, I.B., Fehr, S., Renner, R., Salvail, L., Schaffner, C.: A tight high-order entropic quantum uncertainty relation with applications (2007), Available at http://arxiv.org/abs/quant-ph/0612014
Damgård, I.B., Fehr, S., Salvail, L., Schaffner, C.: Cryptography in the bounded quantum-storage model. In: FOCS. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 449–458. IEEE Computer Society Press, Los Alamitos (2005)
Damgård, I.B., Fehr, S., Salvail, L., Schaffner, C.: Oblivious transfer and linear functions. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 427–444. Springer, Heidelberg (2006)
Damgård, I.B., Pedersen, T.B., Salvail, L.: On the key-uncertainty of quantum ciphers and the computational security of one-way quantum transmission. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 91–108. Springer, Heidelberg (2004)
Deutsch, D.: Uncertainty in quantum measurements. Physical Review Letters 50(9), 631–633 (1983)
Dumais, P., Mayers, D., Salvail, L.: Perfectly concealing quantum bit commitment from any quantum one-way permutation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 300–315. Springer, Heidelberg (2000)
Fuchs, C.A., Gisin, N., Griffiths, R.B., Niu, C.-S., Peres, A.: Optimal eavesdropping in quantum cryptography. Physical Review A 56, 1163–1172 (1997)
Hilgevood, J., Uffink, J.: The mathematical expression of the uncertainty principle. In: Microphysical Reality and Quantum Description, Kluwer Academic Publishers, Dordrecht (1988)
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: STOC. 21st Annual ACM Symposium on Theory of Computing, pp. 12–24. ACM Press, New York (1989)
Kraus, K.: Complementary observables and uncertainty relations. Physical Review D 35(10), 3070–3075 (1987)
Larsen, U.: Superspace geometry: the exact uncertainty relationship between complementary aspects. Journal of Physics A: Mathematical and General 23(7), 1041–1061 (1990)
Lütkenhaus, N.: Security against individual attacks for realistic quantum key distribution. Physical Review A 61, 52304 (2000)
Maassen, H., Uffink, J.B.M.: Generalized entropic uncertainty relations. Physical Review Letters 60(12), 1103–1106 (1988)
Renner, R.: Security of Quantum Key Distribution. PhD thesis, ETH Zürich (2005), http://arxiv.org/abs/quant-ph/0512258
Renner, R., Gisin, N., Kraus, B.: An information-theoretic security proof for QKD protocols. Phys. Rev. A. 72(012332) (2005)
Renner, R., König, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 407–425. Springer, Heidelberg (2005)
Renner, R., Wolf, S.: Simple and tight bounds for information reconciliation and privacy amplification. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 199–216. Springer, Heidelberg (2005)
Sánchez-Ruiz, J.: Entropic uncertainty and certainty relations for complementary observables. Physics Letters A 173(3), 233–239 (1993)
Sánchez-Ruiz, J.: Improved bounds in the entropic uncertainty and certainty relations for complementary observables. Physics Letters A 201(2–3), 125–131 (1995)
Wegman, M.N., Carter, J.L.: New classes and applications of hash functions. In: FOCS. 20th Annual IEEE Symposium on Foundations of Computer Science, pp. 175–182. IEEE Computer Society Press, Los Alamitos (1979)
Wiesner, S.: Conjugate coding. SIGACT News 15(1), 78–88 (1970)
Wullschleger, J.: Oblivious-Transfer amplification. In: Advances in Cryptology—EUROCRYPT ’07. LNCS, Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Damgård, I.B., Fehr, S., Renner, R., Salvail, L., Schaffner, C. (2007). A Tight High-Order Entropic Quantum Uncertainty Relation with Applications. In: Menezes, A. (eds) Advances in Cryptology - CRYPTO 2007. CRYPTO 2007. Lecture Notes in Computer Science, vol 4622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74143-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-74143-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74142-8
Online ISBN: 978-3-540-74143-5
eBook Packages: Computer ScienceComputer Science (R0)