SoftBank and SandboxAQ’s Proof-of-Concept on PQC Hybrid Cryptography

Key Points of This Blog

・ The results of a proof-of-concept experiment on a hybrid cryptographic scheme combining PQC(Post Quantum Cryptography) and conventional encryption have been released.

・ The impact of introducing PQC on communication, including latency and the number of simultaneous connections.

・ The performance of standardized PQC algorithms has a smaller impact on communication performance compared to other algorithms.

1. Efforts Toward the Practical Application of Quantum Computers: SoftBank and SandboxAQ’s Challenge

In the near future, it is anticipated that quantum computers with powerful computational capabilities will emerge and be capable of outmatching traditional encryption methods. While the advent of quantum computers promises significant advancements in our daily lives, it poses a serious threat to cybersecurity, with current encryption standards such as RSA and Elliptic Curve Cryptography (ECC) potentially being easily broken.

SoftBank, in collaboration with SandboxAQ, has been validating the practical application of Post Quantum Cryptography (PQC), which is capable of ensuring security even in the era of quantum computers, and their efforts have proven the effectiveness of PQC.

Press release:SoftBank Corp. and SandboxAQ Jointly Verify Hybrid Mode Quantum-safe Technology (Feb, 2023)

Blog:SoftBank’s PQC: Preparing for the Arrival of Quantum Computers (Apr, 2023)

With the standardization of some PQC algorithms by the National Institute of Standards and Technology (NIST), we will now release the results of our previously unpublished Proof-of-Concept in a white paper.

The white paper can be downloaded from the following URL.

https://www.softbank.jp/en/corp/technology/research/news/076/

This blog post overviews the necessity and challenges of PQC and the insights gained from the PoC, while excerpting content from the white paper.

2. The Threat of Quantum Computers to Cryptography

Quantum computers possess remarkable abilities in solving mathematical problems that traditional computers cannot. This makes them a major threat to widely used encryption methods. This section will explain the mechanisms and impacts of this threat.

Traditional computers process information using "bits," which assume values of either 0 or 1. Quantum computers, on the other hand, use "quantum bits (qubits)," which can hold both 0 and 1 simultaneously, a property known as ”superposition”. This allows quantum computers to perform multiple calculations at once.

RSA and ECC rely on the mathematical difficulties of problems like factorization and discrete logarithms. These encryption methods have been considered secure for traditional computers due to the substantial time required to solve these problems. However, quantum computers can solve these problems dramatically faster using Shor’s algorithm, a quantum algorithm that efficiently handles factorization and discrete logarithms, thereby potentially breaking RSA and ECC encryption.

To counter this, researchers are developing PQC, a new encryption method designed to be resistant to quantum computer attacks. This includes lattice-based and code-based cryptographic methods, which rely on mathematical problems that quantum computers cannot easily solve.

The National Institute of Standards and Technology (NIST) has been advancing the standardization of PQC algorithms to combat decryption by quantum computers. By 2024, three PQC algorithms have been standardized: one key exchange algorithm and two digital signature algorithms.

Table 1: Standardized Algorithms by NIST

3. Overcoming Challenges of Practical Application with ”Hybrid Cryptography”

While PQC is expected to become the next generation encryption technology that even quantum computers cannot easily decipher, there are challenges around its practical application, such as compatibility with existing systems and the risk of undiscovered vulnerabilities.

To address these issues, "hybrid cryptography" is being adopted. This technique combines traditional encryption methods with PQC, ensuring compatibility with current systems while also providing security in the era of quantum computers.

However, using hybrid cryptography requires handling both traditional and PQC methods, which may increase communication sizes and computational costs. When migrating systems, it is important to assess not only the security aspects, but also the impact on communication in an actual operating environment.

4. Proof-of-Concept: Achieving Secure Communication without Compromising User Experience

SoftBank and SandboxAQ conducted a proof-of-concept in 2022 to verify the effectiveness of hybrid cryptography under conditions simulating a real-world network environment. The experiment assessed the impact of performing key exchange and digital signatures using a hybrid method of PQC and traditional encryption across various network scenarios.

