spgitec-blog - Tumblr blog

[spgitec-blog]

PostQuantum Resistance

Governments and multinationals are investing large amounts of money in the construction of the quantum computer; Today IBM and Google are more advanced in this direction. These systems have become a quantum simulation. But this advance also has its drawbacks, for example, it will no longer be safe. The security of the encryption algorithms of public key or digital signature plus employees, such as RSA and DSA, using the Shor algorithm.

Faced with this situation, in 2015 the National Security Agency (NSA) of EE. UU It will publish the current terms of long-term unsecured public key cryptography that will be initiated in the search for encryption algorithms of public key. Insurance against computers, also called post-quantum. Motivated by this announcement, the National Institute of Standards and Technology (NIST) of the US launched in 2016 a public contest to identify, choose and standardize post-quantum algorithms. Systems of two types were sought: encryption and exchange of keys, and digital signature. 83 proposals from 17 countries have been submitted, of which 56 have maintained their resistance to attack with the classical systems and the quantum algorithms known at the moment. Advertising inRead invented by Teads

Mathematics plays an important role in all encryption systems of public key and digital signature, and also in postcutaneous systems. Public key systems use a key (PK) that is public to encrypt, and a secret key (SK) to decipher, which can not be inferred from the first. For the digital signature, SK and then PK are used first. The security of these systems is based on the difficulty of solving mathematical problems, we even have a computer with a large calculation capacity. For example, in the famous and ubiquitous RSA algorithm, security is based on the difficulty of factoring a number N = p * q is the product of two very large prime numbers (without knowing any of these, which have the private key (p , q)). In lattice systems, the difficult problem is finding a minimum length vector; and the so-called multivariable systems are based on the difficulty of solving systems of polynomial equations in many variables. Detail of the interior of the IBM universal computer. enlarge photo Detail of the interior of the IBM universal computer. IBM Research

These multivariable systems are used as a key in a set of low-grade polynomials (2,3,4 ..) in many variables. It works in the following way: if the public key is the polynomials F (x, y) = 3y² + 2x + y, G (x, y) = 18y³ + 12xy²-2x² + x + yy one message is M = (3, 11) the encrypted message is the result of evaluating (replacing) the message in the two polynomials, that is: (F (3,7), G (3,7)) = (44, -4418). An unauthorized person who does not have the private key has to solve the equations 3y² + 2x + y = 134, 18y³ + 12xy²-2x² + x + y = -41462 to get the original message. When the number of polynomials used and their variables grows, these are systems of very complicated equations to solve, even for a computer.

All the multivariate systems proposed to the NIST use quadratic polynomials (of degree two) in a high number N of variables (for example N = 512) except the system called DME that we have developed and patented in the Complutense University and the ICMAT, which uses polynomials in six variables of very high degree (up to 2 ^ 48) on finite bodies. This system, implemented in collaboration with the University of Zaragoza, is very fast and has the advantage over these keys. From time to time, these systems are safe against optical systems and now their resistance to attacks with the "classics" is evaluated. For now, the DME remains in the contest, as a candidate and be one of the several "winners" expected from it. According to the NIST plans, the standardization process will be completed from 2025 and will become a migration to the new cryptographic systems, to the principles of the quantum revolution. Although it is not known when to reach the most important results, all confidential data and Internet traffic will be protected from that date, in the coming years.