Academic Year 2018-2019
- 06/06/19 - 9:30-10:20 - RH 510R - Quantum computing and Grover's algorithm - Shahed Sharif
-
Given a database of $N$ entries of which exactly one satisfies some
easily checked condition, classically it takes $O(N)$ trials to find the
satisfying entry. Grover's algorithm is a quantum algorithm which
reduces the work to $O(\sqrt{N})$ trials. One consequence is that in the
post-quantum regime, hash functions and symmetric ciphers only provide
half the security (measured as the log of the number of trials) as
currently provided. In this talk, we will give a brief description of
Grover's algorithm, including all of the necessary background in quantum
computing.
Notes are available here.
- 05/23/19 - 9:30-10:20 - RH 510R - The Charles-Goren-Lauter Hash Function - Travis Scholl
-
In this talk we will summarize the Charles-Goren-Lauter hash function that is built on isogeny graphs of supersingular curves. We will also look at the quaternion analogue, which is broken. We will attempt to explain why breaking the quaternion model does not immediately break the isogeny model.
Notes are available here.
- 05/10/19 - 11:00-11:50 - PSCB 220 - The Humbert Invariant and Isogeny Graphs of Abelian Surfaces - Shahed Sharif
-
In a series of papers, Kani studies elliptic subcovers of genus 2 curves. This talk will focus on summarizing this work and it's applications to a recent question of Galbraith concerning isogeny graphs of abelian surfaces. Let A be a Jacobian of a curve of genus 2 which is isogeneous, but not isomorphic, to a product of elliptic curves. Galbraith's question is how "far" is A from a product of elliptic curves in the $\ell$-isogeny graph for a small prime $\ell$.
Notes are available here.
- 04/26/19 - 11:00-11:50 - PSCB 220 - Multilinear Cryptography using Nilpotent Groups - Alice Silverberg
-
In a recent paper, Kahrobaei, Tortora, and Tota proposed a multilinear cryptosystem using nilpotent groups. This talk will be an exposition of that paper which is available at https://arxiv.org/abs/1902.08777.
- 04/19/19 - 11:00-11:50 - PSCB 220 - Smoothing Ideals in Quaternion Algebras - Travis Scholl
-
In this talk we will go over one an algorithm of Kohel-Lauter-Petit-Tignol that, given a left ideal for a maximal order in a quaternion algebra, returns an equivalent left ideal with $\ell$-power reduced norm (The preprint can be found here: https://arxiv.org/pdf/1406.0981.pdf). This algorithm was mentioned in the previous talk as a supplementary algorithm to the reductions between certain computational problems. If there is time, we will also discuss a recent signature scheme proposed by Galbraith-Petit-Silva based on this algorithm.
Notes are available here.
- 04/12/19 - 11:00-11:50 - PSCB 220 - Computing Supersingular Isogenies and Endomorphism Rings Part 2 - Shahed Sharif
-
We will continue discussing the paper by Eisentraeger-Hallgren-Lauter-Morrison-Petit (available at https://eprint.iacr.org/2018/371). In this part of the talk, we will focus on the reductions between the major problems. We will also outline the supplementary algorithms used as a black box in these reductions.
- 04/05/19 - 11:00-11:50 - PSCB 220 - Computing Supersingular Isogenies and Endomorphism Rings - Shahed Sharif
-
In this talk we will review a recent paper by Eisentraeger-Hallgren-Lauter-Morrison-Petit (available at https://eprint.iacr.org/2018/371). This paper gives reductions between several important computational problems including finding a path in the $\ell$-isogeny graph between two supersingular elliptic curves, and computing the endomorphism ring of a supersingular elliptic curve curve. This work requires some background on quaternion algebras which can be in Voight's book https://math.dartmouth.edu/~jvoight/quat-book.pdf.
Notes are available here.
- 03/15/19 - 11:00-11:50 - PSCB 220 - A Discussion on Some Open Problems - Travis Scholl
-
This talk will be more of a discussion on some open problems we have seen so far. It should be independent of the previous talks. We will focus on a few of the problems on class groups and isogenies referred to in the Altug-Chen paper discussed on 2/22/19. The preprint is available here: https://eprint.iacr.org/2018/926 and notes from the previous talk can be found here. The problems we will focus on are finding an elliptic curve with a specified endomorphism ring, and finding l-isogenies over composite rings.
Notes are available here.
- 03/08/19 - 11:00-11:50 - RH 306 - Trilinear maps for cryptography Part 1 - Ming-Deh Huang
-
Cryptographic applications of multilinear maps beyond bilinear pairings were first proposed in the work of Boneh and Silverberg. However the existence of cryptographically interesting $n$-multilinear maps for $n > 2$ remains an open problem. Very recently Lin and Tessaro showed that trilinear maps are sufficient for the purpose of achieving indistinguishability obfuscation. This striking result put spotlight on the following question: can a cryptographically interesting algebraic trilinear map be constructed? In this talk we discuss a method for constructing such a trilinear map, and present concrete candidate trilinear maps which involve Weil descent and the Jacobian varieties of hyperelliptic curves. A preprint is available here: https://arxiv.org/abs/1810.03646.
Slides are available here.
- 03/08/19 - 12:00-12:50 - RH 306 - Trilinear maps for cryptography Part 2 - Ming-Deh Huang
-
This talk will be a continuation of the previous talk. A preprint is available here: https://arxiv.org/abs/1810.03646.
Slides are available here.
- 03/01/19 - 11:00-11:50 - PSCB 220 - Quantum resistant code-based cryptosystems: the McEliece cryptosystem and its variants - Jon-Lark Kim
-
The McEliece cryptosystem is the first code-based public key cryptosystem proposed by Robert McEliece in 1978 a few years after the appearance of RSA. The original McEliece cryptosystem uses binary Goppa codes which are a subclass of Algebraic Geometric Codes and it is still unbroken under quantum attack. In this talk, we introduce basic facts about coding theory and discuss various code-based public key cryptosystems including our new cryptosystem McNie, which is a combination of the McEliece cryptosystem and the Niederreiter cryptosystem.
Note are available here. Slides are available here.
- 02/22/19 - 11:00-11:50 - PSCB 220 -
Altug-Chen Candidate Group with Infeasible Inversion - Travis Scholl
-
A group where finding inverses is hard can be used for many cryptographic constructions. In this talk we will discuss a candidate construction by Salim Ali Altug and Yilei Chen of a group where finding inverses is supposed to be difficult, see https://eprint.iacr.org/2018/926. Their construction works by representing the class group of a quadratic imaginary field as an isogeny graph of an elliptic curve over the ring Z/NZ where N is a product of two primes. After going over the basic constructions, we will discuss some open problems relating to the security of the construction.
Notes are available here.
- 02/08/19 - 11:00-11:50 - PSCB 220 - Gentry-Gorbunov-Halevi Multilinear Map Scheme Part 2 - Shahed Sharif
-
A continuation of the previous talk on the Gentry-Gorbunov-Halevi multilinear map.
Notes are available here.
- 02/01/19 - 11:00-11:50 - RH440R - Gentry-Gorbunov-Halevi Multilinear Map Scheme Part 1 - Travis Scholl
-
In this talk, we will summarize a candidate multilinear map construction due to Gentry-Gorbunov-Halevi (GGH15). While the original key exchange protocol using GGH15 is broken, new safeguards have recently been proposed which aim to prevent this and other ``zeroizing'' attacks. Our goal will be to understand the construction, attack, and proposed safeguards.
Notes are available here.
- 01/25/19 - 11:00-11:50 - RH440R - Garg-Gentry-Halevi Multilinear Map Schemes Part 2 - Shahed Sharif
-
A continuation of the previous talk on the Garg-Gentry-Halevi multilinear map. We finish our description of the scheme, and describe some attacks on it.
Notes are available here.
- 01/11/19 - 11:00-11:50 - RH440R - Cryptographic Applications of the Weil Pairing - Travis Scholl
-
In this talk we will introduce the Weil pairing on an elliptic curve and give several cryptographic applications. We will review the argument of Boneh and Silverberg which suggests that this kind of pairing does not exist naturally on higher dimensional varieties. We will also look at some constructions of pairing-friendly elliptic curves.
Notes are available here.
- 12/07/18 - 10:00-11:50 - RH340P - Garg-Gentry-Halevi Multilinear Map Schemes - Shahed Sharif
-
Despite widespread interest in cryptographic multilinear maps since Boneh-Silverberg's 2003 paper, very few candidate maps have been discovered. The first serious candidate was a scheme of Garg-Gentry-Halevi (GGH), which is based on ideal lattices in cyclotomic number rings. While the scheme was later shown to be broken, the only other candidate schemes are hardened variants of GGH. We give a relatively detailed description of the GGH multilinear map.
Notes are available here.
- 11/20/18 - 3:00-3:50 - RH340P - An Introduction to Cryptographic Multilinear Maps - Travis Scholl
-
Multilinear maps is a new hot topic in cryptography because they offer a significant number of applications. The main open problem in this area is constructing a secure and efficiently computable multilinear map. In this talk, we introduce cryptographic multilinear maps, go through several applications, and then discuss some possible obstructions to constructing one. The main reference for this talk is the paper "Applications of Multilinear Forms to Cryptography" by Dan Boneh and Alice Silverberg.
Notes are available here.