- This event has passed.
CSE Colloquium: Fang Song
March 7, 2016 @ 12:30 pm - 1:30 pm UTC-5
Title: Get Cryptography Ready for a Quantum World
Abstract: Cybersecurity is becoming a more and more serious issue at
the individual, societal and national levels, and cryptography
provides the basis of a secure solution. However, quantum computing, a
new scientific paradigm with steady advances in technology of physical
implementations, would change classical cryptography drastically. It
is known that quantum computers can break many of the public-key
cryptography deployed on the Internet today. This demands an update to
quantum-safe cryptography. On the other hand, honest users can also
take advantage of quantum technology and sometimes achieve what is
impossible classically, such as exchanging a secret key against
computationally unbounded eavesdropper.
In this talk, I will introduce the threats and opportunities that
cryptography faces in a quantum world with a focus on securing
classical cryptosystems against quantum attacks. In the first part, I
will discuss new candidate problems for building quantum-safe
cryptography. In some detail, I will describe efficient quantum
algorithms breaking a promising candidate (lattice) problem that was
believed hard for quantum computers [1,2]. In the second part, I will
discuss the difficulties and approaches of analyzing formally the
security of classical cryptographic constructions in the presence of
quantum attacks. I will describe a recent work [3] on establishing
quantum security of hash functions and general proof techniques for
hash-based cryptosystems.
[1] Efficient quantum algorithms for computing class groups and
solving the principal ideal problem in arbitrary degree number
fields. Jean-François Biasse and Fang Song. (SODA 2016)
[2] A Quantum Algorithm for Computing the Unit Group of an Arbitrary
Degree Number Field. Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev
and Fang Song. (STOC 2014)
[3] Mitigating multi-target attacks in hash-based signatures. Andreas
Hülsing, Joost Rijneveld and Fang Song. (PKC 2016)
