avendano@unizar.es
The public-key cryptosystems (based on the difficulty of factoring integers) are vulnerable to the hypothetical quantum computer, whose realization seems imminent. Anyone that is currently storing communications ciphered with those cryptosystems will be able to decode them in the (near) future. The answer to such a problem led to what is called post-quantum cryptography, whose main goal is to develop public-key cryptosystems that can be used with classical computers and that are not vulnerable to attacks with quantum computers. The american agency NIST opened recently a contest asking for such cryptosystems, with the idea of selecting and then standarizing the best for global usage.
In this talk, I am going to present the DME cryptosystem, proposed by Prof. Ignacio Luengo (Univ. Complutense de Madrid) and implemented by Miguel Marco Buzunamiz and myself (Univ. de Zaragoza). This cryptosystem changes the integer factorization problem by the problem of factoring a polynomial map as the composition of three linear and two exponential maps. Compared to the standard RSA cryptosystem, the description of DME is significantly harder, but its implementation is competitive (both in key-size and running-time), which is one of the reasons the system attracted a lot of attention in the first round of the NIST contest. Although the system has not been broken in its more general form, we have found a weakness in the way certain maps are composed, which led to a structural attack that breaks the system (as submitted to NIST) in a few minutes. The attack reduces to the computation of the intersection of a toric variety with a linear space. If time allows, I will also present the main ideas of these algebraic attacks.