1 Introduction
1.1 Our contribution
2 Preliminaries
2.1 Definition of EM-based key-alternating Feistel cipher
2.2 Security notion of EM-based key-alternating Feistel cipher
2.3 H-coefficient technique
3 Security result of 5-round EM-KAF
3.1 Computation order in the real world and transcript notation
3.2 A brief overview of the proof strategy
4 Proof of Theorem 2
4.1 Sampling procedure in the ideal world
Step name | Sampling | Bad events triggered |
---|---|---|
Step-\(\tau \) a | \(\forall i \in \mathcal {I}_{\textsf {enc}}\), \((S^i, T^i) \leftarrow _{\$} \{0, 1\}^{2n}\) | |
Step-\(\tau \) b | \(\forall i \in \mathcal {I}_{\textsf {dec}}\), \((L^i, R^i) \leftarrow _{\$} \{0, 1\}^{2n}\) | |
bad\(\tau \)-switch, bad\(\tau \)-\(\widehat{Y}\), bad\(\tau \)-3path, bad\(\tau \)-3coll | ||
Step-K | \(\textbf{K}\leftarrow _{\$} \{0, 1\}^{5n}\) | |
badK-outer, badK-source | ||
Step-\(\gamma \) a | \(\forall d \in [q_{*}]\), \(\gamma _*^d \leftarrow _{\$} \varGamma _*^d\) | |
Step-\(\gamma \) b | \(\forall S \in \mathcal {S}^{\mathcal {I}_{R*}}\), \(\widehat{S}\leftarrow _{\$} \{0, 1\}^n\) | |
Step-\(\gamma \) c | \(\forall R \in \mathcal {R}^{\mathcal {I}_{S*}}\), \(\widehat{R}\leftarrow _{\$} \{0, 1\}^n\) | |
bad\(\gamma \)-prim, bad\(\gamma \)-coll, bad\(\gamma \)-\(\widehat{Y}\), bad\(\mu \)-in &out, bad\(\mu \)-source, bad\(\mu \)-inner, bad\(\mu \)-3coll, bad\(\mu \)-size | ||
Step-\(\lambda \) a | \(\forall h \in [q_{**}]\), \(\lambda _{**}^h \leftarrow _{\$} \varLambda _{**}^h\) | |
Step-\(\lambda \) b | \(\forall X \in \mathcal {X}^{\mathcal {I}_R \sqcup \mathcal {I}_{XX}}\), \(\widehat{X}\leftarrow _{\$} \{0, 1\}^n\) | |
Step-\(\lambda \) c | \(\forall Z \in \mathcal {Z}^{\mathcal {I}_S \sqcup \mathcal {I}_{ZZ}}\), \(\widehat{Z}\leftarrow _{\$} \{0, 1\}^n\) | |
Step-\(\lambda \) d | \(\forall \widehat{Y}\in \mathcal {\widehat{Y}}^{\mathcal {I}_{\widehat{Y}\widehat{Y}}}\), \(Y \leftarrow _{\$} \{0, 1\}^n\) | |
Step-\(\lambda \) e | \(\forall i \in \mathcal {I}_{RR} \sqcup \mathcal {I}_{SS}\), \(Y^i \leftarrow _{\$} \{0, 1\}^n\) | |
bad\(\lambda \)-prim, bad\(\lambda \)-coll |
4.1.1 Bad events on \(\tau \)
4.1.2 Sampling K and bad events thereof
4.1.3 Defining and computing \(G[\tau _*]\)
4.1.4 Sampling \(\gamma \)
-
\(\widehat{R}^i + K_1 \notin \textsf {ran}_1\) for each \(i \in \mathcal {I}{\setminus } \mathcal {I}_R\);
-
\(\widehat{S}^i + K_5 \notin \textsf {ran}_5\) for each \(i \in \mathcal {I}{\setminus } \mathcal {I}_S\);
-
\(R^i = R^j \iff \widehat{R}^i = \widehat{R}^j\);
-
\(S^i = S^j \iff \widehat{S}^i = \widehat{S}^j\);
-
\(R^i = R^j \implies \widehat{S}^i + \widehat{S}^j \ne L^i + T^i + L^j + T^j\);
-
\(S^i = S^j \implies \widehat{R}^i + \widehat{R}^j \ne L^i + T^i + L^j + T^j\).
4.1.5 Bad events on \(\gamma \)
4.1.6 Bad events on \(\mu \)
4.1.7 Sampling \(\lambda \)
-
\(\widehat{X}^i + K_2 \notin \textsf {ran}_2\) for each \(i \in \mathcal {I}{\setminus } \mathcal {I}_X\);
-
\(Y^i + K_3 \notin \textsf {dom}_3\) for each \(i \in \mathcal {I}{\setminus } \mathcal {I}_{\widehat{Y}}\);
-
\(\widehat{Z}^i + K_4 \notin \textsf {ran}_4\) for each \(i \in \mathcal {I}{\setminus } \mathcal {I}_Z\).
-
\(\widehat{X}^i + Y^i = R^i\) for each \(i \in \mathcal {I}\);
-
\(Y^i + \widehat{Z}^i = S^i\) for each \(i \in \mathcal {I}\);
-
\(X^i = X^j \iff \widehat{X}^i = \widehat{X}^j\);
-
\(\widehat{Y}^i = \widehat{Y}^j \iff Y^i = Y^j\);
-
\(Z^i = Z^j \iff \widehat{Z}^i = \widehat{Z}^j\).
4.1.8 Bad events on \(\lambda \)
4.1.9 Definition of bad transcripts, bad lemma and good lemma
4.2 Bounding bad\(\gamma \)-prim
-
bad\(\gamma \)-prim-1. \(\exists i \in \mathcal {I}_{R*}\) and \(j \in [q _ 5]\) such that \(\widehat{S}^ i + K_1 = V ^ j _ 5\).
-
bad\(\gamma \)-prim-2. \(\exists i \in \mathcal {I}_{S*}\) and \(j \in [q _ 1]\) such that \(\widehat{R}^ i + K_1 = V ^ j _ 1\).
4.2.1 Bounding bad\(\gamma \)-prim-1
-
bad\(\gamma \)-prim-1a. \(\exists i \in \mathcal {I}_{R*} \cap \mathcal {I}_R\) and \(j \in [q _ 5]\) such that \(\widehat{S}^ i + k_5 = V ^ j _ 5\).In other words,\(~\exists i \in q\), \(j \in [q _ 5]\) and \(l \in [q _ 2]\) such that \(R ^ i + K _ 1 = U ^ l _ 1\) and \(\widehat{S}^ i + K_5 = V ^ j _ 5\). Let’s first fix the values for the indices i, j and l. The probability of each of the events comes out to be (1/N) due to the n-bit randomness over the keys \(K _ 1\) and \(K _ 5\) respectively. As we can choose the indices i, j and l in q, \(q _ 5\) and \(q _ 2\) ways, we use the union bound over all those possible choices to obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {prim}}-1a] \le \frac{q q _ 2 q _ 5}{N ^ 2}\,. \end{aligned}$$(3)
-
bad\(\gamma \)-prim-1b. \(\exists i \in \mathcal {I}_{R*} \cap \mathcal {I}_{RR}\) and \(j \in [q _ 5]\) such that \(\widehat{S}^ i + K_5 = V ^ j _ 5\).In other words,\(~\exists i \in \mathcal {I}_{\textsf {dec}}\), \(j \in [q _ 5]\) and \(l \in [i - 1]\) such that \(R ^ i = R ^ l\) and \(\widehat{S}^ i + K _ 5 = V ^ j _ 5\). Let’s first fix the values for the indices i, j and l. The probability of the event \(R ^ i = R ^ l\) comes out to be (1/N) due to the n-bit randomness over \(R ^ i\) as \(i > l\) and \(i \in \mathcal {I}_{\textsf {dec}}\). The probability of the event \(\widehat{S}^ i + K _ 5 = V ^ j _ 5\) comes out to be (1/N) due to the n-bit randomness over the key \(K _ 5\). As we can choose the pair of indices (i, l) in \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) ways and the index j in \(q _ 5\) ways, we use the union bound over all those possible choices to obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {prim}}-1b] \le \frac{q _ 5 \left( {\begin{array}{c}q\\ 2\end{array}}\right) }{N ^ 2}\,. \end{aligned}$$(4)
4.2.2 Bounding bad\(\gamma \)-prim-2
-
bad\(\gamma \)-prim-2a. \(\exists i \in \mathcal {I}_{S*} \cap \mathcal {I}_S\) and \(j \in [q _ 1]\) such that \(\widehat{R}^ i + K_1 = V ^ j _ 1\).In other words,\(~\exists i \in q\), \(j \in q _ 1\) and \(l \in q _ 2\) such that \(S ^ i + K _ 5 = V ^ l _ 5\) and \(\widehat{R}^ i + K_1 = V ^ j _ 1\). Let’s first fix the values for the indices i, j and l. The probability of each of the events comes out to be (1/N) due to the n-bit randomness over the keys \(K _ 1\) and \(K _ 5\) respectively. As we can choose the indices i, j and l in q, \(q _ 5\) and \(q _ 1\) ways, we use the union bound over all those possible choices to obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {prim}}-2a] \le \frac{q q _ 1 q _ 5}{N ^ 2}\,. \end{aligned}$$(6)
-
bad\(\gamma \)-prim-2b. \(\exists i \in \mathcal {I}_{S*} \cap \mathcal {I}_{SS}\) and \(j \in [q _ 1]\) such that \(\widehat{R}^ i + K_1 = V ^ j _ 1\).In other words,\(~\exists i \in \mathcal {I}_{\textsf {enc}}\), \(j \in [q _ 1]\) and \(l \in [i - 1]\) such that \(S ^ i = S ^ l\) and \(\widehat{R}^ i + K _ 1 = V ^ j _ 1\). Let’s first fix the values for the indices i, j and l. The probability of the event \(S ^ i = S ^ l\) comes out to be (1/N) due to the n-bit randomness over \(S ^ i\) as \(i > l\) and \(i \in \mathcal {I}_{\textsf {enc}}\). The probability of the event \(\widehat{R}^ i + K _ 1 = V ^ j _ 1\) comes out to be (1/N) due to the n-bit randomness over the key \(K _ 1\). As we can choose the pair of indices (i, l) in \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) ways and the index j in \(q _ 1\) ways, we use the union bound over all those possible choices to obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {prim}}-2b] \le \frac{q _ 1 \left( {\begin{array}{c}q\\ 2\end{array}}\right) }{N ^ 2}\,. \end{aligned}$$(7)
4.3 Bounding bad\(\gamma \)-coll
-
bad\(\gamma \)-coll-1. \(\exists i, j \in \mathcal {I}_{R*}\) and \(i \ne j\) such that \(S ^ i \ne S ^ j\) and \(\widehat{S}^ i = \widehat{S}^ j\).
-
bad\(\gamma \)-coll-2. \(\exists i, j \in \mathcal {I}_{S*}\) and \(i \ne j\) such that \(R ^ i \ne R ^ j\) and \(\widehat{R}^ i = \widehat{R}^ j\).
4.3.1 Bounding bad\(\gamma \)-coll-1
-
bad\(\gamma \)-coll-1a. \(\exists i, j \in \mathcal {I}_{R*} \cap \mathcal {I}_R\) and \(i \ne j\) such that \(S ^ i \ne S ^ j\) and \(\widehat{S}^ i = \widehat{S}^ j\).In other words,\(~\exists i, j \in \mathcal {I}_R\), such that \(i \ne j\), and \(k, l \in [q _ 1]\) such thatWe can write the above event in an equivalent way as$$\begin{aligned} R^i + K_1 = U^k_1, R^j + K_1 = U^l_1, \widehat{S}^ i = \widehat{S}^ j. \end{aligned}$$Let’s first fix the values for the indices i, j, k and l and without loss of generality, we assume that \(i > j\). The probability of the event \(R ^ i + K_1 = U^k_1 \) comes out to be (1/N) due to the n-bit randomness over the key \(K_1\). Moreover, the probability of the event \(\widehat{S}^ i = \widehat{S}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{S}^i\). However, the number of choices of indices (i, j, k, l) such that \(R^i + R^j = U^k_1 + U^l_1\) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) q_1\). By using the union bound over all those possible choices to obtain$$\begin{aligned} R^i + K_1 = U^k_1, R^i + R^j = U^k_1 + U^l_1, \widehat{S}^ i = \widehat{S}^ j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-1a] \le \frac{2q _ 1 \left( {\begin{array}{c}q\\ 2\end{array}}\right) }{N ^ 2} \le \frac{q^2q_1}{N^2}\,. \end{aligned}$$(10)
-
bad\(\gamma \)-coll-1b. \(\exists i, j \in \mathcal {I}_{R*} \cap \mathcal {I}_{RR}\) and \(i \ne j\) such that \(S ^ i \ne S ^ j\) and \(\widehat{S}^ i = \widehat{S}^ j\).In other words,\(~\exists i, j \in \mathcal {I}_{RR}\), such that \(i \ne j \in \mathcal {I}_{\textsf {dec}}\), and \(k \in [i-1], l \in [j - 1]\) such thatLet’s first fix the values for the indices i, j, k and l. The probability of the first two events \(R ^ i = R^k\) and \(R^j = R^l\) comes out to be \((1 / N^2)\) due to the n-bit randomness over \(R^i\) and \(R^j\). Moreover, the probability of the event \(\widehat{S}^ i = \widehat{S}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{S}^i\). However, the number of choices of indices (i, j, k, l) is at most \(q^4\). By using the union bound over all those possible choices to obtain$$R^i = R^k, R^j = R^l, \widehat{S}^ i = \widehat{S}^ j.$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-1b] \le \frac{2q^4}{N ^ 3}\,. \end{aligned}$$(11)
-
bad\(\gamma \)-coll-1c. \(\exists i \in \mathcal {I}_{R*} \cap \mathcal {I}_R\) and \(j \in \mathcal {I}_{R*} \cap \mathcal {I}_{RR}\) such that \(S ^ i \ne S ^ j\) and \(\widehat{S}^ i = \widehat{S}^ j\).In other words,\(~\exists i \in \mathcal {I}_R, j \in \mathcal {I}_{RR}\), such that \(i \ne j\) and \(j \in \mathcal {I}_{\textsf {dec}}\), and \(k \in [q_1], l \in [j - 1]\) such thatLet’s first fix the values for the indices i, j, k and l. The probability of the first two events \(R ^ i + K_1 = U^k_1\) and \(R^j = R^l\) comes out to be \((1 / N^2)\) due to the n-bit randomness over \(k_1\) and \(R^j\). Moreover, the probability of the event \(\widehat{S}^ i = \widehat{S}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{S}^i\). However, the number of choices of indices (i, j, l) is at most \(q^3\) and the number of choices for k is at most \(q_1\). By using the union bound over all those possible choices to obtain$$R^i + K_1 = U^k_1, R^j = R^l, \widehat{S}^ i = \widehat{S}^ j.$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-1c] \le \frac{2q^3 q_1}{N ^ 3}\,. \end{aligned}$$(12)
4.3.2 Bounding bad\(\gamma \)-coll-2
-
bad\(\gamma \)-coll-2a. \(\exists i, j \in \mathcal {I}_{S*} \cap \mathcal {I}_S\) and \(i \ne j\) such that \(R ^ i \ne R ^ j\) and \(\widehat{R}^ i = \widehat{R}^ j\).In other words,\(~\exists i, j \in \mathcal {I}_S\), such that \(i \ne j\), and \(k, l \in [q _ 5]\) such thatWe can write the above event in an equivalent way as$$\begin{aligned} S^i + K_5 = U^k_5, S^j + K_5 = U^l_5, \widehat{R}^ i = \widehat{R}^ j. \end{aligned}$$Let’s first fix the values for the indices i, j, k and l and without loss of generality, we assume that \(i > j\). The probability of the event \(S ^ i + K_5 = U^k_5 \) comes out to be (1/N) due to the n-bit randomness over the key \(K_5\). Moreover, the probability of the event \(\widehat{R}^ i = \widehat{R}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{R}^i\). However, the number of choices of indices (i, j, k, l) such that \(S^i + S^j = U^k_5 + U^l_5\) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) q_5\). By using the union bound over all those possible choices to obtain$$\begin{aligned} S^i + K_5 = U^k_5, S^i + S^j = U^k_5 + U^l_5, \widehat{R}^ i = \widehat{R}^ j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-2a] \le \frac{2q _ 5 \left( {\begin{array}{c}q\\ 2\end{array}}\right) }{N ^ 2} \le \frac{q^2q_5}{N^2}\,. \end{aligned}$$(14)
-
bad\(\gamma \)-coll-2b. \(\exists i, j \in \mathcal {I}_{S*} \cap \mathcal {I}_{SS}\) and \(i \ne j\) such that \(R ^ i \ne R ^ j\) and \(\widehat{R}^ i = \widehat{R}^ j\).In other words,\(~\exists i, j \in \mathcal {I}_{SS}\), such that \(i \ne j \in \mathcal {I}_{\textsf {enc}}\), and \(k \in [i-1], l \in [j - 1]\) such thatLet’s first fix the values for the indices i, j, k and l. The probability of the first two events \(S ^ i = S^k\) and \(S^j = S^l\) comes out to be \((1 / N^2)\) due to the n-bit randomness over \(S^i\) and \(S^j\). Moreover, the probability of the event \(\widehat{R}^ i = \widehat{R}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{R}^i\). However, the number of choices of indices (i, j, k, l) is at most \(q^4\). By using the union bound over all those possible choices to obtain$$\begin{aligned} S^i = S^k, S^j = S^l, \widehat{R}^ i = \widehat{R}^ j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-2b] \le \frac{2q^4}{N ^ 3}\,. \end{aligned}$$(15)
-
bad\(\gamma \)-coll-2c. \(\exists i \in \mathcal {I}_{S*} \cap \mathcal {I}_S\) and \(j \in \mathcal {I}_{S*} \cap \mathcal {I}_{SS}\) such that \(R ^ i \ne R ^ j\) and \(\widehat{R}^ i = \widehat{R}^ j\).In other words,\(~\exists i \in \mathcal {I}_S, j \in \mathcal {I}_{SS}\), such that \(i \ne j\) and \(j \in \mathcal {I}_{\textsf {enc}}\), and \(k \in [q_5], l \in [j - 1]\) such thatLet’s first fix the values for the indices i, j, k and l. The probability of the first two events \(S ^ i + K_5 = U^k_5\) and \(S^j = S^l\) comes out to be \((1 / N^2)\) due to the n-bit randomness over \(K_5\) and \(S^j\). Moreover, the probability of the event \(\widehat{R}^ i = \widehat{R}^j\) comes out to be at most 2/N due to the randomness of \(\widehat{R}^i\). However, the number of choices of indices (i, j, l) is at most \(q^3\) and the number of choices for k is at most \(q_5\). By using the union bound over all those possible choices to obtain$$\begin{aligned} S^i + K_5 = U^k_5, S^j = S^l, \widehat{R}^ i = \widehat{R}^ j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -{\textsf {coll}}-2c] \le \frac{2q^3 q_5}{N ^ 3}\,. \end{aligned}$$(16)
4.4 Bounding bad\(\gamma \)-\(\widehat{Y}\)
-
bad\(\gamma \)-\(\widehat{Y}\)-1. \(\exists i \in \mathcal {I}^c_*, j \in [q]\) and \(i \ne j\) such that \(R ^ i = R ^ j\) and \(\widehat{S}^ i + \widehat{S}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).
-
bad\(\gamma \)-\(\widehat{Y}\)-2. \(\exists i \in \mathcal {I}^c_*, j \in [q]\) and \(i \ne j\) such that \(S ^ i = S ^ j\) and \(\widehat{R}^ i + \widehat{R}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).
4.4.1 Bounding bad\(\gamma \)-\(\widehat{Y}\)-1
-
bad\(\gamma \)-\(\widehat{Y}\)-1a \(\exists i \in \mathcal {I}_R, j \in [q]\) and \(i \ne j\) such that \(R ^ i = R ^ j\) and \(\widehat{S}^ i + \widehat{S}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_R, j \in [q]\), with \(i \ne j\) and \(k \in [q_1]\) such thatLet’s first fix the values for the indices i, j and k. The probability of the first event comes from the n-bit randomness over \(K_1\) and the probability of the last event comes from the randomness over \(\hat{S} ^ i\). Hence, the joint probability comes out to be at most \((2 / N^2)\). However, the number of choices of indices i and j is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) and the number of choices for k is at most \(q_1\). By using the union bound over all those possible choices to obtain$$\begin{aligned} R^i + K_1 = U^k_1, R^i = R^j, \hat{S}^i + \hat{S}^j = L^i + T^i + L^j + T^j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-1a] \le \frac{q^2 q_1}{N ^ 2}\,. \end{aligned}$$(19)
-
bad\(\gamma \)-\(\widehat{Y}\)-1b. \(\exists i \in \mathcal {I}_S, j \in [q]\) and \(i \ne j\) such that \(R ^ i = R ^ j\) and \(\widehat{S}^ i + \widehat{S}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_S, j \in [q]\), with \(i \ne j\) and \(k \in [q_5]\) such thatNow, we consider that \(j \in \mathcal {I}_S\), as the analysis of this case is the involved one. Therefore, we have$$\begin{aligned} S^i + K_5 = U^k_5, R^i = R^j, \hat{S}^i + \hat{S}^j = L^i + T^i + L^j + T^j. \end{aligned}$$for some \(l \in [q_5]\) and we equivalently write Eq. (20) as$$\begin{aligned} S^i + K_5 = U^k_5, S^j + K_5 = U^l_5, R^i = R^j, V^k_5 + V^l_5 = L^i + T^i + L^j + T^j, \end{aligned}$$(20)Now, we analyze this case in separate subcases:$$\begin{aligned} S^i + K_5 = U^k_5, S^i + S^j = U^k_5 + U^l_5, R^i = R^j, V^k_5 + V^l_5 = L^i + T^i + L^j + T^j. \end{aligned}$$(21)Case (a): We first assume the construction queries appear after the primitive queries and let \(i < j\) and let j be an encryption query index (analysis for j to be a decryption query will be similar). Then from the first equation we use the randomness of \(K_5\) and from the second equation, we use the randomness of \(S^j\) which allows us to bound the probability of the event for a fixed choice of indices, to at most \(2/N^2\). Moreover, the number of tuples (i, j, k, l) such that Eq. (21) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) for choices of i and j and the number of choices for k is at most \(q_5\) which leaves a unique choice for l such that \(V^k_5 + V^l_5 = L^i + T^i + L^j + T^j\) holds. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_5/N^2\).Case (b): Now, we consider the case where the primitive queries appear after the construction queries and let \(k < l\) and let l be a forward query index. Then from the first equation we use the randomness of \(K_5\) and from the fourth equation, we use the randomness of \(V^l_5\) which allows us to bound the probability of the event for a fixed choice of indices, to at most \(2/N^2\). Moreover, the number of tuples (i, j, k, l) such that Eq. (21) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) for choices of i and j and the number of choices for k is at most \(q_5\) which leaves a unique choice for l such that \(S^i + S^j = U^k_5 + U^l_5\) holds. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_5/N^2\).Case (c): Similarly, if l is an inverse query index. Then from the first equation we use the randomness of \(K_5\) and from the second equation, we use the randomness of \(U^l_5\) which allows us to bound the probability of the event for a fixed choice of indices, to at most \(2/N^2\). Moreover, the number of tuples (i, j, k, l) such that Eq. (21) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) for choices of i and j and the number of choices for k is at most \(q_5\) which leaves a unique choice for l such that \(V^k_5 + V^l_5 = L^i + T^i + L^j + T^j\) holds. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_5/N^2\).By taking the union of all the above cases, we obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-1b] \le \frac{3q^2 q_5}{N ^ 2}\,. \end{aligned}$$(22)
-
bad\(\gamma \)-\(\widehat{Y}\)-1c. \(\exists i \in \mathcal {I}_{RR}, j \in [q]\) and \(i \ne j\) such that \(R ^ i = R ^ j\) and \(\widehat{S}^ i + \widehat{S}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_{RR}, j \in [q]\), with \(i \ne j\) and \(i \in \mathcal {I}_{\textsf {dec}}\) and \(k \in [i-1]\) such thatLet’s first fix the values for the indices i, j and k. The probability of the first event comes from the n-bit randomness over \(R^i\) and the probability of the last event comes from the randomness over \(\hat{S} ^ i\). Hence, the joint probability comes out to be at most \((2 / N^2)\). However, the number of choices of indices i and j is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) and the number of choices for k is at most q. By using the union bound over all those possible choices to obtain$$\begin{aligned} R^i = R^k, R^i = R^j, \hat{S}^i + \hat{S}^j = L^i + T^i + L^j + T^j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-1c] \le \frac{q^3}{N ^ 2}\,. \end{aligned}$$(23)
-
bad\(\gamma \)-\(\widehat{Y}\)-1d. \(\exists i \in \mathcal {I}_{SS}, j \in [q]\) and \(i \ne j\) such that \(R ^ i = R ^ j\) and \(\widehat{S}^ i + \widehat{S}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).Analysis of this case is identical to the analysis of bad\(\gamma \)-\(\widehat{Y}\)-1c., where we use the randomness of \(S^i\) as \(i \in \mathcal {I}_{\textsf {enc}}\). Hence, we obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-1d] \le \frac{q^3}{N ^ 2}\,. \end{aligned}$$(24)
4.4.2 Bounding bad\(\gamma \)-\(\widehat{Y}\)-2
-
bad\(\gamma \)-\(\widehat{Y}\)-2a. \(\exists i \in \mathcal {I}_R, j \in [q]\) and \(i \ne j\) such that \(S ^ i = S ^ j\) and \(\widehat{R}^ i + \widehat{R}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_R, j \in [q]\), with \(i \ne j\) and \(k \in [q_1]\) such thatNow, we consider that \(j \in \mathcal {I}_R\) as this the analysis of this case is the involved one. Therefore, we have$$\begin{aligned} R^i + K_1 = U^k_1, S^i = S^j, \widehat{R}^i + \widehat{R}^j = L^i + T^i + L^j + T^j. \end{aligned}$$for some \(l \in [q_1]\) and we equivalently write Eq. (26) as$$\begin{aligned} R^i + K_1 = U^k_1, R^j + K_1 = U^l_1, S^i = S^j, V^k_1 + V^l_1 = L^i + T^i + L^j + T^j, \end{aligned}$$(26)Now, we analyze this case in separate subcases:$$\begin{aligned} R^i + K_1 = U^k_1, R^i + R^j = U^k_1 + U^l_1, S^i = S^j, V^k_1 + V^l_1 = L^i + T^i + L^j + T^j. \end{aligned}$$(27)Case (a) As before, we assume the construction queries appear after the primitive queries and let \(i < j\) and let j be an encryption query index (analysis for j to be a decryption query will be similar). Then from the first equation we use the randomness of \(K_1\) and from the third equation, we use the randomness of \(S^j\) which allows us to bound the probability of the event for a fixed choice of indices, to at most \(2/N^2\). Moreover, the number of tuples (i, j, k, l) such that Eq. (27) holds is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) for choices of i and j and the number of choices for k is at most \(q_1\) which leaves a unique choice for l such that \(V^k_1 + V^l_1 = L^i + T^i + L^j + T^j\) holds. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_1/N^2\).Case (b) Analysis for this case is exactly identical to the case (b) of bounding bad\(\gamma \)-\(\widehat{Y}\)-1c. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_1/N^2\).Case (c) Analysis for this case is exactly identical to the case (c) of bounding bad\(\gamma \)-\(\widehat{Y}\)-1c. Therefore, by varying all possible choices of indices, we bound the probability to at most \(q^2q_1/N^2\).By taking the union of all the above cases, we obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-2a] \le \frac{3q^2 q_1}{N ^ 2}\,. \end{aligned}$$(28)
-
bad\(\gamma \)-\(\widehat{Y}\)-2b. \(\exists i \in \mathcal {I}_S, j \in [q]\) and \(i \ne j\) such that \(S ^ i = S ^ j\) and \(\widehat{R}^ i + \widehat{R}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_S, j \in [q]\), with \(i \ne j\) and \(k \in [q_5]\) such thatLet’s first fix the values for the indices i, j and k. The probability of the first event comes from the n-bit randomness over \(K_5\) and the probability of the last event comes from the randomness over \(\widehat{R}^ i\). Hence, the joint probability comes out to be at most \((2 / N^2)\). However, the number of choices of indices i and j is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) and the number of choices for k is at most \(q_5\). By using the union bound over all those possible choices to obtain$$\begin{aligned} S^i + K_5 = U^k_5, R^i = R^j, \widehat{R}^i + \widehat{R}^j = L^i + T^i + L^j + T^j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-2b] \le \frac{q^2 q_5}{N ^ 2}\,. \end{aligned}$$(29)
-
bad\(\gamma \)-\(\widehat{Y}\)-2c. \(\exists i \in \mathcal {I}_{RR}, j \in [q]\) and \(i \ne j\) such that \(S ^ i = S ^ j\) and \(\widehat{R}^ i + \widehat{R}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).In other words,\(~\exists i \in \mathcal {I}_{RR}, j \in [q]\), with \(i \ne j\) and \(i \in \mathcal {I}_{\textsf {dec}}\) and \(k \in [i-1]\) such thatLet’s first fix the values for the indices i, j and k. The probability of the first event comes from the n-bit randomness over \(R^i\) and the probability of the last event comes from the randomness over \(\hat{R} ^ i\). Hence, the joint probability comes out to be at most \((2 / N^2)\). However, the number of choices of indices i and j is at most \(\left( {\begin{array}{c}q\\ 2\end{array}}\right) \) and the number of choices for k is at most q. By using the union bound over all those possible choices to obtain$$\begin{aligned} R^i = R^k, S^i = S^j, \hat{R}^i + \hat{R}^j = L^i + T^i + L^j + T^j. \end{aligned}$$$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-2c] \le \frac{q^3}{N ^ 2}\,. \end{aligned}$$(30)
-
bad\(\gamma \)-\(\widehat{Y}\)-2d. \(\exists i \in \mathcal {I}_{SS}, j \in [q]\) and \(i \ne j\) such that \(S ^ i = S ^ j\) and \(\widehat{R}^ i + \widehat{R}^ j = L ^ i + T ^ i + L ^ j + T ^ j\).Analysis of this case is identical to the analysis of bad\(\gamma \)-\(\widehat{Y}\)-2c., where we use the randomness of \(S^i\) as \(i \in \mathcal {I}_{\textsf {enc}}\). Hence, we obtain$$\begin{aligned} \Pr [{\textsf {bad}}\gamma -\widehat{Y}-2d] \le \frac{q^3}{N ^ 2}\,. \end{aligned}$$(31)