ASIACRYPT 2017

ASIACRYPT 2017 took place in Hong Kong and had a large number of talks with elliptic curve and/or number-theoretical content.

The three invited talks were:

  • Dustin Moody The ship has sailed: the NIST Post-Quantum Cryptography “competition”. This talk gave a summary of the NIST post-quantum crypto standardisation process. The deadline for submissions was only 3 days before the conference so there had not been enough time yet for NIST to determine which submissions were “complete and proper” according to their criteria. Hence the talk did not list the actual submissions or give any details of particular submissions. However, it is known that there is one supersingular isogeny (SIDH) submission to the process.

    Mostly Dustin discussed the process up to this point, and the expectations of NIST for the coming stages of the process. Proposals were invited for either signature schemes or else public key encryption/key encapsulation schemes. Dustine emphasised that there is no single technology that provides all the desired features (“no silver bullet”) and that post-quantum crypto is a complex area that is still actively being researched. As a result, NIST is expecting to standardise several different schemes in each category.

    The slides of Dustin’s talk are here.

  • Huaxiong Wang Combinatorics in Information-Theoretic Cryptography surveyed how various areas of combinatorics have been used in various ways in crypto.
  • Pascal Paillier White-box Cryptomania explained the concept of white-box crypto and urged theoretical researchers to get involved in this area. He reported on the recent WhibOx challenge, all submissions to which were broken. It is fair to say that Pascal received vigorous questioning after his talk, and that several individuals in the audience were not convinced by his arguments.

    Two elliptic curve papers were highlighted in the “best paper” and “invited to Journal of Cryptology” category, and even the SNARKs paper (see below) uses pairings:

    • Steven D. Galbraith, Christophe Petit and Javier Silva Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems. I have a conflict of interest, so I won’t say too much about this paper. It is about post-quantum signatures from isogenies. The main contribution is to give a scheme based on the general endomorphism/isogeny problem, rather than the “special” isogeny problem used in SIDH key exchange. I should mention that the signature is not very efficient and is not recommended for practical use. The talk was presented by Javier.
    • Sabyasachi Karati and Palash Sarkar Kummer for Genus One over Prime Order Fields. This paper is about efficient “x-coordinate only” type arithmetic on elliptic curves. The performance results are excellent. The natural question is how this relates to Montogomery curves.
    • Behzad Abdolmaleki, Karim Baghery, Helger Lipmaa and Michal Zajac A Subversion-Resistant SNARK.

    Finally, there were many other contributed talks of interest to a mathematical audience.

    • Dominique Unruh Post-Quantum Security of Fiat-Shamir discussed the Fiat-Shamir transform in the quantum random oracle model. Previous work has given more complex transforms that turn an interactive sigma protocol (identification scheme) into a non-interactive signature scheme. Unruh’s result is that if the public key is “lossy” (he calls it “dual-mode hard instance generator”) then the basic Fiat-Shamir transform can be applied. For a similar result see Kiltz, Lyubashevsky and Schaffner eprint 2017/916.
    • There was a session on lattices, with several papers about algorithmic results and/or hardness. It comprised: Martin R. Albrecht and Amit Deo Large Modulus Ring-LWE >= Module-LWE; Martin R. Albrecht, Florian Göpfert, Fernando Virdia and Thomas Wunderer Revisiting the Expected Cost of Solving uSVP and Applications to LWE; Qian Guo, Thomas Johansson, Erik Mårtensson and Paul Stankovski
      Coded-BKW with Sieving; Thomas Prest Sharper Bounds in Lattice-Based Cryptography using the Rényi Divergence.

    • There was a whole session on Homomorphic Encryption and a whole session on Pairings. In particular, Jens Groth gave a lecture presenting two “uber assumptions” for pairing-based crypto which provide the “best” targets for cryptanalysis.
    • Martin Roetteler, Michael Naehrig, Krysta M. Svore and Kristin Lauter Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. This papers counts the number of Toffoli gates to perform elliptic curve arithmetic over a finite field of real-world size on a quantum computer. This therefore gives an estimate of the number of gates required to run Shor’s algorithm for ECDLP.

    • Joost Renes and Benjamin Smith qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs gives a signature scheme suitable for x-coordinate-only arithmetic. Signature verification in ECDSA requires computing [s]P + [c]Q and checking if this is equal to R. The new scheme computes x( [s]P ) and x( [c]Q ) using ladder algorithms and then cleverly checks if x(R) can be equal to either x( [s]P + [c]Q ) or x( [s]P - [c]Q ). The scheme can be used for elliptic curves or Kummer varieties of hyperelliptic curves. They note that FourQ is faster, but FourQ uses special curves.
    • Craig Costello and Hüseyin Hisil A simple and compact algorithm for SIDH with arbitrary degree isogenies discussed doing SIDH with isogenies of degree \ell > 3. Currently there is no application for this question, but the paper is nice anyway.
    • Christophe Petit Faster Algorithms for Isogeny Problems using Torsion Point Images introduces a very interesting and original idea to cryptanalyse the SIDH problem. In particular, his result uses the auxiliary points that are one of the concerning elements of the SIDH problem. The method does not succeed in breaking the current schemes, but would break variants of SIDH with “unbalanced” parameters.
    • Rex Fernando, Peter M.R. Rasmussen and Amit Sahai Preventing CLT Attacks on Obfuscation with Linear Overhead gave an approach to prevent an attack on the Coron-Lepoint-Tibouchi multilinear map. This seems to be a very interesting result.

    — Steven Galbraith

    Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s