Eurocrypt 2020

Eurocrypt 2020 took place online, being the first major IACR cryptography conference to be run online over zoom. The chairs did an amazing job at short notice, assisted very ably by Kevin McCurley and Kay McKelly from the IACR as Virtual Conference Administrators.

I understand there were over 1000 registrations, making it by far the largest Eurocrypt of all time. It turns out that online events are more accessible. Certainly I had not planned to fly to Europe for it, but since it was online I was able to attend.

Short videos of the talks are on youtube and are linked from the conference webpage, and the full live sessions are on the IACR YouTube channel. Unfortunately I did not attend any of the live sessions due to time-zones, but I did at least catch most of the rump session.

For the purposes of this blog, the most important session was the opening session on “Number-Theoretic Cryptography”. There was an unexpected hidden theme between two of the papers, which is the algorithm by Becker, Coron and Joux for solving subset-sum (building on the beautiful idea of Howgrave-Graham and Joux to split vectors by weight rather than length).

I now discuss the papers in this session.

  • “He Gives C-Sieves on the CSIDH” by Chris Peikert, and “Quantum Security Analysis of CSIDH” by Xavier Bonnetain and André Schrottenloher.

    These two papers are about quantum algorithms to solve the group action problem (the computational assumption underlying the CSIDH isogeny-based post-quantum key exchange protocol). Both papers use Kuperberg’s second algorithm for the hidden shift problem. The papers advance our understanding of the security of CSIDH.

    As outlined very clearly in Peikert’s talk, there are three components of such an algorithm:

    1. A quantum circuit to compute the class group action [a]*E for “arbitrary” ideal classes. This is used to create certain “labelled” quantum states (consisting of an integer, called the “label”, stored classically as bits, and a quantum state).
    2. A sieve algorithm to combine “naughty” labelled states to form “nice” labelled quantum states.
    3. A measurement process that allows to compute some bits of the secret ideal class from a nice labelled state.

    The main challenges are to get a small quantum circuit to do step 1 and to minimise the number of states needed for the sieving in step 2.

    Peikert’s paper is mainly about items 2 and 3. The paper uses “quantumly accessible classical RAM”, which means there is a storage device that stores classical bits, and one can efficiently create quantum states that are superpositions of stored values. The paper then studies the sieving process (the “collimation sieve”, which is the “C-sieve” in the title of the paper). One aim is to minimimise the total number of labelled states that need to be computed in step 1, and hence reduce the total number of quantum gates required.

    Peikert claims that if the storage is (respectively) 2^{32}, 2^{40}, 2^{48} bits, then one can attack CSIDH-512 using (respectively) 2^{18.7}, 2^{15.7}, 2^{14.1} executions of step 1. He claims that in the case of 2^{40} bits of storage this gives a quantum algorithm to break CSIDH-512 that requires 2^{60} T-gates. Officially this is below NIST level 1, though it is still unclear to me that a quantum computer with 2^{60} gates is a realistic object in the forseeable future (as far as I know, we do not currently have classical computers with 2^{60} gates).

    Peikert discusses several optimisations and also reports on his simulations (his code is available).

    Bonnetain and Schrottenloher study a different range of parameters for Kuperberg’s second algorithm. Regarding step 2 they focus on the case of small storage and aim to reduce the quantum cost of the algorithm by doing a large classical computation involving the labels. In other words, they reduce the quantum cost by increasing the classical cost. Their innovations in the sieve stage include using subset-sum algorithms (such as the one by Becker-Coron-Joux that I mentioned above) and list-merging algorithms (such as Schroeppel-Shamir). They also make progress on step 1, with new ideas to shrink the quantum circuit for computing the class group action.

    For CSIDH-512, Bonnetain and Schrottenloher claim an attack that requires only about 40,000 logical qubits and a total circuit size of approximately 2^{71.6} T-gates, while also performing a 2^{86} classical computation. Again, this is technically below the required security for NIST level 1.

    In the discussion it was noted that these papers do not “break” CSIDH, but both authors suggest the parameters should be increased. It was also mentioned that the attacks apply to CSURF. If I had been awake in the discussions I would have asked what is the security level if the Bonnetain-Schrottenloher quantum circuit is used with the Peikert sieve. Presumably this gives a further improvement of the attack.

  • “Double-Base Chains for Scalar Multiplications on Elliptic Curves” by Wei Yu, Saud Al Musa and Bao Li.

    There has been an ongoing literature on the task of computing low weight double-base chains, which are a tool to potentially speed up variable point scalar multiplication on elliptic curves. This paper, which is mostly theoretical, gives some improvements in this area.

  • “Rational Isogenies from Irrational Endomorphisms” by Wouter Castryck, Lorenz Panny and Frederik Vercauteren.

    This lovely paper gives a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves.

    For simplicity I discuss the case p \equiv 3 \mod{4}. Let E_0 : y^2 = x^3 + x be the supersingular curve with j-invariant 1728. The quadratic twist E_0^t of E_0 is isomorphic over \mathbb{F}_p to E_0.

    The paper exploits the fact that if E = [a] * E_0 for some ideal class [a] then E^t = [a^{-1}] E_0. Now suppose \tau \in End(E) is an isogeny of degree \ell such that \tau \circ \pi = - \pi \circ \tau, where \pi is the p-power Frobenius (this is a typical case). Let \phi : E \to E^t be the isomorphism over \mathbb{F}_{p^2} from E to its quadratic twist. Then \phi \circ \tau : E \to E^t is an \ell-isogeny that is \mathbb{F}_p-rational. It follows that \phi \circ \tau corresponds to an ideal class [b] such that E^t = [ab] E_0. Hence [ab] = [a^{-1}] and we can solve for [a] by computing \sqrt{[b]}.

    In short, if we are given E and want to compute [a] such that E = [a] * E_0, then it suffices to find a suitable element \tau \in End(E). The paper explains how to do this.

  • “Low Weight Discrete Logarithms and Subset Sum in 2^{0.65n} with Polynomial Memory” by Andre Esser and Alexander May.

    This paper gives the first progress on the low Hamming weight DLP for about 20 years and it is a major result. The paper is a total mind-bender, with random walks built from random walks forming rhos of rhos. A key idea is splitting by weight, which again takes us back to the Becker-Coron-Joux algorithm.

    I am sorry, but I cannot begin to summarise this paper in a few lines. Read it. Then read it again when you are stoned. Then read it again when you are sober.

The invited talks were both excellent.

  • “Mathematics and Cryptography: A Marriage of Convenience?” by Alice Silverberg.

    I watched the 44-minute pre-recorded lecture. There is also a Live talk with 30 mins presentation followed by Q&A.

    Alice told various stories of her journey through mathematics and crypto, and some of the people she has worked with. She briefly talked about her work with Rubin on compression in finite fields (algebraic tori), her work with Boneh on multilinear maps, and her work with H.W. Lenstra Jr. on the Gentry-Szydlo algorithm. Most importantly she used these stories to illustrate the importance of community, curiosity, communication, kindness, listening, and doing the right thing.

  • “Fine-Grained Cryptography: A New Frontier?” by Alon Rosen.

    The talk gave an overview of recent work on fine-grained complexity and crypto. The basic idea is this: Suppose we have a computational problem that an honest user can set up in roughly linear time O(n) but an attacker requires time O(n^k) to solve. This is polynomial time, but if k is large enough then such work may be infeasible, or at least extremely time-consuming, and that could be enough for crypto applications.

    Alon explained the k-Orthogonal Vectors (k-OV) problem, which is: Given k lists L_i, each containing n vectors in \mathbb{F}_p^d (for small p and d = O( \log(n))) to find k vectors u_i \in L_i such that \sum_{j=1}^d \prod_{i=1}^k u_{i,j} = 0. In the case k=2 this becomes the problem of finding two vectors whose Eucliden inner product is zero (i.e., the vectors are orthogonal).

    The obvious way to solve the k-OV problem is to consider all n^k combinations of vectors. The k-OV assumption is that there is no algorithm that can do much better than this.

    Impagliazzo, Paturi and Zane introduced the Strong Exponential Time Hypothesis (SETH) which is that you can’t solve k-SAT much better than expected. The SETH supports the k-OV assumption, in the sense that if there was a faster algorithm for k-OV then there would be faster algorithms for k-SAT than currently known.

    Alon then described how to get proof-of-work and one-way functions from k-OV, and said many nice things about the CRYPTO 2019 paper “Public-Key Cryptography in the Fine-Grained Setting” by Rio LaVigne, Andrea Lincoln and Virginia Vassilevska Williams. The final part of the talk was a blur of philosophical musings (and some jokes).

As always, a highlight was the rump session. There was drinking. There were cigars. There were unusual zoom backgrounds. Contacts were traced. There was a challenging quiz.

In terms of this blog, there were no rump session talks of particular relevance to ECC. Two highlights were the songs “I will survive” by Women in Theory, and “Zoom zoom zoom zoom” by Chloe Martindale. Please click here for the
Youtube link for the IACR Fellows Award Ceremony and Rump Session.

For those who wanted to visit Zagreb, don’t worry! The conference general chairs are being rewarded for their competence by being asked to run the conference again in 2021.

In the meantime, as FakeIACR quipped on twitter, I look forward to not seeing you soon at PKC and CRYPTO.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

1 Response to Eurocrypt 2020

  1. Hi Steve,
    Regarding your comment wondering if there are out there classical computers equipped with 2^60 gates, the answer (as you were guessing) is no. According to this article of the Wikipedia:
    https://en.wikipedia.org/wiki/Transistor_count
    As of today, the largest microprocessor ever built has a transistor count of less than 2^36 CMOS transistors. This is far below than 2^60 gates, where a two-input NAND gate requires 4 CMOS transistors.

    Cheers,
    Francisco

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s