R-Propping of HK17: Upgrade for a Detached Proposal of NIST PQC First Round Survey

Keita Xagawa

Taniya Hasija, K. R. Ramkumar, Amanpreet Kaur +2 more

The tremendous increase in the volume of data over internet for many applications such as banking, hospitals, insurance, online trading, messengers, voice communications and others has resulted in increased security threats. Due to the evaluation in the quantum computer generation, the classical cryptography algorithm will be broken in very less amount of time and lead to the security breaches and malicious attacks. The National Institute of Standard and Technology (NIST) has invited a new generation of Quantum Safe cryptography. First two rounds are completed successfully, and the finalist has been announced. This paper provides an in-depth examination of NIST third round selected candidates which are going to be the standard Post Quantum Cryptography (PQC) algorithm. Also, the limitations and attacking concerns related to that PQC algorithms are presented.

Haoyu Li, Renzhang Liu, Qutaibah Marwan Malluhi +3 more

In November 2017, Hecht and Kamlofsky submitted HK17, a quaternion(octonion)-based Diffie-Hellman key exchange protocol, to NIST post-quantum cryptography project, and thought that at least O(p8) arithmetic operations are needed for a passive adversary to recover the shared key where p is the modulo used in the scheme. Later, Bernstein and Lange pointed out that the shared key can be recovered with O(p) arithmetic operations, which implies that HK17 with small p is not secure. However, their attack does not work in practice for the scheme with sufficiently large p, although the scheme is still efficient. In this paper, we propose an attack to show that just constant arithmetic operations, or Õ(log p) bit operations, are enough to recover the shared key for a passive adversary. Note that even the legal party in the protocol needs at least Õ(log p) bit operations to establish the shared key. We break HK17 completely in the practical sense.

Edgard Nicéas Arcoverde Gusmão Lima, Fábio Wlademir Monteiro Maia, Tiago A. E. Ferreira +1 more

Maryna V. Yesina, Ye.V. Ostrianska, І.Д. Горбенко

In recent years, there has been steady progress in the creation of quantum computers. If large-scale quantum computers are implemented, they will threaten the security of many widely used public-key cryptosystems. Key-establishment schemes and digital signatures based on factorization, discrete logarithms, and elliptic curve cryptography will be most affected. Symmetric cryptographic primitives such as block ciphers and hash functions will be broken only slightly. As a result, there has been an intensification of research on finding public-key cryptosystems that would be secure against cryptanalysts with both quantum and classical computers. This area is often called post-quantum cryptography (PQC), or sometimes quantum-resistant cryptography. The goal is to design schemes that can be deployed in existing communication networks and protocols without significant changes. The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through an open competition. New public-key cryptography standards will define one or more additional digital signatures, public-key encryption, and key-establishment algorithms. It is assumed that these algorithms will be able to protect confidential information well in the near future, including after the advent of quantum computers. After three rounds of evaluation and analysis, NIST has selected the first algorithms that will be standardized as a result of the PQC standardization process. The purpose of this article is to review and analyze the state of NIST's post-quantum cryptography standardization evaluation and selection process. The article summarizes each of the 15 candidate algorithms from the third round and identifies the algorithms selected for standardization, as well as those that will continue to be evaluated in the fourth round of analysis. Although the third round is coming to an end and NIST will begin developing the first PQC standards, standardization efforts in this area will continue for some time. This should not be interpreted as meaning that users should wait to adopt post-quantum algorithms. NIST looks forward to the rapid implementation of these first standardized algorithms and will issue future guidance on the transition. The transition will undoubtedly have many complexities, and there will be challenges for some use cases such as IoT devices or certificate transparency.

Sergey Vladimirovich Polyakov, Alan L. Migdall