9 papers
Lower Bounds on Black-Box Constructions of Pseudorandom Functions
Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam
In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When co…
Improved Time-Space Tradeoffs for 3SUM-Indexing
Itai Dinur, Alexander Golovnev
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 (u…
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal +3
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case search problem of finding a solution t…
Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
Itai Dinur, Nathan Keller, Avichai Marmor
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…
On Differential Privacy and Adaptive Data Analysis with Bounded Space
Itai Dinur, Uri Stemmer, David P. Woodruff +1
We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that…
Locality-Preserving Hashing for Shifts with Connections to Cryptography
Elette Boyle, Itai Dinur, Niv Gilboa +3
Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically clos…
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
Itai Dinur, Nathan Keller, Ohad Klein
An average-case variant of the -SUM conjecture asserts that finding numbers that sum to 0 in a list of random numbers, each of the order , cannot be done in much le…
Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting
Itai Dinur
We consider the problem of finding a solution to a multivariate polynomial equation system of degree in variables over . For , the best-known algorithm f…
Tight Bounds on Online Checkpointing Algorithms
Achiya Bar-On, Itai Dinur, Orr Dunkelman +4
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 p…