IDItai Dinur
Itai Dinur
*This is an algorithmically generated author record based on publicly available information.
Itai Dinur has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
Nathan Keller
Bar-Ilan University
4 shared publications- Nathan Keller
Department of Mathematics, Bar Ilan University, Ramat Gan, Israel
4 shared publications - Gaëtan Leurent
INRIA
2 shared publications Niv Nadler
2 shared publicationsOhad Klein
Bar-Ilan University
2 shared publications- Ohad Klein
Hebrew University of Jerusalem
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1660-1671
Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1660-1671
Open AccessNon-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations
- Open Access
- 11 June 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (3) , 1-41
Fine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR
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.- 11 June 2024
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 71 (3) , 1-41
Open AccessFine-grained Cryptanalysis: Tight Conditional Bounds for Dense k -SUM and k -XOR
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. - Open Access
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
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. On the other hand, 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 paper, 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 which 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.Open AccessFine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
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. On the other hand, 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 paper, 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 which 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. - 15 April 2023
- Published by Springer Nature
- p. 98-127
Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation
- 15 April 2023
- Published by Springer Nature
- p. 98-127
Efficient Detection of High Probability Statistical Properties of Cryptosystems via Surrogate Differentiation
- 25 May 2022
- Published by Springer Nature
- p. 57-85
Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2
- 25 May 2022
- Published by Springer Nature
- p. 57-85
Refined Cryptanalysis of the GPRS Ciphers GEA-1 and GEA-2
- 16 June 2021
- Published by Springer Nature
- p. 374-403
Cryptanalytic Applications of the Polynomial Method for Solving Multivariate Equation Systems over GF(2)
- 16 June 2021
- Published by Springer Nature
- p. 374-403
Cryptanalytic Applications of the Polynomial Method for Solving Multivariate Equation Systems over GF(2)
- 1 May 2020
- Published by Springer Nature
- Vol. 12106, 433-460
On the Streaming Indistinguishability of a Random Permutation and a Random Function
An adversary with S bits of memory obtains a stream of Q elements that are uniformly drawn from the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,2,\ldots ,N\}$$\end{document}{1,2,…,N}, either with or without replacement. This corresponds to sampling Q elements using either a random function or a random permutation. The adversary’s goal is to distinguish between these two cases.- 1 May 2020
- Published by Springer Nature
- Vol. 12106, 433-460
On the Streaming Indistinguishability of a Random Permutation and a Random Function
An adversary with S bits of memory obtains a stream of Q elements that are uniformly drawn from the set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1,2,\ldots ,N\}$$\end{document}{1,2,…,N}, either with or without replacement. This corresponds to sampling Q elements using either a random function or a random permutation. The adversary’s goal is to distinguish between these two cases.- 1 May 2020
- Published by Springer Nature
- p. 405-434
Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications
- 1 May 2020
- Published by Springer Nature
- p. 405-434
Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications
- 26 September 2019
- Published by Springer Nature in Journal of Cryptology
- Vol. 33 (3) , 824-873
An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing
- 26 September 2019
- Published by Springer Nature in Journal of Cryptology
- Vol. 33 (3) , 824-873
An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing