An official website of the United States government
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 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.
more »
« less
Performance Characterization of Post-Quantum Digital Certificates
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 classical cipher and therefore the verification overheads require careful considerations when using the post-quantum-cipher-based certificates.
more »
« less
- Award ID(s):
- 1922410
- PAR ID:
- 10324007
- Date Published:
- Journal Name:
- International Conference on Computer Communications and Networks (ICCCN)
- Page Range / eLocation ID:
- 1 to 9
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Domain Name System Security Extensions (DNSSEC) uses public-key digital signatures to provide integrity and authentication for DNS query responses. The current standardized DNS for reliable UDP delivery limits DNS response (including the message, signature, and public key) to a maximum of 1232 bytes. Incorporating NIST’s post-quantum digital signatures into the DNS protocol results in a response size that exceeds the limit set by the Ethernet standardization, making PQC incompatible with the current standardized DNS. To address the incompatibility and enable PQC to protect the authenticity against the quantum-equipped adversaries, previous research proposed fragmenting the DNSSEC messages. Fragmentation however exposes DNSSEC to Fragmentation Mis-Association threat, traditionally studied in the broader IP fragmentation contexts and not applicable in the current DNSSEC with classical/pre-quantum cipher (no fragmentation needed). We distinguish our work from the previous research incorporating PQC to DNSSEC to defend against the Fragmentation Mis- Association Threat by chaining the fragments and applying cryptographic commit-and-reveal. We also advance the previous research and further reduce the number of packet fragments, which can be particularly useful as the DNSSEC based on UDP is prone to packet transmission failure increasing the chance of the DNS response failure when sent in multiple fragments, by using blockchain to offload and enable the offline delivery of the public key. Our scheme thus even allows the Falcon-512 PQC cipher incorporation to forgo the fragmentation, in contrast to the previous research requiring fragmentation for Falcon-512; the other PQC ciphers, i.e., Dilithium ciphers and Falcon-1024, still require fragmentation in our scheme due to the standardized signature sizes. We implement our scheme and analyze the effectiveness and performances through experimentation.more » « less
-
Post-quantum ciphers (PQC) provide cryptographic algorithms for public-key ciphers which are computationally secure against the threats from quantum-computing adversaries. Because the devices in mobile computing are limited in hardware and power, we analyze the PQC power overheads. We implement the new NIST PQCs across a range of device platforms to simulate varying resource capabilities, including multiple Raspberry Pis with different memories, a laptop, and a desktop computer. We compare the power measurements with the idle cases as our baseline and show the PQCs consume considerable power. Our results show that PQC ciphers can be feasible in the resource-constrained devices (simulated with varying Raspberry Pis in our case); while PQCs consume greater power than the classical cipher of RSA for laptop and desktop, they consume comparable power for the Raspberry Pis.more » « less
-
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.more » « less
-
Blockchain technology is the cornerstone of digital trust and systems’ decentralization. The necessity of eliminating trust in computing systems has triggered researchers to investigate the applicability of Blockchain to decentralize the conventional security models. Specifically, researchers continuously aim at minimizing trust in the well-known Public Key Infrastructure (PKI) model which currently requires a trusted Certificate Authority (CA) to sign digital certificates. Recently, the Automated Certificate Management Environment (ACME) was standardized as a certificate issuance automation protocol. It minimizes the human interaction by enabling certificates to be automatically requested, verified, and installed on servers. ACME only solved the automation issue, but the trust concerns remain as a trusted CA is required. In this paper we propose decentralizing the ACME protocol by using the Blockchain technology to enhance the current trust issues of the existing PKI model and to eliminate the need for a trusted CA. The system was implemented and tested on Ethereum Blockchain, and the results showed that the system is feasible in terms of cost, speed, and applicability on a wide range of devices including Internet of Things (IoT) devices.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICCCN52240.2021.9522179
