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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Each variable represents the number of new edges that can be saved by some constructive method, usually denoted by \(h_i\) in the proofs.
- 2.
- 3.
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].
- 4.
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}\).
- 5.
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.
- 6.
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.
- 7.
In fact, the idea of this framework is quite general and it can be easily generalized to other constructions.
- 8.
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.
- 9.
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].
- 10.
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}\)).
- 11.
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.
- 12.
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.
- 13.
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.
- 14.
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].
References
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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, 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)
Acknowledgements
We would like to thank the anonymous reviewers of TCC 2023 for their valuable comments. Yu Yu is supported by the National Natural Science Foundation of China (Grant Nos. 62125204 and 92270201), the National Key Research and Development Program of China (Grant No. 2018YFA0704701), and the Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008). Yu Yu also acknowledges the support from the XPLORER PRIZE. This work is supported in part by the National Key Research and Development Program of China (Grant No. 2022YFB2701400) and in part by the National Natural Science Foundation of China (Grant No. 62132005, 62172162).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Yu, L., Wu, Y., Yu, Y., Cao, Z., Dong, X. (2023). Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14369. Springer, Cham. https://doi.org/10.1007/978-3-031-48615-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-48615-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48614-2
Online ISBN: 978-3-031-48615-9
eBook Packages: Computer ScienceComputer Science (R0)
