TITLE: Lattice Algorithms: State of the Art and Open Problems
SPEAKER: Daniele Micciancio (UCSD)

ABSTRACT
Computational problems on point lattices play an important role in
many areas of computer science and mathematics. Since the discovery of
the LLL basis reduction algorithm in the early '80s, much effort has
gone into the development of better (faster, or more accurate)
algorithms, largely motivated by applications in cryptanalysis. Today,
with the flourishing of lattice based cryptography (i.e.,
cryptographic function whose security rests on the computational
intractability of lattice problems, including the recent development
of fully homomorphic encryption schemes), improving our understanding
of the effort required to solve lattice problems has never been more
important, as it plays a critical role determining appropriate key
sizes. In this talk I will describe the current state of the art in
lattice algorithms, including the asymptotically fastest known
algorithm of Micciancio and Voulgaris, as well as less understood but
practically effective heuristics, and a panoramic of the many research
problems that are still open in the area.

Bio sketch: Daniele Micciancio got his PhD from MIT in 1998, and
joined the UCSD CSE faculty in 1999. He is the recipient of several
awards, including an NSF CAREER award, Sloan Fellowship and Hellman
Fellowship. He is most known for his research on the complexity of
lattice problems, which spans the whole spectrum from computational
complexity and algorithms, to cryptography. His most notable
achievements include the first significant inapproximability result
for the Shortest Vector Problem, pioneering the use of cyclic and
ideal lattices from algebraic number theory for the construction of
very efficient cryptographic primitives based on worst-case complexity
assumptions, and the discovery of the first single exponential time
algorithm to solve all the most important computational problems on
point lattices.

Homomorphic encryption allows you to delegate the processing of your data or your query to a "worker" (e.g., the "cloud") without sacrificing your privacy. The worker can process your private data or private query even though it is encrypted, and send back to you the (encrypted) response that you were seeking, without learning anything significant.

This talk will partly be a tutorial designed to give a taste of how homomorphic encryption schemes work, and why they have been so inefficient. Next, the talk will sketch some very recent results that dramatically improve efficiency and give us hope that homomorphic computation may one day be truly practical.

Bilinear pairings, such as the Weil and Tate pairings, have revolutionized
public-key cryptography since they burst onto the scene at the turn of the
century. In the decade that has followed, methods to compute
cryptographically secure pairings have received a great deal of attention
from mathematicians and cryptographers alike, in an effort to accelerate
their speed so that the many new and exciting protocols that pairings
facilitate can be realized in industry. In this talk we give an overview
of the progress in pairing computation, paying particular attention to the
very latest results in the area.

In this talk, we present the family of generalized Hessian curves.

The family of generalized Hessian curves covers more isomorphism classes of elliptic curves than Hessian curves.

We provide efficient unified addition formulas for generalized Hessian curves. The formulas even feature completeness for suitably chosen curve parameters.

We also also present extremely fast addition formulas for generalized binary Hessian curves. The fastest projective addition formulas require $9\M+3\s$, where $\M$ is the cost of a field multiplication and $\s$ is the cost of a field squaring. Moreover, very fast differential addition and doubling formulas are provided that need only $5\M+4\s$ when the curve is chosen with small parameters.