# How to Find Cryptographic Needles In Exponentially Large Haystacks

- Speaker:
- Adi Shamir - COLLOQUIUM LECTURE
- Date:
- Tuesday, 6.6.2017, 14:30
- Place:
- Room 337 Taub Bld.
- 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
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.