Eurocrypt 2013 : Number Theory Session

The number theory session consisted of three talks. One by Joux on the DLP, one by people from Microsoft Redmond on Genus 2 curves, and one by Bouillaguet and co-workers on breaking systems based on hidden quadratic equations.  In this post I will mainly concentrate on the first one, and make a small comment on the second. The third talk was very interesting, and basically concluded that the systems considered in this work should not be considered secure.

Joux presented his work on the medium prime case of DLP in a finite field. He first outlined the basis Function Field Sieve method of Joux and Lercier for solving such DLPs: If the finite field is of size p^k, for p of size L_p^k(1/3), then one selects two polynomials f1(x) and f2(x) of degree d1 and d2 respectively such that d1*d2>k and such that

x-f1(f2(x))

is divisible, modulo p, by an irreducible factor of degree exactly k.

The attacker then selects a smoothness basis of x-a and y-a, and sets y=f2(x), and x=f1(y). With this identification the bivariate linear polynomial

x y + a y + b x + c

can be expressed either as a polynomial in x, or a polynomial in y. When both such polynomials split over the factor base one obtains a relation.

The basic idea of Joux's new method was to apply the technique used when the field can be expressed as a Kummer extension, to all extensions. Namely to fix on y=x^d1. Joux then showed that when one obtains a single relation one can amplify this to many relations using the substitution x = v X for some v. A similar trick working when we consider the other side of the relation. Thus relation finding becomes a task of taking known factorizations and matching them up. This produces a great improvement in the so-called sieving step; in fact eliminating the need for sieving entirely.

Joux ended with discussing his recent work on charactereristic two discrete logarithms; which we have discussed elsewhere in this blog. He presented a new world record; announced in the last week of solving the DLP in a finite field of 6168 bits.

In the next talk Craig Costello presented some interesting performance improvement to arithmetic on genus two curves; obtaining some very impressive results. He presented two implementations; one based on general arithmetic using a four dimensional GLV style trick, and the second based on a Montgomery ladder technique based on the Kummer surface. He left with a tantalising open problem which was to apply GLV style methods to the Kummer surface. This looks very interesting, and a possible place to start this line of work would be to see what can be done in the simpler case of elliptic curves, where both GLV and the Kummer surface are easier to understand

Day one - part one - two

The third talk of Monday was given by Chris Peikert on ring-LWE.  Lattice cryptography bases security mainly on SIS and LWE problemS. Whereas they enjoy worst-case security, this approach typically leads to constructions where key sizes and runtimes are big, roughly quadratic on the security parameter (Omega(n^2)). It turns out that their analogous on the ring  setting are more efficient (Omega(n)), so it is important to understand until what extent, without compromising security, the ring counterpart can be  employed.

A key part in the security reduction of RLWE to lattices problems is that the underlying ring should have a particular algebraic structure.  Namely, the class of rings considered are cyclotomic rings, defined as the quotient of polynomial rings with integers coefficents over  cyclotomic polynomials, (the m-th cyclotomic polynomial is that with its  roots being exactly all nth-primitive roots of unity). So unless one is able to provide a reduction for any number field, the question is, what cyclotomic rings and what representations of the  ring elements are best suitable for efficiency purposes?

Many applications  require the degree to be a power of two. This work is on extending the setting to more general cyclotomic rings.  From a practical point of view, the most obvious reason for doing so is that the security level of an application may not need to call to the next power of two in the ring dimension. Working with rings with tighter dimensions allows e.g. to have smaller keys. Also on the power of two case, improvements on  efficiency like SIMD operations cannot be applied.

Using any cyclotomic field would not comprOmise security at all, but other  difficulties arise if we do not restrict to some nicer structures. For example, reduction modulo general or irregular cyclotomic polynomials is  ususally cumbersome because the polynomial can take any shape. The  situation is different if the order is prime.

