We revisit the problem of finding Bblocklong collisions in MerkleDamg˚ard Hash Functions
in the auxiliaryinput random oracle model, in which an attacker gets a piece of Sbit advice
about the random oracle and makes T oracle queries.
Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis,
Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for 2 ≤ B ≤ T (with
respect to a random salt). The attack achieves advantage Ω( e ST B/2
n + T
2/2
n) where n is the
output length of the random oracle. They conjectured that this attack is optimal. However,
this socalled STB conjecture was only proved for B ≈ T and B = 2. Very recently, Ghoshal
and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of B, and
provided an Oe(S
4T B2/2
n + T
2/2
n) bound for all choices of B.
In this work, we prove an Oe((ST B/2
n)· max{1, ST2/2
n}+T
2/2
n) bound for every 2 < B <
T. Our bound confirms the STB conjecture for ST2 ≤ 2
n, and is optimal up to a factor of S
for ST2 > 2
n (note as T
2
is always at most 2n, otherwise finding a collision is trivial by the
birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters
except for B = Oe(1) and ST2 > 2
n.
We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian
(FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the
limitations of prior techniques. Along the way, we obtain a considerably simpler and illuminating
proof for B = 2, recovering the main result of Akshima, Cash, Drucker and Wee.
more »
« less
This content will become publicly available on July 1, 2024
Revisiting timespace tradeoffs for function inversion
We study the blackbox function inversion problem, which is the problem of finding x[N] such that f(x)=y, given as input some challenge point y in the image of a function f:[N][N], using T oracle queries to f and preprocessed advice 01S depending on f. We prove a number of new results about this problem, as follows.
1. We show an algorithm that works for any T and S satisfying TS2maxST=(N3) . In the important setting when ST, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires TS3N3. E.g., Fiat and Naor's algorithm is only nontrivial for SN23 , while our algorithm gives a nontrivial tradeoff for any SN12 . (Our algorithm and analysis are quite simple. As a consequence of this, we also give a selfcontained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.)
2. We show a nonadaptive algorithm (i.e., an algorithm whose ith query xi is chosen based entirely on and y, and not on the f(x1)f(xi−1)) that works for any T and S satisfying S=(Nlog(NT)) giving the first nontrivial nonadaptive algorithm for this problem. E.g., setting T=Npolylog(N) gives S=(NloglogN). This answers a question due to CorriganGibbs and Kogan [TCC, 2019], who asked whether it was possible for a nonadaptive algorithm to work with parameters T and S satisfying T+SlogNo(N) . We also observe that our nonadaptive algorithm is what we call a guessandcheck algorithm, that is, it is nonadaptive and its final output is always one of the oracle queries x1xT. For guessandcheck algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (ST) for this natural class of algorithms. (CorriganGibbs and Kogan showed that any such lower bound for arbitrary nonadaptive algorithms would imply new circuit lower bounds.)
3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f:[N][M] with different ranges.
All of the above results are most naturally described in a model with shared randomness (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not.
more »
« less
 Award ID(s):
 2122230
 NSFPAR ID:
 10428119
 Editor(s):
 Lysyanskaya, Anna; Handschuh, Helena
 Date Published:
 Journal Name:
 Lecture notes in computer science
 ISSN:
 16113349
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


The noise sensitivity of a Boolean function f: {0,1}^n  > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noisesensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/ epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.more » « less

We consider a model of selective prediction, where the prediction algorithm is given a data sequence in an online fashion and asked to predict a prespecified statistic of the upcoming data points. The algorithm is allowed to choose when to make the prediction as well as the length of the prediction window, possibly depending on the observations so far. We prove that, even without any distributional assumption on the input data stream, a large family of statistics can be estimated to nontrivial accuracy. To give one concrete example, suppose that we are given access to an arbitrary binary sequence x1, . . . , xn of length n. Our goal is to accurately predict the average observation, and we are allowed to choose the window over which the prediction is made: for some t < n and m < n − t, after seeing t observations we predict the average of x_{t+1},..., x{t+m}. This particular problem was first studied in [Dru13] and referred to as the “density prediction game”. We show that the expected squared error of our prediction can be bounded by O(1/log n) and prove a matching lower bound, which resolves an open question raised in [Dru13]. This result holds for any sequence (that is not adaptive to when the prediction is made, or the predicted value), and the expectation of the error is with respect to the randomness of the prediction algorithm. Our results apply to more general statistics of a sequence of observations, and we highlight several open directions for future work.more » « less

Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(1−1/O(k)) time algorithm for kSAT in the worst case. For this reason, it has been hypothesized that the worstcase kSAT problem cannot be solved in 2n(1−f(k)/k) time for any unbounded function f. This hypothesis has been called the “SuperStrong ETH”, modeled after the ETH and the Strong ETH. We give two results on the SuperStrong ETH: 1. It has also been hypothesized that kSAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clausetovariable ratio is 2^kln2−Θ(1). We give a randomized algorithm which refutes the SuperStrong ETH for the case of random kSAT and planted kSAT for any clausetovariable ratio. For example, given any random kSAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2^n(1−Ω(logk)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a wellknown algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlák and Zane [17]. 2. The Unique kSAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the SuperStrong ETHs for Unique kSAT and kSAT are equivalent. More precisely, we show the time complexities of Unique kSAT and kSAT are very tightly correlated: if Unique kSAT is in 2^n(1−f(k)/k) time for an unbounded f, then kSAT is in 2^n(1−f(k)(1−ε)/k) time for every ε>0.more » « less

Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(11/O(k)) time algorithm for kSAT in the worst case. For this reason, it has been hypothesized that the worstcase kSAT problem cannot be solved in 2n(1f(k)/k) time for any unbounded function f. This hypothesis has been called the "SuperStrong ETH", modelled after the ETH and the Strong ETH. It has also been hypothesized that kSAT is hard to solve for randomly chosen instances near the "critical threshold", where the clausetovariable ratio is such that randomly chosen instances are satisfiable with probability 1/2. We give a randomized algorithm which refutes the SuperStrong ETH for the case of random kSAT and planted kSAT for any clausetovariable ratio. For example, given any random kSAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2n(1c*log(k)/k) time with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a wellknown algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1999). The Unique kSAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the SuperStrong ETHs for Unique kSAT and kSAT are equivalent. More precisely, we show the time complexities of Unique kSAT and kSAT are very tightly correlated: if Unique kSAT is in 2n(1f(k)/k) time for an unbounded f, then kSAT is in 2n(1f(k)/(2k)) time.more » « less