Asiacrypt 2014, Kaohsiung, Taiwan

Asiacrypt 2014 was held in Kaohsiung, Taiwan on December 7-11 2014.  There were 55 accepted papers, a very high number indeed. A good number of these papers are of interest to researchers in curves.

The conference began with the best paper Solving LPN using covering codes, presented by Qian Guo and joint work with Thomas Johansson and Carl Londahl. Here “LPN” means the “learning parity with noise” problem, which is somewhat related to the problem of decoding a random linear code over GF(2). LPN is also related to learning with errors. The paper is about the Blum-Kalai-Wasserman algorithm, and introduces covering codes in the final stage of the algorithm to reduce the size of an “exhaustive search” operation.

The next talk was Algebraic attack against variants of McEliece with Goppa polynomial of a special form by Jean-Charles Faugere, Ludovic Perret and Frederic de Portzamparc. This paper is about a “structural attack” on special McEliece keys using Groebner basis algorithms.

The paper Bivariate polynomials modulo composites and their applications by Dan Boneh and Henry Corrigan-Gibbs uses some very nice mathematics. The paper proposes to use the function f(x,y) = x^7 + 3 y^7 \mod{N}, where N is an RSA modulus, as a commitment scheme in place of traditional Pedersen commitments C(m,r) = g^m h^r. The idea that f(x,y) is a collision-resistent hash function comes from a conjecture by Don Zagier that x^7 + 3 y^7 defines an injective function \mathbb{Q}^2 \to \mathbb{Q}. The paper refers to some nice mathematics from number theory and algebraic geometry, and Henry gave a very clear talk.

Mehdi Tibouchi presented the paper GLV/GLS decomposition, power analysis and attacks on ECDSA signatures with single-bit nonce bias, with too many co-authors for me to type. It is a very interesting paper with many contributions. First, the authors study a technique due to Bleichenbacher for learning the secret key by exploiting a bias in the random nonce in ECDSA signatures (it also applies to other signature schemes such as Schorrr, ElGamal etc). This technique uses the inverse Fast Fourier Transform. They show that these ideas do lead to an attack on ECDSA signatures, though the cost is too high to be demonstrated using current computing power. Next the paper considers GLV/GLS methods for computing [k]P = [k_1]P + [k_2]\psi(P) in ECDSA, where \psi is the GLV/GLS endomorphism satisfying \psi(P) = [\lambda]P for some large integer \lambda. The paper discusses three natural approaches to compute (k_1,k_2): (1) Choose uniform k and decompose; (2) Choose k_1,k_2 uniformly in [0, 2^m) for suitable m; (3) in the case when \lambda^2 + 1 \equiv 0 \mod{n}, where n is the order of the point P, to choose k_1, k_2 uniformly in [0, \sqrt{n}). One might naively assume that all three methods are fine. But there are surprises in store! The paper shows that: (1) is vulnerable to a side-channel attack; (2) is broken by Bleichenbacher’s attack (and this can be done in practice in reasonable time); (3) is provably secure.

The next morning began with a session of three talks on elliptic and hyperelliptic curves.

Christophe Doche presented his paper On the enumeration of double-base chains with applications to elliptic curve cryptography. The idea of double-base chains is to exploit curves that have both efficient doubling and tripling operations, and to try to minimise the number of general additions. One can represent an integer k as a chain 2^{a_1} 3^{b_1} \pm 2^{a_2} 3^{b_2} \pm \cdots \pm 2^{a_l} 3^{b_l} where a_i \mid a_{i+1} and b_i \mid b_{i+1}. When this is done, the cost of computing [k]P is then a_l doubles, b_l triples, and (l-1) general additions. The fundamental problem is to find a double-base chain that gives the fastest computation of [k]P. It seems to be hard to find such a chain efficiently. Instead, one can generate a “random” integer k by generating a random double-base chain. The paper gives new methods to count the number of double-base chains for a given triple (l, a_l, b_l) and hence to get an idea of what values are required to cover all (or almost all) possible integers k. An interesting future question is to consider the issues discussed by Mehdi Tibouchi in this setting.

