International Association
for Cryptologic Research

We present analysis of time-space tradeoffs for both the search and decision variants of the $k$-collision problem in algorithmic perspective, where $k \in \left[2, O(\operatorname{polylog}(N))\right]$ and the underlying function is $f_{N,M} : [N] \rightarrow [M]$ with $M \geq N$. In contrast to prior work that focuses either on 2-collisions or on random functions with $M = N$, our results apply to both random and arbitrary functions and extend to a broader range of $k$. The tradeoffs are derived from explicit algorithmic constructions developed in this work, especially for decision problems when $k\geq3$. For 2-collision problems, we show that for any random function $f_{N,M}$ with $M \geq N$, the time-space tradeoff for finding all 2-collisions follows a single curve $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}}\right)$, where $T$ denotes time complexity and $S$ denotes available space. This tradeoff also extends to arbitrary functions with at most $O(N)$ total 2-collisions. For 3-collision problems, we identify two time-space tradeoff curves for the search variant over random functions, depending on the available space $S$. For arbitrary functions, we show that the decision problem can be solved with a tradeoff of $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_3}\right)$, where $n_{i}$ denotes the number of $i$-collisions. Surprisingly, for random functions, the decision problem for 3-collision shares the same time-space tradeoff as the 2-collision case $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}}\right)$. For general $k$-collision problems, we extend these results to show that the decision problem over arbitrary functions can be solved in time $T=\widetilde{O}\left(\frac{N^{3/2}}{\sqrt{S}} + \frac{N}{S}\frac{n_2}{n_k}\right)$. For the search problem over random functions, we derive two time-space tradeoffs based on the space $S$, yielding approximately $S^{1/(k-2)}$ or $S^{1/(2k-2)}$-fold speedups compared to the low-memory setting $S = O(\log M)$. When $M = N$, the tradeoff simplifies to one single curve with $S^{1/(k-2)}$-fold speedup.

In CRYPTO 2019, Gohr showed that well-trained neural networks could perform cryptanalytic distinguishing tasks superior to differential distribution table (DDT)-based distinguishers. This suggests that the differential-neural distinguisher (ND) may use additional information besides pure ciphertext differences. However, the explicit knowledge beyond differential distribution is still unclear. In this work, we provide explicit rules that can be used alongside DDTs to enhance the effectiveness of distinguishers compared to pure DDT-based distinguishers. These rules are based on strong correlations between bit values in right pairs of XOR-differential propagation through addition modulo $2^n$. Interestingly, they can be closely linked to the earlier study of the multi-bit constraints and the recent study of the fixed-key differential probability. In contrast, combining these rules does not improve the NDs' performance. This suggests that these rules or their equivalent form have already been exploited by NDs, highlighting the power of neural networks in cryptanalysis. In addition, we find that to enhance the differential-neural distinguisher's accuracy and the number of rounds, regulating the differential propagation is imperative. Introducing differences into the keys is typically believed to help eliminate differences in encryption states, resulting in stronger differential propagations. However, differential-neural attacks differ from traditional ones as they don't specify output differences or follow a single differential trail. This questions the usefulness of introducing differences in a key in differential-neural attacks and the resistance of Speck against such attacks in the related-key setting. This work shows that the power of differential-neural cryptanalysis in the related-key setting can exceed that in the single-key setting by successfully conducting a 14-round key recovery attack on Speck32/64.