In the talk, three features were presented which in somehow also determine  the ring structure; the canonical embedding, the tensorial decomposition,  and the dual ring. A crucial quantity when trading security by efficiency is  the expansion factor of the ring; it controls the noise growth after arithmetic  operations. The size of this term can be given in different ways, for example one is tempted to consider the norm of the vector associated to the noise. This way, one is using the so-called coefficient embedding. Unfortunately this yields expansion factors depending on the cyclotomic polynomial, and they are usually quite loose, getting too large  with high composite m. Another important caveat is that security  decreases with the expansion factor. On the other hand we may use the  canonical embedding. It maps the ring element (seen as a polynomial) to the vector of its evaluation at each primitive root, seated on the complex vectorial space. A nice property is that the expansion factor is very small and independent of the base ring. One might suspect that tensorial decomposition will allow SIMD operations. The decomposition is done via an old theorem that states that the m-th cyclotomic  ring can be  expressed as an multivariate quotient depending on the factorization of m. It turns out that this characterization with a basis of the ring called 'powerful basis' renders much efficient  constructions, than if one uses the univariate version with the standard basis (sometimes called power basis). Lastly, under the canonical embedding the  cylotomic ring is not self dual. In the formalization of the RLWE problem  it was shown that the dual was necessary, and although it is possible to  get rid of it DD12, it seems better to keep it since the error tolerance  in decryption is larger when using the dual.

The take-home message of the talk was that mathematical objects (canonical embedding) and representations (tensorial bases) yields provable hardness, fast algorithms and tighter analysis.

EuroCrypt 2013: Day one, part one

Today marks the start of Eurocrypt 2013 in Athens. The first session was on lattices and the first talk was on Candidate Multilinear Maps from Ideal Lattices, which received the best paper award. This paper was also discussed in an earlier blog post as part of a study group.

The second talk was on Lossy Codes and a New Variant of the Learning-With-Errors Problem, by Nico Döttling (who gave the talk) and Jörn Müller-Quade from KIT. In the Learning With Errors problem, you are given some noisy inner products (mod q) of a secret vector with random vectors and the goal is to retrieve the secret vector (search version) or distinguish these noisy inner products from random (decision version). In certain cases (depending on the modulus q and the noise distribution) it is possible to reduce the search to the decision problem. More importantly, if the noise is taken from an appropriate Gaussian distribution, it can be shown that the average-case instances are as hard as worst-case instances through a worst-case to average-case reduction.

However, it is cumbersome to sample such Gaussian noise, and in this paper the authors examine whether it is possible to get a worst-case reduction for some non-Gaussian noise distribution. They give a new worst-case connection for LWE with uniformly distributed errors, but it comes with the drawback that the number of LWE samples that will be given out must be fixed in advance. As the paper title indicates, their proof relies on lossy codes, which is a proof-strategy that was used earlier by Peikert and Waters. Strictly speaking, they do not come with a new proof of the worst-case reduction, but use the proof for Gaussian noise in such a way that they do not require the Gaussians in the LWE instantiation.

For a fixed number of LWE samples, it is possible to write the problem in matrix form, where the matrix consists of the random vectors used in the inner products. In the original LWE variant this matrix consists of randomly drawn elements mod q. In the variant in this paper, this matrix is replaced by one from a distribution of lossy matrices, which are computationally indistinguishable from random matrices. If this lossy problem is somehow computationally easier than the standard LWE problem, this allows you to distinguish between the lossy matrices and random matrices. The main part of the paper is dedicated to showing that their specific LWE construction is actually lossy for their uniform noise distribution.

The end result is a reduction from worst-case GapSVP to the average case of their LWE variant. Compared to previous reductions, this one suffers from the loss of an additional factor m in the approximation factor for the lattice problem. It is an open problem to tighten this reduction.

Workshop on Mathematics of Information-Theoretic Cryptography

A workshop on Mathematics of Information-Theoretic Cryptography has been held this week in Leiden. The first morning started with a very interesting talk given by Amos Beimel on Multilinear Secret Sharing Schemes. He described a recent joint work with Aner Ben-Efraim, Carles Padro, and Ilya Tyomkin.   Multilinear secret sharing schemes (MSSS) can be seen as a generalization of  linear secret sharing schemes, in which  the secret is composed by some field elements instead of just one, and they are based on multi-target monotone span  program, a generalization of monotone span program. He showed, using representation of groups, that ideal multilinear p-schemes (in which the secret is composed of p field elements, for every prime p) are more powerful of ideal k-linear multilinear schemes for k<p.

The  talk  “Low Rank Parity Check Codes (LRPC) and their applications to cryptography”, by Gilles Zemor, was particularly appealing.  These codes can be seen as the equivalent of LDPC codes (Low Density Parity Check codes) for the rank metric. More precisely, a LRPC code of rank d, length n and dimension k over F_q^m,   is a code with parity  check matrix H, that is  an (n-k) x m matrix such that the subspace of F_q^m  generated by its coefficients has dimension at most d. He described how these codes can be used to define a  public key cryptosystem, with small keys and a poor structure, which is not based on the Gabidulin codes. Interestingly, as the more recent MDPC cryptosystem,  this construction can be seen as a  generalization of the NTRU cryptosystem, but with the rank metric.

