skip to main content

Title: Security Comparisons and Performance Analyses of Post-quantum Signature Algorithms
Quantum computing challenges the computational hardness assumptions anchoring the security of public-key ciphers, such as the prime factorization and the discrete logarithm problem. To prepare for the quantum era and withstand the attacks equipped with quantum computing, the security and cryptography communities are designing new quantum-resistant public-key ciphers. National Institute of Standards and Technology (NIST) is collecting and standardizing the post-quantum ciphers, similarly to its past involvements in establishing DES and AES as symmetric cipher standards. The NIST finalist algorithms for public-key signatures are Dilithium, Falcon, and Rainbow. Finding common ground to compare these algorithms can be difficult because of their design, the underlying computational hardness assumptions (lattice based vs. multivariate based), and the different metrics used for security strength analyses in the previous research (qubits vs. quantum gates). We overcome such challenges and compare the security and the performances of the finalist post-quantum ciphers of Dilithium, Falcon, and Rainbow. For security comparison analyses, we advance the prior literature by using the depth-width cost for quantum circuits (DW cost) to measure the security strengths and by analyzing the security in Universal Quantum Gate Model and with Quantum Annealing. For performance analyses, we compare the algorithms’ computational loads in the execution more » time as well as the communication costs and implementation overheads when integrated with Transport Layer Security (TLS) and Transmission Control Protocol (TCP)/Internet Protocol (IP). Our work presents a security comparison and performance analysis as well as the trade-off analysis to inform the post-quantum cipher design and standardization to protect computing and networking in the post-quantum era. « less
; ; ; ; ;
Award ID(s):
Publication Date:
Journal Name:
Applied Cryptography and Network Security (ACNS)
Sponsoring Org:
National Science Foundation
More Like this
  1. Public Key Infrastructure (PKI) generates and distributes digital certificates to provide the root of trust for securing digital networking systems. To continue securing digital networking in the quantum era, PKI should transition to use quantum-resistant cryptographic algorithms. The cryptography community is developing quantum-resistant primitives/algorithms, studying, and analyzing them for cryptanalysis and improvements. National Institute of Standards and Technology (NIST) selected finalist algorithms for the post-quantum digital signature cipher standardization, which are Dilithium, Falcon, and Rainbow. We study and analyze the feasibility and the processing performance of these algorithms in memory/size and time/speed when used for PKI, including the key generation from the PKI end entities (e.g., a HTTPS/TLS server), the signing, and the certificate generation by the certificate authority within the PKI. The transition to post-quantum from the classical ciphers incur changes in the parameters in the PKI, for example, Rainbow I significantly increases the certificate size by 163 times when compared with RSA 3072. Nevertheless, we learn that the current X.509 supports the NIST post-quantum digital signature ciphers and that the ciphers can be modularly adapted for PKI. According to our empirical implementations-based study, the post-quantum ciphers can increase the certificate verification time cost compared to the current classicalmore »cipher and therefore the verification overheads require careful considerations when using the post-quantum-cipher-based certificates.« less
  2. Many currently deployed public-key cryptosystems are based on the difficulty of the discrete logarithm and integer factorization problems. However, given an adequately sized quantum computer, these problems can be solved in polynomial time as a function of the key size. Due to the future threat of quantum computing to current cryptographic standards, alternative algorithms that remain secure under quantum computing are being evaluated for future use. One such algorithm is CRYSTALS-Dilithium, a lattice-based digital signature scheme, which is a finalist in the NIST Post Quantum Cryptography (PQC) competition. As a part of this evaluation, high-performance implementations of these algorithms must be investigated. This work presents a high-performance implementation of CRYSTALS-Dilithium targeting FPGAs. In particular, we present a design that achieves the best latency for an FPGA implementation to date. We also compare our results with the most-relevant previous work on hardware implementations of NIST Round 3 post-quantum digital signature candidates.
  3. Motivated by the rise of quantum computers, existing public-key cryptosystems are expected to be replaced by post-quantum schemes in the next decade in billions of devices. To facilitate the transition, NIST is running a standardization process which is currently in its final Round. Only three digital signature schemes are left in the competition, among which Dilithium and Falcon are the ones based on lattices. Besides security and performance, significant attention has been given to resistance against implementation attacks that target side-channel leakage or fault injection response. Classical fault attacks on signature schemes make use of pairs of faulty and correct signatures to recover the secret key which only works on deterministic schemes. To counter such attacks, Dilithium offers a randomized version which makes each signature unique, even when signing identical messages. In this work, we introduce a novel Signature Correction Attack which not only applies to the deterministic version but also to the randomized version of Dilithium and is effective even on constant-time implementations using AVX2 instructions. The Signature Correction Attack exploits the mathematical structure of Dilithium to recover the secret key bits by using faulty signatures and the public-key. It can work for any fault mechanism which can inducemore »single bit-flips. For demonstration, we are using Rowhammer induced faults. Thus, our attack does not require any physical access or special privileges, and hence could be also implemented on shared cloud servers. Using Rowhammer attack, we inject bit flips into the secret key s1 of Dilithium, which results in incorrect signatures being generated by the signing algorithm. Since we can find the correct signature using our Signature Correction algorithm, we can use the difference between the correct and incorrect signatures to infer the location and value of the flipped bit without needing a correct and faulty pair. To quantify the reduction in the security level, we perform a thorough classical and quantum security analysis of Dilithium and successfully recover 1,851 bits out of 3,072 bits of secret key $s_{1}$ for security level 2. Fully recovered bits are used to reduce the dimension of the lattice whereas partially recovered coefficients are used to to reduce the norm of the secret key coefficients. Further analysis for both primal and dual attacks shows that the lattice strength against quantum attackers is reduced from 2128 to 281 while the strength against classical attackers is reduced from 2141 to 289. Hence, the Signature Correction Attack may be employed to achieve a practical attack on Dilithium (security level 2) as proposed in Round 3 of the NIST post-quantum standardization process.« less
  4. Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true. We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bitsmore »albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing. We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.« less
  5. Distributed cyber-infrastructures and Artificial Intelligence (AI) are transformative technologies that will play a pivotal role in the future of society and the scientific community. Internet of Things (IoT) applications harbor vast quantities of connected devices that collect a massive amount of sensitive information (e.g., medical, financial), which is usually analyzed either at the edge or federated cloud systems via AI/Machine Learning (ML) algorithms to make critical decisions (e.g., diagnosis). It is of paramount importance to ensure the security, privacy, and trustworthiness of data collection, analysis, and decision-making processes. However, system complexity and increased attack surfaces make these applications vulnerable to system breaches, single-point of failures, and various cyber-attacks. Moreover, the advances in quantum computing exacerbate the security and privacy challenges. That is, emerging quantum computers can break conventional cryptographic systems that offer cyber-security services, public key infrastructures, and privacy-enhancing technologies. Therefore, there is a vital need for new cyber-security paradigms that can address the resiliency, long-term security, and efficiency requirements of distributed cyber infrastructures. In this work, we propose a vision of distributed architecture and cyber-security framework that uniquely synergizes secure computation, Physical Quantum Key Distribution (PQKD), NIST PostQuantum Cryptography (PQC) efforts, and AI/ML algorithms to achieve breach-resilient, functional, andmore »efficient cyber-security services. At the heart of our proposal lies a new Multi-Party Computation Quantum Network Core (MPC-QNC) that enables fast and yet quantum-safe execution of distributed computation protocols via integration of PQKD infrastructure and hardware acceleration elements. We showcase the capabilities of MPCQNC by instantiating it for Public Key Infrastructures (PKI) and federated ML in our HDQPKI and TPQ-ML, frameworks, respectively. HDQPKI (to the best of our knowledge) is the first hybrid and distributed post-quantum PKI that harnesses PQKD and NIST PQC standards to offer the highest level of quantum safety with a breach-resiliency against active adversaries. TPQ-ML presents a post-quantum secure and privacy-preserving federated ML infrastructure.« less