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

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.

1. 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. 2.

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

3. 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. 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. 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. 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. 7.

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

8. 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. 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. 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. 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. 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. 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. 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].

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).

Authors and Affiliations

1. East China Normal University, Shanghai, China

   Liqing Yu, Zhenfu Cao & Xiaolei Dong

2. Shanghai Jiao Tong University, Shanghai, China

   Yu Yu

3. Shanghai Qi Zhi Institute, Shanghai, China

   Liqing Yu, Yusai Wu & Yu Yu

Corresponding author

Correspondence to Yusai Wu .

Editors and Affiliations

1. Apple, Cupertino, CA, USA

   Guy Rothblum

2. NTT Research, Sunnyvale, CA, USA

   Hoeteck Wee

Reprints and permissions

© 2023 International Association for Cryptologic Research

Policies and ethics