5 papers · 1 filter
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…
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…
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…
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…