Chitchanok Chuengsatiansup presented joint work with Daniel J. Bernstein, Tanja Lange and Peter Schwabe on Kummer strikes back: new DH speed records. The goal is to study Kummer surface arithmetic for variable-base divisor multiplication. It turns out that the Montgomery ladder when using Kummer surface arithmetic is very suitable for 4-way vectorisation. Hence, an implementation can be done that breaks previous cycle-count records.

Huseyin Hisil presented the paper Jacobian coordinates on genus 2 curves. This joint work with Craig Costello presents beautiful new formula for divisor arithmetic on genus 2 curves. It is very surprising to me that these formulae had not been discovered before. The new formulae lead to significant speedups when performing arithmetic in the divisor class group of general curves. Of course, for many applications it is better to use Kummer surface formula (as in the previous talk), but I am sure there will be situations where the new formula are useful.

The next session, while not about curves, was of interest to this community. Rob Granger presented the paper Mersenne factorization factory, as none of the authors were able to attend. The paper is about factorising a collection of special integers of the form 2^m - 1 using the special number field sieve. The idea is to use the same sieving for one side of the algorithm, giving an overall speedup. More generally, the paper analyses situations where one could try to factor a collection of RSA moduli simultaneously. The other paper, presented by Cecile Pierrot, was joint work with Antoine Joux on finite field discrete logarithms. The paper gives some new techniques for computing discrete logs of low degree elements. The complexity of the first stage becomes O( q^6 ). The talk reported a new record-breaking computation of discrete logarithms in GF( 3^{5 \cdot 479}), which is reported in the full version of the paper here. That computation takes q = 3^5. For pairing applications one would take q = 3^6, which would give a DLP computation approximately 3^6 times slower than the record reported. This confirms that pairings using supersingular elliptic curves in characteristic 3 are not a good choice for pairing-based cryptography.

The first invited talk, by Kenny Paterson, was on Big bias hunting in Amazonia: Large-scale computation and exploitation of RC4 biases. The talk was extremely clear and well-presented. Kenny explained how RC4 biases can be exploited to obtain some realistic and significant attacks on real-world protocols. One theme of his talk was that cryptographers should try to pay more attention to what is going on in the real world, as they can make important contributions. Another was that it is difficult to bring change in the real world: “Things won’t change until you present an engineer with their password”. One can find a longer report on this lecture at the Bristol crypto blog.

Chrysanthi Mavromati presented the paper Multi-user collisions: Applications to discrete logarithms, Even-Mansour and PRINCE, which is joint work with Pierre-Alain Fouque and Antoine Joux. One of the results in the paper is a new approach to solve L discrete logarithm instances using Pollard rho in a group of size N in O( \sqrt{LN} ) group operations. Such a complexity has been previously obtained by Kuhn-Struik and Bernstein-Lange, but the new result achieves this is a slightly different way. The paper is mostly about applying similar ideas in the case of the Even-Mansour block cipher.

Nils Fleischhacker presented a paper On tight security proofs for Schnorr signatures, which continues a line of work on meta-reductions. The fundamental problem is that the security of Schnorr signatures (and many other signature schemes) is proved using the forking lemma, and so proofs are not tight. Results based on meta-reductions are intended to explain why one cannot get around this problem. Luckily it is known that there are signature schemes with tight security reductions, but they are based on other computational problems like CDH or DDH.

The rump session lacked talks on ECC, and beer.

The second invited talk was by Helaine Leggat, who is an information security lawyer in Australia. Her talk was The legal infrastructure around information security in Asia and she discussed, among other things, the processes by which nation states develop their own national laws on information security. She highlighted several different issues surrounding surveillance, including governments spying on their citizens and companies spying on their employees/contractors. She predicts “There will be a fight between states and what technology can provide”. For more thoughts on her talk see the Bristol crypto blog. Her notes and references for this talk will eventually appear on the conference webpage.

At the elaborate and extensive Chinese banquet, awards were given for the best paper and Antoine Joux was inducted as an IACR fellow.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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