Fourteenth Algorithmic Number Theory Symposium, ANTS-XIV,
University of Auckland, New Zealand
June 29 - July 4, 2020
Schedule
The conference schedule is below. The link for each talk, also giving a schedule for the conference, is available online at researchseminars.org.
For each contributed paper there will be the following activities for the audience to learn about and discuss the work:
- The pdf will be available at the conference website and at researchseminars.org at least one week before the conference.
- A pre-recorded talk of around 15-20 minutes for a general algorithmic number theory audience will be available to registered participants at least 4 days before the conference starts. This talk will introduce the general subject area, and state the main problem/result. It will not contain the technical details.
- A Zulip channel about the paper, for registered conference participants to make comments or ask questions.
- A live session of up to 25 minutes in total, which is moderated by one or two session chairs, and intended for a small expert audience who has the paper in front of them. This session will be interactive and allow for interruptions and questions. This session will not be recorded and is only open to registered conference participants. Conference participants who are unable to attend can email their comments or questions to the session chair(s) to be asked on their behalf.
- A live discussion in the "social event" slot at the end of each session, for any interested registered participants (including the authors) to discuss the papers in that conference session. This will not be recorded.
Sunday 28/Monday 29: Speaker practice room: UTC 14:00-15:00 and UTC 24:00-01:00.
Monday 29/Tuesday 30: UTC 21:00-02:00 [5 hours]
21:00-22:50: Session 1 (Chairs: Galbraith and Petit)
- 21:00-21:10 Opening remarks and welcome by Steven Galbraith and Jason Tutara
- 21:10-21:40 Love and Boneh
- 21:45-22:15 Eisenträger, Hallgren, Leonardi, Morrison and Park
- 22:15-22:30 Short break
- 22:30-22:50 Social events
00:10-02:00 Session 2 (Chairs: Creutz and Voloch)
- 00:10-00:40 Katsura and Takashima
- 00:45-01:15 Kudo, Harashita and Howe
- 01:20-01:45 Social events
- 01:45-02:00 Wrap up first day; feedback and suggestions for the rest of the conference
Tuesday 30: UTC 17:00-21:40 [4.5 hours]
17:00-18:20 Session 3 (Chairs: Fisher and Paulhus)
- 17:00-17:30 Calegari, Chidambaram and Roberts
- 17:30-18:00 Bruin and Lewis
- 18:00-18:20 Social events
- 18:30-19:00 Elkies and Klagsbrun
- 19:00-19:30 MacNeil, Jacobson and Scheidler
- 19:30-19:50 Social events
21:10-21:40 Poster session (1) (Chair: Galbraith) Chen/Lau; Sorenson; Dobson
Wednesday 1st (Canada Day) UTC 18:00-22:00 [4 hours]
18:00-19:50 Session 5 (Chairs: Ostafe and Stange)
- 18:00-18:30 Anderson, Manes and Tobin
- 18:30-19:00 Stacy
- 19:00-19:30 Sorenson, Sorenson and Webster
- 19:30-19:50 Social events
21:00-21:20 Social events
21:20-21:30 Remembering Peter Montgomery (Michael Naehrig and Joppe Bos)
21:30-22:00 Rump session (Chairs: Creutz and Voloch)
Thursday 2nd UTC 16:00-21:00 [5 hours]
16:00-17:50 Session 6 (Chairs: Castryck and Martindale)
- 16:00-16:30 Bernstein, De Feo, Leroux and Smith
- 16:30-17:00 Dina and Ionica
- 17:00-17:30 Dutour Sikirić, Haensch, Voight and van Woerden
- 17:30-17:50 Social events
19:00-19:20 Social events
19:30-21:00 Session 7 (Chairs: Broker and Vincent)
- 19:30-20:00 Rama and Tornaría
- 20:00-20:30 Costa, Kedlaya and Roe
- 20:30-21:00 Social events
Friday July 3rd UTC 14:00-19:00 [5 hours]
14:00-16:50 Session 8 (Chairs: Kohel and Streng)
- 14:00-14:30 Dwivedi and Saxena
- 14:30-15:00 Kaluderovic, Kleinjung and Kostic
- 15:00-15:20 Social events/break
- 15:30-16:00 Castryck and Vermeulen
- 16:00-16:30 Sutherland
- 16:30-16:50 Social events
18:10-19:00 Announcement of Selfridge prize, followed by business meeting
Saturday July 4th (US Independence Day) UTC 13:00-18:00 [5 hours]
13:00-14:20 Session 9 (Chairs: Fieker and Kirshanova)
- 13:00-13:30 Espitau and Kirchner
- 13:30-14:00 Coron, Notarnicola and Wiese
- 14:00-14:20 Social events
15:00-16:00 Invited talk Andrew Booker (Chair: Thomé)
16:00-16:20 Social events
16:30-18:00 Session 10 (Chairs: Aggarwal and Thomé)
- 16:30-17:00 Bootland, Castryck and Vercauteren
- 17:00-17:30 Martin
- 17:30-18:00 Social events and closing
The meeting will be followed by an online workshop on the Mathematics of Post-Quantum crypto at the following times (approximately):
- Monday 6th UTC 3am-6am
- Monday 6th UTC 9pm-midnight
- Tuesday 7th UTC 9pm-midnight
There will be a Slack channel for the event. This will be announced on the ANTS Zulip channel. Zoom links will be posted to the Slack channel.
Programme:
Monday 6th UTC 3am-6am:
- 3:00 Steven Galbraith (University of Auckland)
Welcome and housekeeping - 3:05 Daniel J. Bernstein (University of Illinois at Chicago and Ruhr University Bochum) and Tanja Lange (Eindhoven University of Technology)
Exploring the parameter space in lattice attacks
Abstract: The standard framework for attacking a lattice-based cryptosystem gives the attacker a huge (and recently expanded) space of lattices to choose from. This talk will survey open problems regarding the analysis of minimum costs within this space.
Reading:
Section 6 of https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf
https://hyperelliptic.org/tanja/vortraege/20200219.pdf
https://www.youtube.com/watch?v=iAjkEF0x5qw
https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/pattern.ps
https://iacr.org/archive/crypto2007/46220150/46220150.pdf
- 04:00 Ron Steinfeld (Monash)
MPLWE hardness
Abstract: We review a structured variant of the Learning With Errors (LWE) called Middle-Product LWE (introduced in [RSSS17]) and its related PSIS problem [L16], that can be viewed as variants of the classical LWE and SIS lattice problems over (*non*-quotient) polynomial rings Z_q[x], their motivation as a "security-risk vs. performance" balamce, and their hardness reductions from the hardest quotient-ring variants of LWE/SIS in a large family of quotient rings, and discuss some related open problems.
Main References:
[RSSS17] M. Rosca, A. Sakzad, D. Stehle, R. Steinfeld. Middle-Product Learning With Errors. In CRYPTO 2017. Available at http://eprint.iacr.org/2017/628
[L16] V. Lyubashevsky. Digital Signatures Based on the Hardness of Ideal Lattice Problems in all Rings. In ASIACRYPT2016. Available at http://eprint.iacr.org/2016/796
- Discussion/talks to be arranged.
- 9:00 Chloe Martindale (Bristol)
Cryptanalysis of SIDH-style schemes under torsion point attacks
Abstract: In this talk we will discuss recent advances in torsion-point attacks on SIDH-style schemes. I will first present some of the ideas in [1], and then open the floor to discussion on two open problems stemming from this paper. Both open problems are inspired by utilizing the notion of 'insecure starting curves' for an SIDH-style protocol, as discussed in Section 4 of [1]. These curves are called 'insecure' because, if they were used as the starting curve in an SIDH protocol (from which Alice and Bob compute their secret isogenies), then by exploiting the torsion point information the attacker could recover the secret significantly faster than with a generic meet-in-the-middle or claw-finding type algorithm.
The first open problem I'd like to discuss pertains to proving results on (in)security of SIDH via these torsion-point attacks. The insecure starting curves are characterized by having relatively small non-scalar endomorphisms (of norm less than p^1/2). A low-degree isogeny (degree at most about p^1/16) from the curve of j-invariant 1728 to an insecure starting curve could give an attack on SIDH. The question I would like to discuss is: would it be possible to extend Love and Boneh's techniques from their ANTS paper [2] to prove (non) existence of an insecure curve within range of j-invariant 1728?
The second open problem I'd like to discuss is of a more cryptographic nature: is there a meaningful backdoor construction that makes use of these insecure starting curves? Or of insecure base field primes (also discussed in [1, Section 4])?
This is joint work with Kutas, Panny, Petit, and Stange.
Reading:
[1] Kutas, Martindale, Panny, Petit, and Stange, Weak instances of SIDH variants under improved torsion-point attacks, https://eprint.iacr.org/2020/633 (Especially Section 4)
[2] Love and Boneh, Supersingular Curves With Small Non-integer Endomorphisms, https://arxiv.org/abs/1910.03180
- 10:00 Wouter Castryck and Fre Vercauteren (Leuven)
Recent results on CSIDH
Abstract: We will discuss three recent joint works, with Lorenz Panny, Jana Sotáková resp. Thomas Decru. The first work explains how knowledge of a single non-Fp-rational endomorphism of a supersingular elliptic curve E / Fp typically suffices to find the exact location of E in the CSIDH graph. In particular, this observation applies to CM-constructed curves, and as a result such constructions are not useful for hashing into the CSIDH graph, a statement which can be seen as the Fp-version of Love and Boneh's work, presented at ANTS last week.
The second work concerns a general observation on the action of the class group Cl(O) of an imaginary quadratic order O on Ell_q(O,t), the set of elliptic curves over Fq with endomorphism ring O and trace of Frobenius t. We show that the quadratic characters of Cl(O), given to us by genus theory, can be computed directly on Ell_q(O,t). More precisely, given a quadratic character chi and two elliptic curves E and E' = [a]*E in Ell_q(O,t), connected by a secret ideal class [a], we explain how to compute chi([a]) without knowledge of [a].
The third work discusses a new method for computing chains of N-isogenies between elliptic curves over any field, where N > 1 is an integer. The method avoids the costly task of sampling random N-torsion points at each step. Concretely, we show that for any N there exists a concrete formula having the following two properties. Firstly, given an elliptic curve E and a point P of order N, the formula produces the coordinates of a point P' on E' = E/(P), also of order N and such that the composition E -> E/(P) -> E'/(P') is a cyclic N^2-isogeny. Secondly, the formula is a basic arithmetic expression in the coefficients of E, the coordinates of P, and a certain "radical", i.e., the N-th root of another basic expression in the said coefficients and coordinates. The formula can be applied recursively and is especially interesting over finite fields Fq with gcd(N-1, q) = 1, where extracting Nth-roots is easy.
We will mainly spend time on the last two works, for which we recommend the following background material:
[1] W. Castryck, J. Sotáková, F. Vercauteren, Breaking the decisional Diffie-Hellman problem for class group actions using genus theory, see https://eprint.iacr.org/2020/151
[2] M. Streng, Generators of the group of modular units of Gamma^1(N) over the rationals (mainly Section 2), see https://arxiv.org/pdf/1503.08127.pdf
- Discussion/talks to be arranged.
- 9:00 Elena Kirshanova (Immanuel Kant Baltic Federal University)
Open questions in lattice-based cryptanalysis
Abstract: In this talk I'll give a list of my favourite open problems that concern algorithms (classical and quantum) for hard lattice problems. Topics I aim to discuss are targeted towards cryptanalysis of post-quantum lattice-based primitives and include: the shortest vector problem for ell_inf. norm (see [1]), combinatorial algorithms for the LWE problem [2], potential venues to explore quantum hardness of LWE [3], [4].
[1] https://arxiv.org/abs/1801.02358
[2] https://eprint.iacr.org/2015/552.pdf
[3] https://arxiv.org/abs/1710.08223
[4] https://arxiv.org/abs/1702.08255
- Discussion/talks to be arranged.
- 11:00 Mehdi Tibouchi (NTT Labs)
Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices