Eurocrypt 2021 was held as a hybrid conference, with some participants in-person in Zagreb and some online. I was one of the ones joining the conference by Zoom and Zulip. As always in this blog I focus on talks and news most relevant for elliptic curve fans.
For each accepted paper there was a short (20-30 minutes) video available in advance of the conference on the conference website, and also a short live Q&A session that is immortalised on the IACR youtube channel.
There were two invited talks:
Craig Gentry’s talk “A Decade (or So) of Fully Homomorphic Encryption” (FHE) gave an overview of work on FHE, the current main applications of it, and possible future directions. He listed privacy preserving genome association, neural nets, and private information retrieval as three major application areas. He classified FHE schemes into four “generations”, the fourth of which is the CKKS (Cheon, Kim, Kim, Song) approach to FHE for floating point numbers. He gave an abstract formulation of FHE based on the Rothblum generic approach and showed how this seems to inevitably leads to several of the main schemes. Several times he challenged the community to construct FHE schemes not based on lattice assumptions, stating his conviction that lattices and FHE are not “soulmates” (but he is not willing to die in duel over this).
Sarah Meiklejohn cleverly tricked the audience into attending a talk on blockchain by using the title “An Evolution of Models for Zero-Knowledge Proofs”. The talk covered a wide range of applications and aspects of zero knowledge proofs, in particular a detailed discussion of the dependence on a common random string (CRS) and various trust models relating to the generation of the CRS.
The papers “Non-Interactive Zero Knowledge from Sub-exponential DDH” by Jain and Jin, “On the (in)security of ROS” by Benhamouda, Lepoint, Loss, Orrù and Raykova, and “New Representations of the AES Key Schedule” by Leurent and Pernot, were chosen for the Best Paper Awards. The first of these explicitly mentions elliptic curves: They require the sub-exponential hardness of DDH, which is only plausible for (non-pairing) elliptic curves. The paper is about Statistical NIZK arguments and Zaps.
Moving on to the rest of the conference program, I mention the following papers.
“Analysing the HPKE Standard” by Alwen, Blanchet, Hauck, Kiltz, Lipp and Riepel. The paper introduces the notion of “nominal group” to handle groups of non-prime order (such as Curve25519 and Curve448).
“Compact, Efficient and UC-Secure Isogeny-Based Oblivious Transfer” by Lai, Delpech de Saint Guilhem, and me. The paper shows how a special property of CSIDH (that ) can be used to construct a two-round oblivious transfer (OT) scheme. The paper has a fully UC-secure 3-round version. In the live Q&A session, Lai announced that the paper has a “fixable bug” that means the fully secure version requires 4 rounds. Keep an eye on eprint for an updated version.
“One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols” by Kutas, Merz, Petit and Weitkämper. The aim of the paper is study a group action (one can also view it as being a variant of the hidden number problem) in the SIDH setting, so that the Kuperberg-type hidden shift quantum algorithm (as applies to CSIDH) can also be applied to SIDH. The paper shows how to implement this in the case of overstretched SIDH parameters. These overstretched SIDH parameters are already known to be broken due to an attack by Petit. The method of the paper currently has no impact on the security of SIDH.
“Pre-Computation Scheme of Window -NAF for Koblitz Curves Revisited” by Yu and Xu is about efficient discrete-log crypto using elliptic curves. Sadly there were technical problems during the live session and so Yu was unable to answer questions. Since -NAF window methods have been studied for decades one would not expect major progress, but this paper gives a substantial speedup over the previous state-of-the-art. This is done by giving improved operation counts for computing on Kohel’s -model of elliptic curves, and by organising the precomputation stage for the window method more effectively. Combined, these methods allow to potentially go as far as windows of length .
“Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem” by Costello, Meyer and Naehrig is about choosing primes suitable for efficient implementation of B-SIDH and SQI-Sign. The problem is to construct primes such that and are very smooth.
“Delay Encryption” by Burdges and De Feo has the best pre-recoded video — Watch it now! (At least, the first 5 minutes.) The paper is about delay functions based on sequential computation of isogenies.
“On Bounded Distance Decoding with Predicate: Breaking the Lattice Barrier for the Hidden Number Problem” by Albrecht and Heninger. The paper is about lattice algorithms for bounded distance decoding (BDD) by reducing to unique-SVP using the embedding technique and then applying enumeration or sieving. The additional feature is the use of a predicate that identifies the unique desired solution. This predicate naturally arises in problems like the hidden number problem (HNP) where the hidden number is the solution to a instance of the ECDLP. The main motivation of the paper is side-channel attacks recovering ECDSA private signing keys from known nonce bits.
“Classical vs Quantum Random Oracles” by Yamakawa and Zhandry discussed separations between the random oracle model (ROM) and the quantum random oracle model (QROM). They show a signature scheme that is secure in the ROM but insecure in the QROM, but as is to often the case with separations it is an artifial scheme that outputs the private key when a query is made on a certain type of input. The paper then gives positive results on Fiat-Shamir signatures and Full-Domain-Hash signatures (and more).
The Rump Session was entertaining. For readers of this blog the most interesting announcement was about the solution to the $5000 $IKE challenge. The talk was given by Craig Costello, who is one of the founders of the challenge. The challenge was solved by Aleksei Udovenko and Giuseppe Vitto. Interestingly, their approach uses the classic meet-in-the-middle approach (as mentioned in the original SIDH paper by Jao and De Feo) rather than the van Oorschot and Wiener (vOW) approach. The classic meet-in-the-middle approach is a time-memory tradeoff and so requires very large storage, whereas the vOW method is a low storage random walk method (but with higher time complexity). A paper is now on eprint that explains the computation and a number of optimisations. The $50,000 challenge is still waiting to be claimed!
— Steven Galbraith