Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 8/2020

01.08.2020

A quantum related-key attack based on the Bernstein–Vazirani algorithm

Erschienen in: Quantum Information Processing | Ausgabe 8/2020

Einloggen

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

search-config
loading …

Abstract

Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting and propose a specific related-key attack, which can recover the key of block ciphers efficiently as long as the attacked block ciphers satisfy certain condition. The attack algorithm employs the Bernstein–Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. We give a condition under which the attack will succeed and prove that any block cipher either satisfies the condition or has a distinguishing attack. As a specific example of its application, we use the attack algorithm to extract the private key of the Even–Mansour cipher. The results of this study show the power of related-key attack when combined with quantum algorithms and provide guidance for the design of quantum-secure block ciphers.
Vorheriger Artikel Quantum image encryption algorithm based on bit-plane permutation and sine logistic map
Nächster Artikel Analysis of efficient quantum multi-proxy signature

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
Literatur
1.
Shor, P. W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of Foundations of Computer Science, Santa Fe, NM, pp. 124–134 (1994)
2.
NIST: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016)
3.
Grover, L. K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), Philadelphia, PA, pp. 212–219 (1996)
4.
5.
Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT 2010), pp. 2682–2685. Austin, TX, USA (2010)
6.
Luby, M., Rackoff, C.: How to construct pseudo-random permutations from pseudo-random functions. In: Williams, H.C. (ed.) Advances in Cryptology-CRYPTO ’85 Proceedings LNCS, vol. 218218, pp. 447–447. Springer, Heidelberg (1985)
7.
Kuwakado, H., Morii, M.: Security on the quantum-type even-mansour cipher. In: 2012 International Symposium on Information Theory and its Applications (ISITA 2012), pp. 312–316. Honolulu, HI (2012)
8.
Santoli, T., Schaffner, C.: Using simon’s algorithm to attack symmetric-key cryptographic primitives. Quantum Inf. Comput. 17(1&2), 65–78 (2017)MathSciNet
9.
Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016)CrossRef
10.
Dong, X., Wang, X.: Quantum key-recovery attack on feistel structures. Sci. China Inf. Sci. 61(10), 102501 (2018)CrossRef
11.
Dong, X., Wang, X.: Quantum cryptanalysis on some generalized Feistel schemes. Sci. China Inf. Sci. 62(2), 22501 (2019)MathSciNetCrossRef
12.
Zhou, Q., Lu, S., Zhang, Z., Sun, J.: Quantum differential cryptanalysis. Quantum Inf. Process. 14(6), 2101–2109 (2015)ADSCrossRef
13.
Kaplan, M., Leurent, G., Leverrier, A., & Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. In: FSE 2017, IACR Transactions on Symmetric Cryptology, 2016(1), pp. 71–94 (2017)
14.
15.
Xie, H., Yang, L.: Using Bernstein-Vazirani algorithm to attack block ciphers. Designs, Codes and Cryptography 87(5), 1161–1182 (2019)
16.
Boneh, D., Özgür, D., Fischlin, M., et al.: Random oracles in a quantum world. Advances in Cryptology–ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011)CrossRef
17.
Boneh, D., Zhandry, M.: Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology-CRYPTO 2013, LNCS, vol. 8043, pp. 361–379. Springer, Heidelberg (2013)CrossRef
18.
Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology-CRYPTO 2016, LNCS, vol. 9816, pp. 60–89. Springer, Heidelberg (2016)CrossRef
19.
Goldreich, O.: Foundations of Cryptography, Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)CrossRef
20.
Bellare, M.; Desai, A.; Jokipii, E.; Rogaway, P.: A concrete security treatment of symmetric encryption. In: Proceedings 38th Annual Symposium on Foundations of Computer Science (FOCS’97), pp. 394–403 (1997)
21.
Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptol. 7(4), 229–246 (1994)CrossRef
22.
Knudsen, L.R.: Cryptanalysis of LOKI91. In: Seberry, J., Zheng, Y. (eds.) Advances in Cryptology-AUSCRYPT ’92 LNCS, vol. 718, pp. 22–35. Springer, Heidelberg (1993)CrossRef
23.
Andreeva, E., Bogdanov, A., Mennink, B.: Towards Understanding the Known-Key Security of Block Ciphers. In: Moriai S. (eds.) Fast Software Encryption. FSE 2013. LNCS, vol 8424, pp. 348–366 Springer, Heidelberg (2014)
24.
Alagic, G., Broadbent, A., Fefferman, B., et al.: Computational Security of Quantum Encryption. In: Nascimento, A., Barreto, P. (eds.) Information Theoretic Security, ICITS 2016. LNCS, vol. 10015, pp. 47–71. Springer, Cham (2016)
25.
Roetteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015)CrossRef
26.
Winternitz, R., Hellman, M.: Chosen-key attacks on a block cipher. Cryptologia 11(1), 16–20 (1987)CrossRef
27.
Ferguson, N., Kelsey, J., Lucks, S., et al.: Improved cryptanalysis of Rijndael. In: Goos, G., Hartmanis, J., van Leeuwen, J., Schneier, B. (eds.) Fast Software Encryption. FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer, Heidelberg (2001)
28.
Bellare, M., Kohno, T.: A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications. In: Biham, E. (ed.) Advances in Cryptology-EUROCRYPT 2003, LNCS, vol. 2656, pp. 491–506. Springer, Heidelberg (2003)CrossRef
29.
Albrecht, M.R., Farshim, P., Paterson, K.G., et al.: On Cipher-Dependent Related-Key Attacks in the Ideal-Cipher Model. In: Joux, A. (ed.) Fast Software Encryption, FSE 2011. LNCS, vol. 6733, pp. 128–145. Springer, Heidelberg (2011)
30.
Biham, E., Dunkelman, O., Keller, N.: A Related-Key Rectangle Attack on the Full KASUMI. In: Roy, B. (ed.) Advances in Cryptology-ASIACRYPT 2005, LNCS, vol. 3788, pp. 443–461. Springer, Heidelberg (2005)CrossRef
31.
Dunkelman, O., Keller, N., Shamir, A.: A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony. In: Rabin, T. (ed.) Advances in Cryptology-CRYPTO 2010, LNCS, vol. 6223, pp. 393–410. Springer, Heidelberg (2010)CrossRef
32.
Fluhrer, S., Mantin, I., Shamir, A.: Weaknesses in the Key Scheduling Algorithm of RC4. In: Vaudenay, S., Youssef, A.M. (eds.) Selected Areas in Cryptography, SAC 2001. LNCS, vol. 2259, pp. 1–24. Springer, Heidelberg (2001)MATH
33.
Mantin, I.: A Practical Attack on the Fixed RC4 in the WEP Mode. In: Roy, B. (ed.) Advances in Cryptology-ASIACRYPT 2005, LNCS, vol. 3788, pp. 395–411. Springer, Heidelberg (2005)CrossRef
34.
Hosoyamada, A., Aoki, K.: On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers. In: Obana, S., Chida, K. (eds.) Advances in Information and Computer Security, IWSEC 2017. LNCS, vol. 10418, pp. 3–18. Springer, Cham (2017)
35.
Cirac, J.I., Zoller, P.: Quantum computations with cold trapped ions. Phys. Rev. Lett. 74(20), 4091–4094 (1995)ADSCrossRef
36.
Nakamura, Y., Pashkin, Y.A., Tsai, J.S.: Coherent control of macroscopic quantum states in a single-Cooper-pair box. Nature 398(6730), 786–788 (1999)ADSCrossRef
37.
Knill, E., Laflamme, R., Milburn, G.J.: A scheme for efficient quantum computation with linear optics. Nature 409(6816), 46–52 (2001)ADSCrossRef
38.
Gershenfeld, N.A., Chuang, I.L.: Bulk spin-resonance quantum computation. Science 275(5298), 350–356 (1997)MathSciNetCrossRef
39.
Monz, T., Nigg, D., Martinez, E.A., et al.: Realization of a scalable Shor algorithm. Scienc 351(6277), 1068–1070 (2016)ADSMathSciNetCrossRef
40.
Lucero, E., Barends, R., Chen, Y., et al.: Computing prime factors with a Josephson phase qubit quantum processor. Nat. Phys. 8(10), 719–723 (2012)CrossRef
41.
Martin-Lopez, E., Laing, A., Lawson, T., et al.: Experimental realization of Shor’s quantum factoring algorithm using qubit recycling. Nat. Photonics 6(11), 773–776 (2012) ADSCrossRef
42.
Politi, J.C., Matthews, J.L., O’brien, J.L.: Shor’s quantum factoring algorithm on a photonic chip. Science 325(5945), 1221 (2009)ADSMathSciNetCrossRef
43.
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2000)MATH
44.
Damgård, I., Funder, J., Nielsen, J.B., et al.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) Information Theoretic Security, ICITS 2013. LNCS, vol. 8317, pp. 142–161. Springer, Cham (2013)
45.
O’connor, L., Klapper, A.: Algebraic nonlinearity and its applications to cryptography. J. Cryptol. 7(4), 213–227 (1994)MathSciNetCrossRef
46.
47.
Li, H., Yang, L.: A quantum algorithm to approximate the linear structures of Boolean functions. Math. Struct. Comput. 28(1), 1–13 (2018)ADSMathSciNetCrossRef
48.
Tao, B., Wu, H.: Improving the biclique cryptanalysis of AES. In: Australasian Conference on Information Security and Privacy. Springer, Cham, pp. 39–56 (2015)
49.
Junod, P.: On the complexity of Matsui’s attack. In: International Workshop on Selected Areas in Cryptography. Springer, Berlin, Heidelberg. pp. 199–211 (2001)
50.
Chen, H., Wang, X.: Improved linear hull attack on round-reduced Simon with dynamic key-guessing techniques. In: International Conference on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 428–449 (2016)
51.
Faghihi Sereshgi, M.H., Dakhilalian, M., Shakiba, M.: Biclique cryptanalysis of MIBS-80 and PRESENT-80 block ciphers. Secur. Commun. Netw. 9(1), 27–33 (2015)CrossRef
52.
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997)MathSciNetCrossRef
Metadaten
Titel
A quantum related-key attack based on the Bernstein–Vazirani algorithm
Publikationsdatum
01.08.2020
Erschienen in
Quantum Information Processing / Ausgabe 8/2020
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-020-02741-2

Weitere Artikel der Ausgabe 8/2020

Quantum Information Processing 8/2020 Zur Ausgabe

OriginalPaper

Quantum discord based on linear entropy and thermal negativity of qutrit–qubit mixed spin chain under the influence of external magnetic field

OriginalPaper

Quantum bicyclic hyperbolic codes

OriginalPaper

Preparation of entangled W states with cat-state qubits in circuit QED

OriginalPaper

Quantum witness of a damped and driven qubit by sequential intermediate measurements with uniform and nonuniform time intervals

OriginalPaper

High-precision parameter estimation and the Zeno–anti-Zeno crossover in an atom–cavity-optomechanical system

OriginalPaper

Quantum transport on large-scale sparse regular networks by using continuous-time quantum walk

Neuer Inhalt

    Bildnachweise