The proof-of-concept used ECC as the traditional encryption method. For PQC, algorithms based on several mathematical problems, as listed in Table 2, were used. These algorithms were chosen from those that remained in the third round of the standardization process as of 2022.

Table 2: Algorithms Used in the Proof-of-Concept

Proof-of-Concept Environment and Evaluation Metrics

For this proof-of-concept, an environment was constructed to simulate online services used daily, such as video streaming, online gaming, and VPN connections.

Performance metrics focused on the direct impact on user experience per below:

- Communication Speed: Measuring the impact of encryption on communication speed

- Device Load: Evaluating the load on devices such as smartphones and servers

- Stability: Assessing communication stability and connection reliability

- Resource Usage: Analyzing the impact of encryption on device memory and CPU usage

Proof-of-Concept Results: High Performance of ML-KEM and ML-DSA

The results demonstrated that hybrid cryptography, particularly algorithms based on lattice-based cryptography (ML-KEM and ML-DSA), provided secure communication without affecting user experience.

For example, when comparing latency, hybrid cryptography utilizing ML-KEM and ML-DSA performed almost as well as traditional methods, implying users can comfortably use online services without noticing any speed degradation caused by encryption.

Analysis of Latency and Connection Success Rates

Lattice-based and code-based cryptography exhibited response times comparable to traditional ECC across all network scenarios (on-premise WiFi, 5G, LTE, and Smart VPN), indicating minimal additional latency due to PQC.

This result signifies that PQC can be practically implemented into current network environments.

Connection success rates also consistently remained at 100% for lattice-based and code-based cryptography until network or server limits were reached (approximately 500 connections per second).

This suggests that PQC can handle high connection rates without issue, with server constraints being the primary limiting factor.

CPU and Memory Usage and Stress Testing

Analysis revealed high CPU usage for isogeny-based cryptography, while lattice-based and code-based cryptography matched the CPU usage levels of traditional algorithms. Lattice-based cryptography, in particular, demonstrated reasonable memory usage, proving efficient resource utilization, making these PQC algorithms practical for real-world deployment.

Stress testing confirmed that PQC did not become a bottleneck in terms of server capacity, and that connection failures were mainly due to network constraints. This shows that lattice-based and code-based algorithms can withstand significant loads.

Communication Size for Digital Signatures

PQC digital signatures posed minimal delay but an increase in communication sizes. Performance analysis indicated both traditional and PQC signature algorithms kept delays under 20 milliseconds, with negligible latency overhead from PQC. However, PQC signatures were larger in communication size, e.g., ML-DSA required 26,586 bytes versus 2,004 bytes for ECDSA. This difference in communication size and its impact on handshake delays must be carefully considered during implementation.

These findings validate hybrid cryptography as a practical solution for current and future security demands.

5. Preparing for the Quantum Computing Era

SoftBank and SandboxAQ’s proof-of-concept clearly demonstrated hybrid cryptography as a practical and effective solution for businesses preparing for the quantum computing era. Hybrid cryptography provides a robust means to counter modern cyber threats and safeguard sensitive data against advancements in quantum computing.

When implementing these technologies, careful selection and verification of algorithms that meet usage requirements is essential. This includes considering communication sizes of signature algorithms and performance-related CPU loads. This proof-of-concept revealed both the practicality of hybrid cryptography as well as the differences and challenges of individual algorithms, providing businesses with crucial information to determine the best fit for their needs.

Gradual implementation of hybrid cryptography in real-world applications is necessary, involving thorough review and documentation of cryptographic systems, clear security and compliance requirements, and fostering a culture of crypto-agility. Organizations can smoothly integrate new cryptographic methods by prioritizing quantum-safe solutions and building flexible infrastructures.

The white paper provides more detailed results of this proof-of-concept experiment, along with recommended actions for early adoption.

For more details, see the white paper.