Elliptic curve cryptography (ECC) is a widely used public key cryptosystem. The security of ECC relies on the difficulty of the elliptic curve discrete log problem (ECDLP). Isogenies are morphisms of curves that can be used to transfer instances of ECDLP between elliptic curves. Suppose that we suspect that some proportion of curves are "weak" in the sense that the ECDLP can be solved quickly. To avoid an attacker moving the ECDLP to a weak curve, we would want to use curves for which it difficult to transfer the ECDLP. In this talk we will introduce the notion of an "isolated" curve. These are curves which do not admit many computable isogenies which obstructs the transferring of the ECDLP.

A.S. will give some remarks (joint work with Hendrik Lenstra) on homomorphic encryption schemes of Smart-Vercauteren and Gentry-Halevi.

S.S. will discuss the paper "A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes" by Martin Albrecht, Shi Bai, Léo Ducas, which is available at: https://eprint.iacr.org/2016/127.pdf

We will complete our discussion of the quantum algorithm to
compute the unit group of a number field. We will then discuss
applications by Biasse and Song to compute class groups and generators
of principal ideals. The paper of Biasse and Song is available on my
webpage,

http://public.csusm.edu/ssharif/crypto

We will complete our discussion of Shor's algorithm for
factoring integers. Then we will begin discussing Hallgren's quantum
polynomial-time algorithm for solving Pell's equation x^2 - dy^2 = 1.
The paper can be found at

http://public.csusm.edu/ssharif/crypto/

Hallgren's idea is to adapt Shor's algorithm to estimate the regulator
of Q(\sqrt{d}), and recover a fundamental unit from the regulator. This
algorithm also provides the main ideas in the quantum unit group
algorithm of Eisentr\"ager, Hallgren, Kitaev, and Song.

Computing the Unit Group of a Number Field

Starting from Pell’s equation and units in real quadratic fields, we will discuss the problem of computing the unit group of a number field. This will lead to a discussion of the Hidden Subgroup Problem, which arises in many quantum algorithms.  We will discuss recent work of Eisentrager, Hallgren, Kitaev, and Song, and of Biasse and Song, giving a quantum algorithm for this problem that runs in polynomial time.