3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is T S³ = n⁶ (up to logarithmic factors), where n is the number of input integers, S is the length of the preprocessed data structure, and T is the running time of the query algorithm. This tradeoff was achieved in [Kopelowitz and Porat, 2019; Golovnev et al., 2020] using the Fiat-Naor generic algorithm for Function Inversion. Consequently, [Golovnev et al., 2020] asked whether this algorithm can be improved by leveraging the structure of 3SUM-Indexing. In this paper, we exploit the structure of 3SUM-Indexing to give a time-space tradeoff of T S = n^{2.5}, which is better than the best known one in the range n^{3/2} ≪ S ≪ n^{7/4}. We further extend this improvement to the kSUM-Indexing problem - a generalization of 3SUM-Indexing - and to the related kXOR-Indexing problem, where addition is replaced with XOR. Additionally, we improve the best known time-space tradeoffs for the Jumbled Indexing problem, which is a well-known data structure problem related to 3SUM-Indexing. Our improvement comes from an alternative way to apply the Fiat-Naor algorithm to 3SUM-Indexing. Specifically, we exploit the structure of the function to be inverted by decomposing it into "sub-functions" with certain properties. This allows us to apply an improvement to the Fiat-Naor algorithm (which is not directly applicable to 3SUM-Indexing), obtained in [Golovnev et al., 2023] in a much larger range of parameters. We believe that our techniques may be useful in additional application-dependent optimizations of the Fiat-Naor algorithm.

In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field \(\mathbb{F}_2\) drawn from a specified distribution. In particular, for any \(d \ge 2\), we design a distribution of degree up to \(d\) polynomials \(\{p_i(x_1,\ldots,x_n)\}_{i\in[m]}\) for \(m \lt n\) over \(\mathbb{F}_2\) for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves \(\{p_i(x_1,\ldots,x_n) = y_i\}_{i\in[m]}\) for a random vector \((y_1,\ldots,y_m)\). On the other hand, while solutions exist with high probability, we conjecture that for constant \(d \gt 2\), it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.

The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.

Abstract Feistel structures are an extensively researched type of cryptographic schemes. In this paper, we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n -bit inputs with seven independent round keys of n /2 bits each, a MITM attack can use ( $$2^{1.5n}$$ 2 1.5 n , $$2^{1.5n}$$ 2 1.5 n ) time and memory, while dissection requires ( $$2^{2n}$$ 2 2 n , $$2^{n}$$ 2 n ) time and memory. Our new attack requires only ( $$2^{1.5n}$$ 2 1.5 n , $$2^{n}$$ 2 n ) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multi-collisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions—in fact, we can use them to reduce the memory complexity of the best known attacks on several concrete cryptosystems such as round-reduced CAST-128 (where we reduce the complexity from $$2^{111} $$ 2 111 to $$2^{64}$$ 2 64 ) and full DEAL-256 (where we reduce the complexity from $$2^{200}$$ 2 200 to $$2^{144}$$ 2 144 ), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures—for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of $$2^{16}$$ 2 16 .

The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length T and width 2S attempts to compute a function f : {0, 1}n → {0, 1}. However, instead of receiving direct access to the input bits (x1,…, xn), the input is given in pairs of the form (ij, xij) ∈ {1, …, n} × {0, 1} for j = 1, 2,…, T, where the indices i1,…,iT are chosen at random from a pre-fixed distribution.

An average-case variant of the k -SUM conjecture asserts that finding k numbers that sum to 0 in a list of r random numbers, each of the order r k , cannot be done in much less than \(r^{\lceil k/2 \rceil }\) time. However, in the dense regime of parameters, where the list contains more numbers and many solutions exist, the complexity of finding one of them can be significantly improved by Wagner’s k -tree algorithm. Such algorithms for k -SUM in the dense regime have many applications, notably in cryptanalysis. In this article, assuming the average-case k -SUM conjecture, we prove that known algorithms are essentially optimal for k = 3,4,5. For k > 5, we prove the optimality of the k -tree algorithm for a limited range of parameters. We also prove similar results for k -XOR, where the sum is replaced with exclusive or. Our results are obtained by a self-reduction that, given an instance of k -SUM that has a few solutions, produces from it many instances in the dense regime. We solve each of these instances using the dense k -SUM oracle and hope that a solution to a dense instance also solves the original problem. We deal with potentially malicious oracles (that repeatedly output correlated useless solutions) by an obfuscation process that adds noise to the dense instances. Using discrete Fourier analysis, we show that the obfuscation eliminates correlations among the oracle’s solutions, even though its inputs are highly correlated.

