The Taub Faculty of Computer Science Events and Talks

One of the most common algorithmic tasks is to find a single interesting event (a needle) in an exponentially large collection (haystack) of N=3D2^n possible events, or to demonstrate that no such event is likely to exist. In particular, we are interested in the problem of finding needles which are defined as events that happen with an unusually high probability of p>>1/N in a haystack which is an almost uniform distribution on N possible events. Such a search algorithm has many applications in cryptography and cryptanalysis, and its best known time/memory tradeoff requires O(1/Mp^2) time given O(M) memory when the search algorithm can only sample values from this distribution. In this talk I will describe much faster needle searching algorithms when the distribution is defined by applying some deterministic function f to random inputs. Such a distribution can be modelled by a random directed graph with N vertices in which almost all the vertices have O(1) predecessors while the vertex we are looking for has an unusually large number of O(pN) predecessors. When we are given only a constant amount of memory, we propose a new search methodology which we call NestedRho. As p increases, such random graphs undergo several subtle phase transitions, and thus the log-log dependence of the time complexity T on p becomes a piecewise linear curve which bends four times. Our new algorithm is faster than the O(1/p^2) time complexity of the best previous algorithm in the full range of 1/N < p < 1, and in particular it improves it for some values of p by a significant factor of sqrt {N}. When we are given more memory, we show how to combine the NestedRho technique with the parallel collision search technique in order to further reduce its time complexity. Finally, we show how to apply our new search technique to more complicated distributions with multiple peaks when we want to find all the peaks whose probabilities are higher than p. The talk will be self contained, requiring no prior knowledge of cryptography. It is joint work with Itai Dinur, Orr Dunkelman, and Nathan Keller.
Short Bio (from Wikipedia):
Shamir received a BSc degree in mathematics from Tel Aviv University in 1973 and obtained his MSc and PhD degrees in Computer Science from the Weizmann Institute in 1975 and 1977 respectively. After a year postdoc at University of Warwick, he did research at MIT from 1977-1980 before returning to be a member of the faculty of Mathematics and Computer Science at the Weizmann Institute. Starting from 2006, he is also an invited professor at Ecole Normale Superieure in Paris.
He is a co-inventor of the RSA algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige-Fiat-Shamir identification scheme (along with Uriel Feige and Amos Fiat), one of the inventors of differential cryptanalysis (along with Eli Biham), and has made many contributions to the fields of cryptography and computer science. Shamir's other numerous inventions and contributions to cryptography include the Shamir secret sharing scheme, the breaking of the Merkle-Hellman knapsack cryptosystem, visual cryptography, and the TWIRL and TWINKLE factoring devices. Shamir has also made contributions to computer science outside of cryptography, such as finding the first linear time algorithm for 2-satisfiability and showing the equivalence of the complexity classes PSPACE and IP.
Shamir has received a number of awards, including the 2002 ACM Turing Award, the Paris Kanellakis Theory and Practice Award, the Erdoes Prize, the 1986 IEEE W.R.G. Baker Award, the UAP Scientific Prize, the Vatican's PIUS XI Gold Medal, the 2000 IEEE Koji Kobayashi Computers and Communications Award, the 2008 Israel Prize, and the 2017 Japan Prize.