Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A New Rank Metric Codes Based Encryption Scheme Read chapter Read first chapter

2017 | OriginalPaper | Chapter

XOR of PRPs in a Quantum World

Authors : Bart Mennink, Alan Szepieniec

Published in: Post-Quantum Cryptography

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the classical world, the XOR of pseudorandom permutations \(E_{k_1}\oplus \cdots \oplus E_{k_r}\) for \(r\ge 2\) is a well-established way to design a pseudorandom function with “optimal” security: security up to approximately \(\min \{|K|,|X|\}\) queries, where K and X are the key and state space of the block cipher E. We investigate security of this construction against adversaries who have access to quantum computers. We first present a key recovery attack in \(|K|^{r/(r+1)}\) complexity. The attack relies on a clever application of a claw-finding algorithm and testifies of a significant gap with the classical setting where 2 pseudorandom permutations already yield optimal security. Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to \(\min \{|K|^{1/2}/r,|X|\}\) queries. The analysis relies on a generic characterization of classical and quantum distinguishers and a universal transformation of classical security proofs to the quantum setting that is of general interest.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers
next chapter Transitioning to a Quantum-Resistant Public Key Infrastructure
Footnotes
1
This list omits research on the XOR of public permutations [37, 39].
 
2
An earlier, yet unrelated and less profound, application of claw finding to cascaded encryption appeared by Kaplan [27].
 
3
The lifting does not apply to ideal-model proofs, such as the ones used for sponge functions [3, 40], Even-Mansour constructions [11, 14], and some tweakable block cipher designs [17, 38], which is because in ideal-model proofs the adversary has quantum query access to idealized primitives.
 
4
Tani [52] uses a slightly different naming: \((p,q)\text {-}\mathsf {subset}(M,N)\).
 
5
Throughout this work, we ignore a third measurement, memory, and assume that the distinguisher has sufficient memory available at all times.
 
6
The attack can be simplified by putting \(z_1\Vert \cdots \Vert z_\tau \) inside relation R and considering \(p=r\) and \(q=0\). We follow current approach for intuitiveness.
 
