Microsoft Research India Workshop on
Lattice-Based Cryptography
December 1, 2013
Lattice-based cryptography revolutionized the field of cryptography with fundamental theoretical breakthroughs and potentially transformative applications. This workshop will include lectures on state of the art in lattice-based cryptography by eminent researchers. Topics that will be covered include algorithmic/complexity foundations of lattices, constructions such as fully homomorphic encryption, functional encryption, hashing, and signature schemes using hard problems on lattices, and cryptanalytic attacks using algorithms on lattices. These lectures will be useful to researchers in cryptography at all stages who wish to advance their knowledge of lattice based cryptography.
Invited Speakers
- Shweta Agrawal, University of California Los Angeles, U S A
- Sanjam Garg, IBM Research, U S A
- Nadia Heninger, University of Pennsylvania, U S A
- Vadim Lyubashevsky, École Normale Supérieure, Paris, France
- Alon Rosen, The Interdisciplinary Center, Herzliya, Israel
- Damien Stehlé, École Normale Supérieure de Lyon, France
Detailed program will be available on this web site soon.
Time and Place
This workshop will take place in the MSR India building (VIGYAN, #9 Lavelle Road) from 9 AM to 6 PM on December 1, 2013. MSR India is just a few minutes (by walk) away from the conference hotel of Asiacrypt 2013.
Registration
Registration for the workshop is free but required. Please register by sending e-mail to indiamrc@microsoft.com with your name, position, affiliation, and whether you are registered for Asiacrypt 2013. Due to limited space, registered participants of Asiacrypt will be given priority. Lunch and coffee/tea/snacks will be served at the venue during the day.
Program
9:00 – 10:00 |
Damien Stehlé, École Normale Supérieure de Lyon, France |
10:00 – 11:00 |
Nadia Heninger, University of Pennsylvania, U S A |
11:00 – 11:30 |
Break |
11:30 – 12:30 |
Alon Rosen, The Interdisciplinary Center, Herzliya, Israel |
12:30 – 2:00 |
Lunch |
2:00 – 3:00 |
Vadim Lyubashevsky, École Normale Supérieure, Paris, France |
3:00 – 4:00 |
Shweta Agrawal, Indian Institute of Technology, Delhi |
4:00 – 4:30 |
Break |
4:30 – 5:30 |
Sanjam Garg, IBM Research, U S A |
Abstracts
Damien Stehlé
École Normale Supérieure de Lyon, France
Title: An overview of lattice reduction algorithms
Abstract : The best generic tool currently known for attacking lattice-based cryptographic primitives is lattice reduction. Lattice reduction is a representation
paradigm: it consists in finding a representation (a basis) of a given lattice that provides easier access to intrinsic properties of that lattice.
In this talk, I will give an overview of the state of the art in lattice reduction algorithms. I will also describe how lattice reduction may be used to solve standard problems from lattice-based cryptography, namely, the Learning With Errors (LWE) and Small Integer Solution (SIS) problems.
Nadia Heninger
University of Pennsylvania, U S A
Title: Approximate Common Divisors via Lattices
Abstract: Coppersmith's technique using lattices to find small roots of polynomial equations (and Howgrave-Graham's extension to solving equations modulo divisors) have produced many fascinating results, particularly in the cryptanalysis of RSA: low public exponent padding vulnerabilities, low public exponent vulnerabilities, and efficient key recovery from partial information. In this talk, I will discuss generalizations of these results and their applications. Extending these results to multivariate equations informs our understanding of fully homomorphic encryption schemes over the integers. The extension to rings of integers over number fields informs our understanding of learning with errors over ideals. And finally, the analogue of these results for polynomial rings turns out to give new efficient decoding algorithms for decoding families of error-correcting codes, including Reed-Solomon codes, Parvaresh-Vardy codes, and algebraic geometry codes.
Joint work with Henry Cohn.
Alon Rosen
The Interdisciplinary Center, Herzliya, Israel
Title: The Learning with Rounding Problem
Abstract: In this talk I will survey a recently introduced cryptographic problem called Learning with Rounding (LWR). I will show reductions from and to the more well-established Learning with Errors (LWE) problem, and demonstrate the applicability of LWR to the construction of efficient Pseudorandom Functions and other cryptographic primitives.
Vadim Lyubashevsky
École Normale Supérieure, Paris, France
Title: Practical Digital Signatures from Lattices
Recent work has solidly established lattice-based signatures as a viable replacement for number-theoretic schemes should quantum computing come into fruition. In fact, the current lattice-based schemes have key and signature sizes comparable to RSA while being an order of magnitude faster. The main focus of this talk will be presenting the main ideas behind the latest results in this area. In addition to the high level intuition, I will try to motivate the many employed optimizations, such as having an NTRU-like public key and sampling from a bimodal Gaussian distribution.
Most of the talk will be based on the papers "Lattice Signatures without Trapdoors" and "Lattice Signatures and Bimodal Gaussians". The latter is joint work with Leo Ducas, Alain Durmus, and Tancrede Lepoint.
Shweta Agrawal
Indian Institute of Technology, Delhi
Title: Building Functional Encryption from Learning With Errors.
Abstract : Recent times have seen fantastic advances in the general area of "computing on encrypted data". Of particular importance, is the fast-growing area of functional encryption (FE). Functional encryption is a generalization of public key encryption which allows tremendous flexibility and control in learning information from encrypted data. In functional encryption, a user's secret key corresponds to some function f, denoted by SK_f. The ciphertext corresponds to some input x chosen from the domain of f. Given SK_f and ciphertext CT_x, the user may run the decryption procedure to learn f(x). Security of the system guarantees that nothing beyond f(x) can be learned from CT_x and SK_f.
We will study how lattices can be used for the construction of functional encryption schemes. Of special interest to us will be the "learning with errors" (LWE) assumption, which enjoys strong worst case guarantees that makes it very desirable for the construction of cryptographic primitives. We will review known constructions of functional encryption from LWE, including FE for point functions or "identity based encryption", FE for linear functions or "inner product" encryption" and FE for more general circuits or "attribute based encryption for circuits". We will also discuss some open problems in this fast growing area.
Sanjam Garg
IBM Research, U S A
Title: "Candidate Multilinear Maps"
I will describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups. These new constructions radically enhance our tool set and open a floodgate of applications. I will present some of these applications.
(joint work with Craig Gentry and Shai Halevi)
Organizers
Satya Lokam (Microsoft Research India) and Vinod Vaikuntanathan (MIT and U. Toronto)
This workshop is supported by Microsoft Research and National Mathematics Initiative at IISc, Banaglore.
