Time+Place: Tuesday 06/06/2017 14:30 Room 337 Taub Bld.
Title: Memory-Efficient Algorithms for Finding Needles in Haystacks
Speaker: Adi Shamir - COLLOQUIUM LECTURE https://en.wikipedia.org/wiki/Adi_Shamir
Affiliation: Weizmann Institute
Host: Yuval Filmus


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 

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.

Refreshments will be served from 14:15
Lecture starts at 14:30