본문 바로가기 메뉴바로가기

NIMS-National Institute for Mathematical Sciences South Korea

korea

Development of Practical Special-Purposed Cryptographic Algorithms based on Mathematical Hard Problems

구글로 퍼가기 프린트하기

Development of Practical Special-Purposed Cryptographic
Algorithms based on Mathematical Hard Problems

Development of a lightweight cryptographic algorithm for internet security in the Internet of Things, based on mathematical hard problems that are resistant to quantum computing Design of a specialized cryptographic algorithm using lightweight cryptographic algorithms, and proof of the safety of the above as an encryption method

Research

  • The RSA and ECC public-key cryptographic algorithms, currently the most widely used methods to ensure internet security over both wired and wireless connections, depend for their integrity on the intractability of certain mathematical hard problems (prime factorization and discrete logarithms, respectively). However, once quantum computing is developed to a widely usable state, this property of intractability becomes obsolete, and new measures must be taken to ensure safety during the Post-Quantum age.
    • prime factorization : obtaining the prime factors of a given composite number
    • Prime factorization is not difficult for small numbers such as 6=2․3, but it is well established that factorization of large numbers over 300 digits (using the decimal system) is at best difficult with current levels of computing power. Researchers have been able to solve the prime factorization problem for numbers of up to 232 digits (RSA-768).
    • , where a finite group G and its generators and are given.
  • All information transmitted from the "smart" devices now ubiquitous in the Internet of Things (IoT) is vulnerable to being tapped, counterfeited or corrupted, and due to common features of such devices (small size, high energy efficiency, etc) that limit their computing power, they are not able to make use of the traditional cryptographic algorithms. Therefore, it is imperative that lightweight cryptographic algorithms be developed especially for use on lightweight devices.
  • Side-channel attacks, which use side information generated by passage of data through lightweight devices to recover the private key, are at least as detrimental to the security of "smart" device transmissions as mathematical weaknesses in the cryptographic algorithm itself. Most domestically used block cipher algorithms, including the industry standard SEED, the government standard ARIA, the international standard AES, as well as the public-key algorithms RSA and ECC, have security flaws that allow the private key to be revealed within seconds through side-channel attacks. Therefore, all research on new cryptographic algorithms must be backed up by concurrent efforts to develop countermeasures against side-channel attacks.
    • Side-channel attacks: a method by which the private key or other data is reverse-engineered from physical effects of the security algorithm on the sensor node or smart card, through fluctuations of energy consumption of the circuit or of electromagnetic fields.
    News reports on cases of successful hacking of encrypion keys through side-channel attacks on IC cards, Example of a Side-Channel Attack
    News reports on cases of successful hacking of encrypion keys through side-channel attacks on IC cards, Example of a Side-Channel Attack
  • While public-key cryptographic algorithms use mathematical functions (i.e., trapdoor one-way functions), quantum cryptography uses physical techniques. Current cryptographic algorithms can be cracked without disturbing the channel of communication, but quantum cryptography requires a bidirectional connection between the quantum cryptographic hardware devices, not only making it much harder for the hacker to escape detection mid-signal, but making it impossible to read any leaked data. Stream ciphering, a traditional cryptographical method that relies on a similar principle to quantum cryptography, can generate a stream of data counted in GB/sec with a CPU costing 200 dollars, but by quantum cryptography, 50 thousand dollars worth of dedicated hardware can generate a stream of only one-millionth that volume. Therefore, it can only be concluded that the alternate solution to safe public-key cryptographic algorithms can only be found in mathematical hard problems resistant to quantum computing. Stream ciphering, a traditional cryptographical method that relies on a similar principle to quantum cryptography, can generate a stream of data counted in GB/sec with a CPU costing 200 dollars, but by quantum cryptography, 50 thousand dollars worth of dedicated hardware can generate a stream of only one-millionth that volume. Therefore, it can only be concluded that the alternate solution to safe public-key cryptographic algorithms can only be found in mathematical hard problems resistant to quantum computing.

Expected effect

  • The mathematical hard problems underlying the safety of the RSA and ECC public-key cryptographic algorithms, currently the most widely used methods to ensure internet security over both wired and wireless connections, are not resistant to quantum computing; therefore, the development of alternative methods of encryption holds enormous significance as a fundamental technology to be given priority.
  • In particular, the solution to systems composed of multivariate quadratics has been defined as NP-complete, and there is no quantum algorithm that can crack it. At the same time, encryption processes using such systems deal with only multiplications in a small finite field and require much less computing power than either the RSA or ECC algorithms, which require modular reduction of large numbers or complex operations in an elliptical curve group. This allows the development of faster algorithms and positively impacts the performance of technologies based on this principle.
  • Design of a specialized cryptographic algorithm is expected to contribute to privacy protection in various fields and can be linked directly to economic gain the form of workforce promotion and stimulation of IoT-related industries.
  • Cryptographic algorithms, the main product of this research endeavor, promise to be a good showcase for our nation's technological progress, contribute to our freedom from dependence on imported cryptographic algorithms, and generate national wealth by securing our dominance in the field of data protection.
Division of Mathematical Modelspin Kyung-Ah Shim
Tel. +82-42-717-5745