nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

New Security Notions and Feasibility Results for Authentication of Quantum Data

verfasst von : Sumegha Garg, Henry Yuen, Mark Zhandry

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We give a new class of security definitions for authentication in the quantum setting. These definitions capture and strengthen existing definitions of security against quantum adversaries for both classical message authentication codes (MACs) as well as full quantum state authentication schemes. The main feature of our definitions is that they precisely characterize the effective behavior of any adversary when the authentication protocol accepts, including correlations with the key. Our definitions readily yield a host of desirable properties and interesting consequences; for example, our security definition for full quantum state authentication implies that the entire secret key can be re-used if the authentication protocol succeeds.

Next, we present several protocols satisfying our security definitions. We show that the classical Wegman-Carter authentication scheme with 3-universal hashing is secure against superposition attacks, as well as adversaries with quantum side information. We then present conceptually simple constructions of full quantum state authentication.

Finally, we prove a lifting theorem which shows that, as long as a protocol can securely authenticate the maximally entangled state, it can securely authenticate any state, even those that are entangled with the adversary. Thus, this shows that protocols satisfying a fairly weak form of authentication security automatically satisfy a stronger notion of security (in particular, the definition of Dupuis et al. (2012)).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Quantum Non-malleability and Authentication

Nächstes Kapitel Time-Memory Tradeoff Attacks on the MTP Proof-of-Work Scheme

One motivation for studying superposition attacks comes from the “Frozen Smart-Card” example [GHS15]: real-world classical authentication systems are frequently implemented on small electronic devices such as RFID tags or a smart-cards. A determined and sophisticated attacker in possession of such a smart-card could try to perform a quantum “side-channel attack” on it: he places the device in a very low temperature environment, and attempts to query the device in quantum superposition. One would like to guarantee that even then the attacker is unable to, say, extract the secret key.

By contrast, in the classical setting, message authentication does not imply message encryption.

One limitation of our definition is that we consider the signature registers as being initialized by the signer. Boneh and Zhandry, in contrast, allow the registers to be initialized by the adversary, with the signature being XORed into the registers.

The work of Dåmgard et al. [DPS05] argue that the key can be recycled entirely when authenticating classical messages, but their protocol does not appear to extend to handling quantum messages.

The observation that quantum authentication implies a form of QKD is due to Charlie Bennett and also observed by Gottesman [Got02].

A seasoned veteran of quantum information may notice that this departs slightly from the convention in quantum information theory where physically realizable quantum operations are CPTP maps. Here the difference is that we consider maps that can possibly decrease the trace of an operator, which corresponds to post-selection.

One can also discuss schemes where the correctness requirements hold approximately (e.g., the state \({\mathsf {Ver}}_k({\mathsf {Auth}}_k(\rho ))\) is within trace distance \(\delta \) of \(\rho \otimes |\mathrm {ACC}\rangle \langle \mathrm {ACC}|\)); using this correctness condition does not significantly affect the discussion in this paper.

See Sect. 9 for a formal statement of the [DNS12] definition.

https://arxiv.org/abs/1607.07759.

However, it is not an 8-design.

For simplicitly let us think of \(\mathcal {M}\) as \((\mathbb {C}^2)^{\otimes n}\) (i.e., n qubits). Then the Pauli group consists of all operators of the form \(X^p Z^q\), where \(p,q \in \{0,1\}^n\). Here, the operator \(X^p\) is defined to be the tensor product of \(X_j^{p_j}\), where \(X_j\) is the X Pauli operator acting on the j’th qubit. \(Z^q\) is defined similarly.

https://arxiv.org/abs/1607.07759.

[ABE10]

Aharonov, D., Ben-Or, M., Eban, E.: Interactive proofs for quantum computations. In: Proceedings of Innovations in Computer Science. Tsinghua University Press (2010)

[ABW09]

Ambainis, A., Bouda, J., Winter, A.: Nonmalleable encryption of quantum information. J. Math. Phys. 50(4), 042106 (2009)MathSciNetCrossRefMATH

[AM16]

Alagic, G., Majenz, C.: Quantum non-malleability and authentication (2016). arXiv preprint arXiv:1610.04214

[BCG+02]

Barnum, H., Crépeau, C., Gottesman, D., Smith, A., Tapp, A.: Authentication of quantum messages. In: 2002 The Proceedings of the 43rd Annual IEEE Foundations of Computer Science, pp. 449–458. IEEE (2002)