We consider the problem of finding a solution to a multivariate polynomial equation system of degree d in n variables over . For d = 2, the best-known algorithm for the problem is by Bardet et al. [J. Complexity, 2013] and was shown to run in time O(20.792n) under assumptions that were experimentally found to hold for random equation systems. The best-known worst-case algorithm for the problem is due to Björklund et al. [ICALP'19]. It runs in time O(20.804n) for d = 2 and O(2(1-1/(2.7d))n) for d > 2. In this paper, we devise a worst-case algorithm that improves the one by Björklund et al. It runs in time O(20.6943n) (or O(1.6181n)) for d = 2 and O(2(1–1/(2d))n) for d > 2. Our algorithm thus outperforms all known worst-case algorithms, as well as ones analyzed for random equation systems. We also devise a second algorithm that outputs all solutions to a polynomial system and has similar complexity to the first (provided that the number of solutions is not too large). A central idea in the work of Björklund et al. was to reduce the problem of finding a solution to a polynomial system over to the problem of counting the parity of all solutions. A parity-counting instance was then reduced to many smaller parity-counting instances. Our main observation is that these smaller instances are related and can be solved more efficiently by a new algorithm to a problem which we call multiple parity-counting.

Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) combiner \( \mathcal {H}_1(M) \oplus \mathcal {H}_2(M) \) and the concatenation combiner \( \mathcal {H}_1(M) \Vert \mathcal {H}_2(M) \) . Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice \(\mathcal {H}_2(\mathcal {H}_1(IV, M), M)\) and the Zipper hash \(\mathcal {H}_2(\mathcal {H}_1(IV, M), \overleftarrow{M})\) , where \(\overleftarrow{M}\) is the reverse of the message M . In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: Several generic preimage attacks on the XOR combiner: A first attack with a best-case complexity of \( 2^{5n/6} \) obtained for messages of length \( 2^{n/3} \) . It relies on a novel technical tool named interchange structure. It is applicable for combiners whose underlying hash functions follow the Merkle–Damgård construction or the HAIFA framework. A second attack with a best-case complexity of \( 2^{2n/3} \) obtained for messages of length \( 2^{n/2} \) . It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the Merkle–Damgård construction. An improvement upon the second attack with a best-case complexity of \( 2^{5n/8} \) obtained for messages of length \( 2^{5n/8} \) . It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two n -bit narrow-pipe hash functions following the considered constructions can never provide n -bit security. A generic second-preimage attack on the concatenation combiner of two Merkle–Damgård hash functions. This attack finds second preimages faster than \( 2^n \) for challenges longer than \( 2^{2n/7} \) and has a best-case complexity of \( 2^{3n/4} \) obtained for challenges of length \( 2^{3n/4} \) . It also exploits properties of functional graphs of random mappings. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is \( 2^{3n/5} \) , obtained for challenge messages of length \( 2^{2n/5} \) . An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is \( 2^{13n/22} \) , obtained for challenge messages of length \( 2^{13n/22} \) . The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two n -bit narrow-pipe Merkle–Damgård hash functions do not provide much more security than that can be provided by a single n -bit hash function. Our main technical contributions include the following: The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.

The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k and smaller than ln 4-o(1)≈ 1.39 for the sparse subset of k ’s, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k . In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large k and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k ≤ 10. In the last part of the article, we describe some new applications of this online checkpointing problem.

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.

Side channel attacks are typically divided into two phases: In the collection phase the attacker tries to measure some physical property of the implementation, and in the analysis phase he tries to derive the cryptographic key from the measured information. The field is highly fragmented, since there are many types of leakage, and each one of them usually requires a different type of analysis. In this paper we formalize a general notion of leakage attacks on iterated cryptosystems, in which the attacker can collect (via physical probing, power measurement, or any other type of side channel) one bit of information about the intermediate state of the encryption after each round. Since bits computed during the early rounds can be usually represented by low degree multivariate polynomials in the plaintext and key bits, we can use the recently discovered cube attack as a generic analysis phase which can be applied in principle to any type of leaked data. However, the original cube attack requires extremely clean data, whereas the information provided by side channel attacks can be quite noisy. To address this problem, we develop in this paper a new type of robust cube attack, which can recover the key even when some of the leaked bits are unreliable. In particular, we show how to exploit trivial equations (of the form 0 = 0, which are plentiful but useless in standard cube attacks) in order to correct a fraction of measurement errors which can be arbitrarily close to 1. Finally, we demonstrate our approach by describing efficient leakage attacks on Serpent (requiring only 218 time for full key recovery when the leaked state bits are clean) and on AES (requiring 235 time in the same scenario), and show how to make them robust with a small additional complexity.