- Information for Middle and High School Researchers

# Our confidential information protected by mathematics

2018.03.03In today's convenient world, we can enjoy shopping on the Internet from the comfort of our homes. In doing so, we need to exchange important information such as credit card numbers, addresses, names, and phone numbers that we do not want to be known to anyone with malicious intent. How is this information protected? This is where "encryption" comes in, which converts information into cipher text so that its contents cannot be understood without special knowledge (keys). In these days when the importance of information security is being questioned due to such issues as the leakage of personal information, let us read from the latest papers on cryptography, which supports security closely related to our daily lives, and on the trends in mathematics that support it.

**Key delivery, which determines the security of cryptography**

The history of cryptography is said to have begun with hieroglyphics during the Babylonian period in 3000 BC. At that time, letters could only be read by a few people with special education and were a code for the majority of people. Therefore, information was encrypted (written) and deciphered using a key called "letters". As time progressed, encryption using "tools" came to be used. In the 19th century, encryption and decryption, which used to be done by hand, began to be done by "machines, In the 19th century, the use of "machines" for encryption and decryption, which had been done manually, made it dramatically more difficult to decipher. One of the most famous mechanical encryption devices is Enigma, which was used by Nazi Germany during World War II. The Enigma is a substitution-type encryption device that uses gears to replace input characters with corresponding characters. The method of using the same mechanism (key), such as a bar or device, to encrypt and decrypt, as in the Scutaree cipher and Enigma, is called "symmetric key cryptography," and was the primary method of encryption until the 1970s. However, in common-key cryptography, the sender and receiver of the cipher needed to exchange keys, and there were concerns that keys could be stolen along the way. The keys had to be passed on and off with great care at all times, and this labor became a major problem as the number of information communications increased.

**The "RSA cipher" we arrived at and the looming threat of quantum computation**

The "public key cryptography" method, which is a cryptography based on mathematics, has led to a solution to this problem. The characteristic feature of this method is that encryption and decryption are performed with different keys. The key used for encryption is called the "public key." For example, when Alice wants to send a secret message to Bob, she encrypts the message using the public key that Bob has made public. A public key that anyone can know can encrypt a message, but it cannot be decrypted (to be precise, it takes a very long time to decrypt it; see below). See below). It is like a padlock that can be closed by anyone. To decipher the cipher, you need to use a "secret key" that only Bob has. This is like the key to a padlock. By using public-key cryptography, there is no need to exchange the private key, and the risk of the private key being stolen and the cipher being deciphered is greatly reduced. The most commonly used public-key cryptosystem is the RSA cipher (initials of developers Rivest, Shamir, and Adleman), which uses the "difficulty of prime factorization. (See Alice and Bob's example.) To decipher the RSA cipher without a secret key, one would have to prime factorize an integer of about 600 digits. Even with the world's most powerful supercomputer, it is said to take more than 10,000 years to factorize these integers. Since the value of the information is lost by the time it has been deciphered, encrypted information is said to be secure in reality. In other words, the fact that "it takes time to compute" supports the security of cryptography.

However, this means that the RSA cipher can be broken if the computer's computation becomes faster. In recent years, a wave of practical applications of quantum computers, which are hundreds of millions of times faster than supercomputers, has been imminent. Fears that quantum computers may break all cryptosystems are rapidly growing, and new cryptosystems are needed to cope with this situation.

**The "key" to mathematics that surpasses computational power**

With the advent of quantum computers, which boast overwhelming computational speed, will all codes be deciphered? In fact, in recent years, a new type of encryption that is difficult to crack even with a quantum computer has been developed by applying mathematics.

One of them is the "lattice cipher. A lattice cipher is a cipher that uses the mathematical properties of a collection of regularly arranged points in space (a lattice). One of the properties used is a mathematical problem called the "Learning with Errors Problem. This is an approximate equation created by adding an Errors term to a large number of equations designed to be solved

and solve this approximated equation without error information (x_{1}, x_{2}x_{m}(to find the secret key) is extremely difficult. Although lattice ciphers have the disadvantage that the amount of information in the secret key is several to trillion times larger than that in RSA ciphers, no method has yet been found to solve them in a realistic amount of time, even with a quantum computer. This cryptography is currently being tested around the world as a highly secure cryptography.

**Made in Japan's new code**

The actual social implementation of cryptography faces a variety of problems, such as data corruption during data transmission and interception by malicious people. For example, data corruption during transmission or interception by a malicious person. To deal with this problem, it is necessary to check whether the data has changed during transmission or reception.

The new cipher with this checking function has been studied in Japan and was finally developed by the National Institute of Information and Communications Technology (NICT) in 2018. It is not only quantum resistant, but also has a security check mechanism. When encrypting data, the structural information is packed together with the ciphertext. If any discrepancies are found, decryption is aborted. Since it has been nominated as a candidate for the world standard encryption technology, research is being conducted around the world to see if there is a solution that can be decrypted in a realistic amount of time, if there is a mechanism that can be intercepted by malicious users, and if it is easy to implement in existing systems.

The development of the Internet and other means of communication and science and technology has made our lives more convenient, but at the same time, the danger of personal information being leaked to others has increased. We must continue to keep an eye on the development of mathematics and cryptography, which protect our important information.