The last talk of the day was given by Harald Niederreiter. He showed some applications of global function fields, i.e. algebraic function fields of one variable over a finite fields.

For me, the highlight of the third day was the talk given by Serge Fehr. He presented a joint work with Marco Tomamichel, Jedrzej Kaniewski, and Stephanie Wehner, that will be presented at Eurocrypt next week. During the talk he described a new quantum game (a monogamy-of-entangled-game) with various and important applications in cryptography. For example it is used to prove that standard BB84 QKD (Quantum Key Distribution) remains secure even when one party uses fully untrusted measurement devices.

Study Group: Non-Committing Encryption

The latest study group was presented by Arpita on the topic of non-committing encryption with material from the following papers:

• Improved Non-Committing Encryption Schemes based on a General Complexity Assumption by Ivan Damgård and Jesper Buus Nielsen
• Improved Non-Committing Encryption with Applications to Adaptively Secure Protocols by Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
• Somewhat Non-Committing Encryption and Efficient Adaptively Secure Oblivious Transfer by Juan A. Garay, Daniel Wichs, and Hong-Sheng Zhou

Non-committing encryption denotes semantically secure public-key encryption with the additional possibility of producing fake public keys and fake ciphertexts. Those should be computationally indistinguishable from real public keys and ciphertexts, respectively, but the fake ciphertexts can efficiently be opened to any message. A stronger notion is deniable encryption, where a real ciphertext can be opened to any message, and it is even possible to compute a secret key that decrypts a ciphertext to any message. Obviously, this would be helpful for individuals in jurisdictions that require key disclosure.

The main motivation for non-committing encryption (NCE) is adaptive security, that is, against an adversary that can corrupted parties in a protocol at any time in a protocol unlike a static adversary that has commit himself at the beginning. NCE can be used to achieve adaptive security in several circumstances such as secure channels, security against selective opening attacks (SOA), and oblivious transfer (implying multiparty computation). For selective opening attacks, the adversary is given a number of ciphertexts under the same public key, of which he can select some to learn the message and tge encryption randomness. A SOA-secure encryption scheme will guarantee that no information on the remaining ciphertexts can be deduced.

Non-commiting encryption was introduced by Canetti et al. in 1996. Damgård and Nielsen proved that NCE can be constructed from simulatable public-key encryption and that ElGamal achieves this property. A simulatable cryptosystem allows to generate a public key and a ciphertext without generating a secret key and inputting message, respectively, and it is possible to extract adequate generation randomness from such a fake public key or ciphertext. The construction involves the sender and the receiver agreeing on a random bit to encrypt one bit as follows: The receiver generates a real and a fake public key and sends them in random order. The sender then encrypts one out two public messages using one of the keys at random, generates a fake ciphertext for the other key, and sends both ciphertexts. If the receiver can decrypt the ciphertext corresponding to the real key to the right public message, they have both chosen the same random bit, which can be used to encrypt one bit. Otherwise, they repeat the protocol.

Unlike simple public-key encryption, this protocol requires interactivity. Nielsen proved in a paper at Crypto 2002  that non-interactive non-committing encryption implies that the secret key has to be as long as the message. However, Choi et al. introduced an NCE scheme that requires only expected two rounds, that is, it is non-interactive with high probability.

School on Information-Theoretic Cryptography

Last week the school on Mathematics of Information-Theoretic Cryptography was held at the Lorentz Center in Leiden, Netherlands. It was intended as a warm up for the workshop following next week at the same center, and that aims to bring together people working in the field, and present latest results on a variety of i-t topics.

I quite enjoyed the school and found it very rewarding, as most of the lectures took special interest in giving careful presentations, on blackboard,  with no hesitation on going into the details of what was being discussed. People in the audience feeling akin to take notes were able to do it without loosing track of what the lecturer was saying.

The school was opened by Jesper Buus Nielsen on Monday. He gave an intuitive presentation on Secure Multiparty Computation (MPC). He discussed aspects of passive security, the UC model, and the efficiency of MPC. Things like Shamir Secret Sharing, security of protocols via simulators and environments, dispute control technique, randomness extraction with  Vandermonde matrices, SIMD operations and its relation to Benes networks, and more was dissected.