[BCG+06]

Ben-Or, M., Crépeau, C., Gottesman, D., Hassidim, A., Smith, A.: Secure multiparty quantum computation with (only) a strict honest majority. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 249–260. IEEE (2006)

[BDF+11]

Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25385-0_3 CrossRef

[Bee97]

Beenakker, C.W.J.: Random-matrix theory of quantum transport. Rev. Mod. Phys. 69(3), 731 (1997)MathSciNetCrossRef

[BGS13]

Broadbent, A., Gutoski, G., Stebila, D.: Quantum one-time programs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 344–360. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_20 CrossRef

[BHH12]

Brandao, F.G.S.L., Harrow, A.W., Horodecki, M.: Local random quantum circuits are approximate polynomial-designs (2012). arXiv preprint arXiv:1208.0692

[BHL+05]

Ben-Or, M., Horodecki, M., Leung, D.W., Mayers, D., Oppenheim, J.: The universal composable security of quantum key distribution. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 386–406. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30576-7_21 CrossRef

[BW16]

Broadbent, A., Wainewright, E.: Efficient simulation for quantum message authentication (2016). arXiv preprint arXiv:1607.03075

[BZ13a]

Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 592–608. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38348-9_35 CrossRef

[BZ13b]

Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 361–379. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_21 CrossRef

[DFNS13]

Damgård, I., Funder, J., Nielsen, J.B., Salvail, L.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) ICITS 2013. LNCS, vol. 8317, pp. 142–161. Springer, Cham (2014). doi:10.1007/978-3-319-04268-8_9 CrossRef

[DNS12]

Dupuis, F., Nielsen, J.B., Salvail, L.: Actively secure two-party evaluation of any quantum operation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 794–811. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_46 CrossRef

[DPS05]

Damgård, I., Pedersen, T.B., Salvail, L.: A quantum cipher with near optimal key-recycling. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 494–510. Springer, Heidelberg (2005). doi:10.1007/11535218_30 CrossRef

[FS16]

Fehr, S., Salvail, L.: Quantum authentication and encryption with key recycling (2016). arXiv preprint arXiv:1610.05614

[GHS15]

Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world (2015). arXiv preprint arXiv:1504.05255

[Got02]

Gottesman, D.: Uncloneable encryption (2002). arXiv preprint arXiv:quant-ph/0210062

[GYZ16]

Garg, S., Yuen, H., Zhandry, M.: New security notions and feasibility results for authentication of quantum data (2016). arXiv preprint arXiv:1607.07759

[HLM16]

Hayden, P., Leung, D.W., Mayers, D.: The universal composable security of quantum message authentication with key recyling (2016). arXiv preprint arXiv:1610.09434

[KLLNP16]

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding (2016). arXiv preprint arXiv:1602.05973

[Low09]

Low, R.A.: Large deviation bounds for k-designs. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 465, pp. 3289–3308. The Royal Society (2009)

[MS09]

Milman, V.D., Schechtman, G.: Asymptotic Theory of Finite Dimensional Normed Spaces: Isoperimetric Inequalities in Riemannian Manifolds. Springer, Heidelberg (2009)MATH

[NC10]

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)CrossRefMATH

[OH05]

Oppenheim, J., Horodecki, M.: How to reuse a one-time pad and other notes on authentication, encryption, and protection of quantum information. Phys. Rev. A 72(4), 042309 (2005)CrossRef

[Por17]

Portmann, C.: Quantum authentication with key recycling. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 339–368. Springer, Cham (2017). doi:10.1007/978-3-319-56617-7_12 CrossRef

[Unr10]

Unruh, D.: Universally composable quantum multi-party computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 486–505. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_25 CrossRef

[WC81]

Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981)MathSciNetCrossRefMATH

[Web15]

Webb, Z.: The clifford group forms a unitary 3-design (2015). arXiv preprint arXiv:1510.02769

[Zha12]

Zhandry, M.: How to construct quantum random functions. In: Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science (FOCS) (2012)

[Zhu15]

Zhu, H.: Multiqubit clifford groups are unitary 3-designs (2015). arXiv preprint arXiv:1510.02619

Titel: New Security Notions and Feasibility Results for Authentication of Quantum Data
verfasst von: Sumegha Garg
Henry Yuen
Mark Zhandry
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2017
Print ISBN: 978-3-319-63714-3

Electronic ISBN: 978-3-319-63715-0

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-63715-0_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"