nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations

verfasst von : Liqing Yu, Yusai Wu, Yu Yu, Zhenfu Cao, Xiaolei Dong

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This work studies the key-alternating ciphers (KACs) whose round permutations are not necessarily independent. We revisit existing security proofs for key-alternating ciphers with a single permutation (KACSPs), and extend their method to an arbitrary number of rounds. In particular, we propose new techniques that can significantly simplify the proofs, and also remove two unnatural restrictions in the known security bound of 3-round KACSP (Wu et al., Asiacrypt 2020). With these techniques, we prove the first tight security bound for t-round KACSP, which was an open problem. We stress that our techniques apply to all variants of KACs with non-independent round permutations, as well as to the standard KACs.

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 On One-Way Functions and Sparse Languages

Nächstes Kapitel Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Each variable represents the number of new edges that can be saved by some constructive method, usually denoted by \(h_i\) in the proofs.

For t-round KAC, the technical lemma of [CS14] (see Lemma 1) solves exactly this probability when \(\left| \mathcal {Q}_{0} \right| =1\).

Although this leads to a somewhat redundant notation, it is still relatively easy to understand. For a concrete example, you can refer to Fig. 1 in the full version [Yu+23, Appendix C].

Due to the uniqueness, we will interchangeably use the permutation-edge \(\langle u, P_{k}, v\rangle \) and the input-output pair (u, v) under \(P_{k}\).

Recall that \(x_i\)’s and \(y_i\)’s are by default in shore 0 and shore \(2t+1\) respectively, so we use the simplified notation here.

The terms arising from a (multivariate) hypergeometric distribution are introduced to help calculate a lower bound on the target probability, see the full version [Yu+23, Eq. (30)] for an example.

In fact, the idea of this framework is quite general and it can be easily generalized to other constructions.

The definition of good transcripts usually excludes the case where \(r_j = 0\). Please note that we keep all key-edges in the graph view here for maximum generality.

Intuitively, this kind of paths require the most new-edges and do not share any edges with other paths. In the words of [WYCD20], the most wasteful way actually means sampling an exclusive element for each inner-node. It had also been shown in [WYCD20] that such samples are easy to analyze. More concrete examples and analysis can be found in the security proofs, such as the Fig. 1 and Appendix C.3 in the full version [Yu+23].

It can be verified that the Examples 2 and 4 in full version [Yu+23, Appendix B] are both connected in the most wasteful way (we purposely assume \(\mathcal {Q}_{1}=\mathcal {Q}_{2}=\emptyset \) over there to ensure that each permutation-edge fixed in the path(s) is new compared to \(\mathcal {Q}_{1}\) and \(\mathcal {Q}_{2}\)).

In Fig. 1 of the full version [Yu+23, Appendix C], the paths between \((x_2,y_2)\) and \((x_2',y_2')\) are called the upper-path and lower-path, respectively.

See Appendix D of the full version [Yu+23] for an analysis of the constraints on Z, which are the sum of constraints from the three shared-edge-based methods.

Note that Step 1 will generate \(2h_1\) new permutation-edges, so there will be \(2h_1\) new elements added to U and V respectively (compared to \(\textsf{Dom}(\mathcal {Q}_{1})\) and \(\textsf{Ran}(\mathcal {Q}_{1})\)). It can be seen that there are only three constraints related to U and V in Eq. (20), \(6h_1\) is obviously the maximum number of changes. We need to point out that this is actually an overestimation. For example, newly added permutation-edges in Step 1 of the form \(\langle x_i\oplus \kappa _0, P_{1}, * \rangle \) cause the set \( U \oplus \kappa _1\) to add new elements (i.e., \(x_i \oplus \kappa _0 \oplus \kappa _1\)) which are already included in \(\textsf{Dom}(\mathcal {Q}_{0}) \oplus \kappa _0 \oplus \kappa _1\). A finer analysis could provide more accurate results, but this simplified treatment is sufficient here since we are not seeking to optimize the constant coefficients in security bounds. Also, we use this easily verifiable overestimation in the evaluation of Eqs. (21)–(26) below.

Although the calculation involves a large number of terms, it is actually simple and regular; the details can be found in the full version [Yu+23].

[Bog+12]

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). https://doi.org/10.1007/978-3-642-29011-4_5 (cited on p. 2)

[Che+18]

Chen, S., Lampe, R., Lee, J., Seurin, Y., Steinberger, J.P.: Minimizing the two-round even-Mansour cipher. J. Cryptol. 4, 1064–1119 (2018). https://doi.org/10.1007/s00145-018-9295-y (cited on pp. 2, 3, 8, 9, 11, 15, 17)

[CS14]

Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_19 (cited on pp. 2, 6, 8)

[DKS12]

Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the even-Mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_21 (cited on p. 2)

[DR02]

Daemen, J., Rijmen, V.: The advanced encryption standard process. In: The Design of Rijndael. Information Security and Cryptography. Springer, Berlin, Heidelberg (2002).https://doi.org/10.1007/978-3-662-04722-4 (cited on p. 1)

[EM97]

Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 3, 151–162 (1997). https://doi.org/10.1007/s001459900025 (cited on p. 1)

[HT16]

Hoang, V.T., Tessaro, S.: Key-alternating ciphers and key-length extension: exact bounds and multi-user security. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 3–32. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_1 (cited on pp. 2, 17)

[LPS12]

Lampe, R., Patarin, J., Seurin, Y.: An asymptotically tight security analysis of the iterated even-Mansour cipher. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 278–295. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_18 (cited on p. 2)

[Ste12]

Steinberger, J.P.: Improved security bounds for key-alternating ciphers via Hellinger distance. In: IACR Cryptology ePrint Archive, p. 481 (2012). http://eprint.iacr.org/2012/481 (cited on p. 2)

[TZ21]

Tessaro, S., Zhang, X.: Tight security for key-alternating ciphers with correlated sub-keys. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 435–464. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_15 (cited on p. 2)

[WYCD20]

Wu, Y., Yu, L., Cao, Z., Dong, X.: Tight security analysis of 3-round key-alternating cipher with a single permutation. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 662–693. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_22 (cited on pp. 2, 3, 9, 10, 12, 15, 16, 18, 21)

[Yu+23]

Yu, L., Wu, Y., Yu, Y., Cao, Z., Dong, X.: security proofs for key-alternating ciphers with non-independent round permutations. In: IACR Cryptology ePrint Archive, Paper 2023/1355 (2023). https://eprint.iacr.org/2023/1355 (cited on pp. 3, 6, 10, 11, 12, 13, 15, 17, 19, 21, 22, 23, 24, 25, 27, 28)

Titel: Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations
verfasst von: Liqing Yu
Yusai Wu
Yu Yu
Zhenfu Cao
Xiaolei Dong
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48614-2

Electronic ISBN: 978-3-031-48615-9

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48615-9_9

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"

Premium Partner