Literature
1.
Abed, F., Forler, C., List, E., Lucks, S., Wenzel, J.: RIV for robust authenticated encryption. In: Peyrin [45], pp. 23–42
2.
Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 44–63. Springer, Cham (2016). doi:10.​1007/​978-3-319-29360-8_​4 CrossRef
3.
Andreeva, E., Bilgin, B., Bogdanov, A., Luykx, A., Mennink, B., Mouha, N., Yasuda, K.: APE: authenticated permutation-based encryption for lightweight cryptography. In: Cid and Rechberger [15], pp. 168–186
4.
Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K.: Parallelizable and authenticated online ciphers. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 424–443. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-42033-7_​22 CrossRef
5.
Andreeva, E., Daemen, J., Mennink, B., Van Assche, G.: Security of keyed sponge constructions using a modular proof approach. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 364–384. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48116-5_​18 CrossRef
6.
Bellare, M., Impagliazzo, R.: A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. Cryptology ePrint Archive, Report 1999/024 (1999)
7.
Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994). doi:10.​1007/​3-540-48658-5_​32
8.
Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). doi:10.​1007/​11761679_​25 CrossRef
9.
Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post-Quantum Cryptography. Springer Science & Business Media, Heidelberg (2009)MATH
10.
Bhaumik, R., Nandi, M.: OleF: an inverse-free online cipher. IACR Trans. Symmetric Cryptol. 1(2), 30–51 (2016)
11.
Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-alternating ciphers in a provable setting: encryption using a small number of public permutations. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 45–62. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​5 CrossRef
12.
Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer, Heidelberg (1998). doi:10.​1007/​BFb0054319 CrossRef
13.
Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324–1330 (2005)MathSciNetCrossRefMATH
14.
Chen, S., Steinberger, J.P.: Tight security bounds for key-alternating ciphers. In: Nguyen and Oswald [42], pp. 327–350
15.
Cid, C., Rechberger, C. (eds.): FSE 2014. LNCS, vol. 8540. Springer, Heidelberg (2015)
16.
Cogliati, B., Lampe, R., Patarin, J.: The indistinguishability of the XOR of \(k\) permutations. In: Cid and Rechberger [15], pp. 285–302
17.
18.
Cogliati, B., Seurin, Y.: EWCDM: an efficient, beyond-birthday secure, nonce-misuse resistant MAC. In: Robshaw and Katz [48], pp. 121–149
19.
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, 22–24 May 1996, pp. 212–219. ACM (1996)
20.
Hall, C., Wagner, D., Kelsey, J., Schneier, B.: Building PRFs from PRPs. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 370–389. Springer, Heidelberg (1998). doi:10.​1007/​BFb0055742 CrossRef
21.
22.
Hoang, V.T., Krovetz, T., Rogaway, P.: Robust authenticated-encryption AEZ and the problem that it solves. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 15–44. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​2
23.
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). doi:10.​1007/​0-387-34799-2_​2 CrossRef
24.
Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (2006). doi:10.​1007/​11799313_​20 CrossRef
25.
Iwata, T., Mennink, B., Vizr, D.: CENC is optimally secure. Cryptology ePrint Archive, Report 2016/1087 (2016)
26.
Iwata, T., Minematsu, K., Guo, J., Morioka, S.: CLOC: authenticated encryption for short input. In: Cid and Rechberger [15], pp. 149–167
27.
Kaplan, M.: Quantum attacks against iterated block ciphers. CoRR abs/1410.1434 (2014)
28.
Kaplan, M., 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). doi:10.​1007/​978-3-662-53008-5_​8 CrossRef
29.
30.
Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: Proceedings of IEEE International Symposium on Information Theory, ISIT 2010, 13–18 June 2010, Austin, Texas, USA, pp. 2682–2685. IEEE (2010)
31.
Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, 28–31 October 2012, pp. 312–316. IEEE (2012)
32.
Landecker, W., Shrimpton, T., Terashima, R.S.: Tweakable blockciphers with beyond birthday-bound security. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 14–30. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-32009-5_​2 CrossRef
33.
34.
Luykx, A., Preneel, B., Tischhauser, E., Yasuda, K.: A MAC mode for lightweight block ciphers. In: Peyrin [45], pp. 43–59
35.
36.
Malozemoff, A.J., Katz, J., Green, M.D.: Automated analysis and synthesis of block-cipher modes of operation. In: IEEE 27th Computer Security Foundations Symposium, CSF 2014, Vienna, Austria, 19–22 July 2014, pp. 140–152. IEEE Computer Society (2014)
37.
Mandal, A., Patarin, J., Nachef, V.: Indifferentiability beyond the birthday bound for the XOR of two public random permutations. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 69–81. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-17401-8_​6 CrossRef
38.
Mennink, B.: XPX: generalized tweakable even-mansour with improved security guarantees. In: Robshaw and Katz [48], pp. 64–94
39.
Mennink, B., Preneel, B.: On the XOR of multiple random permutations. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 619–634. Springer, Cham (2015). doi:10.​1007/​978-3-319-28166-7_​30 CrossRef
40.
Mennink, B., Reyhanitabar, R., Vizár, D.: Security of full-state keyed sponge and duplex: applications to authenticated encryption. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 465–489. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48800-3_​19 CrossRef
41.
Minematsu, K.: Parallelizable rate-1 authenticated encryption from pseudorandom functions. In: Nguyen and Oswald [42], pp. 275–292
42.
Nguyen, P.Q., Oswald, E. (eds.): EUROCRYPT 2014. LNCS, vol. 8441. Springer, Heidelberg (2014)
43.
44.
Patarin, J.: Introduction to mirror theory: analysis of systems of linear equalities and linear non equalities for cryptography. Cryptology ePrint Archive, Report 2010/287 (2010)
45.
Peyrin, T. (ed.): FSE 2016. LNCS, vol. 9783. Springer, Heidelberg (2016)MATH
46.
Peyrin, T., Seurin, Y.: Counter-in-tweak: authenticated encryption modes for tweakable block ciphers. In: Robshaw and Katz [48], pp. 33–63
47.
Reyhanitabar, R., Vaudenay, S., Vizár, D.: Authenticated encryption with variable stretch. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 396–425. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53887-6_​15 CrossRef
48.
Robshaw, M., Katz, J. (eds.): CRYPTO 2016. LNCS, vol. 9814. Springer, Heidelberg (2016)MATH
49.
Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30539-2_​2 CrossRef
50.
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, pp. 124–134. IEEE Computer Society (1994)
51.
52.
53.
Zhandry, M.: How to construct quantum random functions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20–23 October 2012, pp. 679–687. IEEE Computer Society (2012)
54.
Zhandry, M.: A note on the quantum collision and set equality problems. Quant. Inf. Comput. 15(7&8), 557–567 (2015)MathSciNet
55.
Zhandry, M.: A note on quantum-secure PRPs. Cryptology ePrint Archive, Report 2016/1076 (2016)
56.
Metadata
Title
XOR of PRPs in a Quantum World
Authors
Bart Mennink
Alan Szepieniec
Copyright Year
2017
Book
Post-Quantum Cryptography

Print ISBN: 978-3-319-59878-9

Electronic ISBN: 978-3-319-59879-6

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59879-6_21

Premium Partner

    Image Credits