Polynomials against quantum computers

Governments and multinationals are investing large amounts of money in the construction of the quantum computer; Today IBM and Google are the most advanced in this direction. These computers can perform quantum simulation to model complex chemical reactions, or design new drugs, operations that are beyond the reach of the most powerful binary computers. But this advance also has its drawbacks, for example, will cease to be safe the cryptographic systems used today to ensure electronic commerce and communications in the network, since a quantum computer can quickly factor the large numbers on which it is based the security of public key encryption algorithms or digital signature plus employees, such as the RSA and DSA, using the Shor algorithm.

Faced with this situation, in 2015 the National Security Agency (NSA) of the USA announced that current public-key cryptography standards are not secure in the long term and asked that the search for secure public-key encryption algorithms against quantum computers, also called post-quantum, be initiated as soon as possible. Motivated by this announcement, the National Institute of Standards and Technology (NIST) of the USA. In 2016, it launched 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 maintain their resistance to attacks with classic computers and the quantum algorithms known at the moment. 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 certain mathematical problems, even with a computer with a high calculation capacity. For example, in the famous and ubiquitous RSA algorithm, security is based on the difficulty of factoring a number N = p * q that is the product of two very large prime numbers (without knowing any of these, which would be the private key (p , q)). In grid systems, the difficult problem is to find a minimum length vector; and the so-called multivariable systems are based on the difficulty of solving systems of polynomial equations in many variables.

These multivariable systems use as a public key a set of low-grade polynomials (2,3,4 ..) in many variables. They work 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, very complicated systems of equations are obtained, 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 for 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 (like quadratic systems) and has the advantage over these that the keys are much smaller. At the moment it is believed that these systems are safe against quantum computers and now their resistance to attacks with “classic” computers is evaluated. For now the DME remains in the contest, as a candidate to be one of the several “winners” expected of it (at least, there will be one for each technology in competition). According to NIST plans, the standardization process will be completed by 2025 and a migration to the new cryptographic systems, prepared for the quantum revolution, will begin. Although it is not known when quantum computers will arrive, all confidential data and Internet traffic should be protected as of that date, prepared to withstand the quantum future.

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 )

Google photo

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

Connecting to %s