Tuesday and Wednesday were dedicated to a more in-deep range of mathematical topics. Peter Beelen gave a comprehensive introduction of function fields, which constitutes one of the building blocks of algebraic geometric secret sharing. Besides it can be hard to understand for someone with a no-so-wide knowledge in Algebra, he basically started from the scratch, giving examples and intuitions on why concepts are developed in a particular way. He also settled practice exercises that were later resolved on the board. He discussed objects like valuation rings, places, formal expressions known as differentials, the Riemann-Roch theorem, Ihara's constant, and recursively constructions of tower of function fields. I think it was a meticulous introduction, and surely papers dealing with AG secret sharing are much more understandable for anyone who attended this lecture. Chaoping Xing discussed aspects of Algebraic Curves. He was mainly concerned with three applications; algebraic geometric codes (comparison and improvements on bounds of the asymptotic behaviour, and generalization of
Reed-Solomon codes), field multiplication on extension fields (alternative to convolution product in polynomial rings, defined via two maps and the Schur product, and its connection to function fields), and  lastly, perhaps a somewhat less crypto-related application, the Quasi-Monte Methods.

Carles Padro gave explicit definitions of secret sharing schemes seen as random variables, realizations of SS for general access structures, and the relation to matroids and polymatroids. Also discussed on lower and upper bounds of the Information Rate. Thursday was devoted to arithmetic SS, and was driven by Ronald Cramer and Ignacio Cascudo. They explained the Codex Framework, which tries to embody together SS schemes that are multiplicative. Many of the aspects discussed the previous days crystalized in this framework. As an aside, Ronald also informally explained the research development on the topic in, roughly, the last twenty years.

The last day, Friday, Yuval Ishai also talked about MPC and Zero-Knowledge Proofs.  He noted that historically i-t cryptography and honest majority MPC  have made use of 2PC and ZKP, whereas the other direction seems less explored. He gave high level description on several topics regarding this connection, the one I enjoyed the most was the description of the "MPC in the Head" technique.

All the material is available at the school website.

Study Group: Multinlinear Maps (II) - Application

Following on from last weeks study group on the construction of multilinear maps from ideal lattices (http://eprint.iacr.org/2012/610.pdf), this weeks study group, given by Essam and Gareth, was on applications of multilinear maps. One of the papers (appearing at Crypto later this year) this week can be found here:  http://eprint.iacr.org/2013/128.pdf. 

This paper, entitled "Attribute Based Encryption for Circuits from Multi-linear Maps", can be seen as something of a breakthrough for ABE, as previous results were significantly weaker.  We note that there is another concurrent work due to S. Gorbunov, V. Vaikuntanathan and H. Weeto appearing at STOC which achieves a similar result basing security on the Learning With Errors assumption.  At the time of writing this paper was unavailable.

Before going into details, let's talk about ABE.  Introduced by Sahai and Waters in 05, ABE comes in two distinct flavours:  key-policy and ciphertext-policy.  In the former,  secret keys are generated per boolean functions f from an allowable class of functions F.  Ciphertexts encrypting messages are associated with an attribute (assignment of boolean values) x.  Decryption of a ciphertext with a secret key sk_f is possible iff f(x) = 1.  Ciphertext-policy is the just the same with the role of key and ciphertext reversed. 

One of the main challenges has been to increase the depth of function f which can be evaluated.  Previously this was only possible for log(n) depth circuits, where n is the max length of an attribute.  The goal of this work is to realise ABE for any depth circuit.  They construct a KP - ABE and CP-ABE for any polynomially bounded depth circuit, though it should be noted that this work is only a proof-of-concept and is not necessarily intended to be efficient in any way.

They identify the main problem in previous constructions (in paticular those based on bilinear maps) as "backtracking":  lets say I decrypt a ciphertext with attribute x so I possess a secret key sk_f such that f(x) = 1.  Now consider an OR gate (in f).  When using pairings, a ciphertext which succesfully decrypts also allows us to learn information about a gate for which the ciphertext would not have succesfully decrypted since the pairing computation evaluates to the same thing on the OR gate.  Now if the gate for which said attribute would not evalute to 1 on, had fan-out higher than 1, we can potentially use this information to decrypt a ciphertext for which f(x) should evaluate to 0, but the additional information is used such that it evaluates to 1.

The beauty of multi-linear maps is that we can replace the single bi-linear computation with maps from groups e:G_i X G_j -> G_{i+j} such that 

e(g_i^a,g_j^b) = g_{i+j}^{ab}

Using what they call "move-forward-then-shift" they can avoid the backtracking issue.  Essentially, the difference lies in the fact we are now in a new group, whereas previously we applied the bilinear map once and the required value the adversary would need to cheat lied in the exponent coming from a bilinear map.   Thus backtracking is no-longer possible.