Efficient Quantum Algorithm for Post Quantum Cryptography

Summary

This protocol describes the implementation of a "Code based Cryptography" with an explicit quantum circuit for efficient quantum cryptography with a large asymmetric key by utilizing quantum arithmetic with quantum Fourier transformation.

Abstract

The realization of Quantum computers could significantly affect society and global security in many ways. A considerable amount of research has been on quantum cryptography - machines that exploit quantum computerized sensations to solve mathematical problems inaccessible to conventional computers. The flourishing 6th generation of 'Quantum computing' can break and threaten much of the current established protection and digital economy, but may provide cryptographic alternatives. Thus, we are able to optimize various processes more effectively, improving efficiency and enabling faster quantum mechanical simulations for better drug and material design, among other applications. This research focuses on implementing a post-quantum cryptographic algorithm by connecting large-number Quantum multiplication with a quantum random number generator (QRNG). A code-based cryptographic approach using a Quantum Fourier Transformation (QFT) is taken with a giant asymmetric key in an explicit quantum circuit to establish a secure quantum communication system. In this research work, a 'plain text' (classical data) has been encrypted with QRNG using a Quantum multiplier with the aid of quantum arithmetic. Consequently, the resultant quantum data with QRNG data will be transmitted to the receiver end through the quantum channel, where the quantum divider decrypts the same. Furthermore, each intended component's IBM Qiskit simulation results and comparative analysis with previous works and algorithms suggest more robustness and reliability of the proposed quantum proof algorithm when considering large qubit quantum devices. The work provides a valuable direction for further developments in this domain and paves the way for future applications of quantum computing in post-quantum cryptography.

Introduction

Quantum computation is based on quantum bits (qubits), which differ fundamentally from classical bits. While a classical bit can exist only in the state 0 or 1, a qubit can represent 0, 1, or any linear superposition of both states simultaneously. This property enables quantum systems to store and process a vast number of values in parallel rather than sequentially. Upon measurement, the qubit collapses to a definite state, providing the computational result. The inherent parallelism of quantum processing offers a significant speed-up, with estimates suggesting that quantum computers may outperform classical systems by several orders of magnitude. Such advancements pose serious challenges to the security of traditional cryptographic techniques, necessitating the development of cryptographic methods that remain secure in the presence of quantum computation¹.

Classical cryptography has traditionally been regarded as the art of creating secure codes, where the core process of ensuring confidentiality involves encoding and decoding plaintext with the help of a secret key. Historically, cryptographic techniques were primarily employed in military communication and for secure diplomatic exchanges. With the expansion of communication technologies and the growing demand for secure information sharing among legitimate users, cryptography has become a central focus of research in both the academic and industrial sector².

In general, three key components define the encryption process: (1) the cryptographic key or password, (2) the mechanism of key exchange, and (3) the encryption algorithm. The strength of encryption lies in the fact that, even if encrypted data is intercepted, it remains unintelligible without access to the correct key or algorithm³.

Among classical encryption techniques, the Rivest-Shamir-Adleman (RSA), introduced in 1977, has been one of the most widely deployed public-key cryptosystems. At the time of its invention, it was estimated that breaking a 426-bit RSA key would take several quadrillion years. However, by 1994, such keys were compromised, largely due to advances in computational capabilities. As processing power has increased, cryptographic practice has shifted toward longer key lengths, with 2048-bit and 4096-bit RSA keys now serving as contemporary standards³.

In this Internet of Things (IOT) and Cloud service era, data security and privacy are the most important aspects. To address these concerns, an efficient cryptographic algorithm is proposed^3,4,5, which plays a crucial role in securing communication between IoT devices and preserving data privacy. The Edwards curve digital signature, with operations keygen, sign, and verify using the Ed25519 parameter, on the ARM Cortex-M4, implemented in assembly code. The side channel analysis, such as a power analysis attack, is utilized to recover the secret key. While it has been demonstrated that the implementation encompasses all Ed25519 primitives, the scope for attack is limited, and it is shown how different attacks are nullified by this algorithm.

In recent years, numerous cyberattacks have been experienced worldwide, often in the form of ransomware or through other hacking techniques. It leads to losses amounting to hundreds of millions, and in some cases, even billions of dollars, affecting major corporations such as Facebook, Adobe, Sony, Home Depot, JPMorgan, Yahoo, Marriott, and Target, among others.

The advent of quantum computing represents a paradigm shift, exposing new vulnerabilities in classical encryption systems. At the same time, this development has driven innovation in public-key cryptography⁵, giving rise to post-quantum cryptographic primitives^6,7 and protocols specifically designed to withstand quantum-based threats⁶.

The concept of quantum cryptography was first introduced by Stephen Wiesner in the early 1970s, and his foundational ideas were later expanded and formalized by Charles Bennett and Gilles Brassard in 1984². Post-quantum cryptography has been explored in the past through two different approaches: (1) Quantum key distribution (QKD), (2) Theoretical research on post-quantum cryptography, and (3) Implementation of quantum circuits for post-quantum cryptography.

Quantum Key Distribution (QKD)
QKD leverages the principles of quantum mechanics to ensure secure communication. It enables two parties to generate a shared, random secret key that is known exclusively to them, which can subsequently be used for encrypting and decrypting confidential messages. It ensures security where classical cryptography systems cannot. Extensive research has been conducted on quantum key distribution, beginning with the algorithm proposed by C.H. Bennett and G. Brassard² in 1984, followed by BB92³, SARG04⁴, KMB09, S095⁵, S136⁶, and others.

Theoretical research on post-quantum cryptography
Kumar Sekhar Roy and Hemanta Kumar Kalita conducted an extensive survey on this topic. Different post-quantum cryptography-related research has been done mainly on "Lattice based Cryptography"⁸, "Multivariate Cryptography"⁹, "Hash based Cryptography"¹⁰and "Code based Cryptography"¹¹which are showing how they theoretically replace the classical RSA and equivalent algorithms like Elliptic Curve Cryptosystem (ECC). There are multiple algorithms that have been invented in each of these areas.

Lily Chen et al.¹² report on Post-Quantum Cryptography, showing how classical cryptography will be massively impacted due to the introduction of large-scale quantum computers. It shows that asymmetric key-based cryptography will no longer be secure; however, symmetric key-based cryptography will survive in the age of quantum computers by using large key sizes. Additionally, "Quantum arithmetic with the Quantum Fourier Transform"¹³, published by Lidia Ruiz-Perez and Juan Carlos Garcia-Escartin in 2017, opens a new avenue for implementing arithmetic operations on quantum computing to speed up. These works motivate one to implement symmetric key-based cryptography using large number multiplication^14,15 on a quantum computer.

In the context of quantum cryptography, post-quantum cryptographic techniques are theoretically capable of providing strong security guarantees, both in terms of their foundational principles and their applicability to classical as well as emerging security challenges such as encryption, digital signatures, key exchange, and homomorphic encryption^{16,17,18,19,20,21,22}. However, translating these theoretical constructs into practice on quantum computing platforms requires meticulous circuit design and careful consideration of trade-offs. This is necessary to account for the heterogeneity of quantum hardware architectures and to maintain the flexibility needed for deployment in alignment with rapidly evolving cryptographic standards. There are very few realizations or implementations that were done^23,24.

This article presents an implementation where a classical model of symmetric key-based cryptography is reimagined and realized on a quantum computer using the concept of large-number multiplication, which represents a form of code-based cryptography. The symmetric-key cryptography model on quantum computers is presented as more efficient and scalable than existing post-quantum methods^23,24. Lattice- and multivariate-based schemes require heavy computation and large keys; hash-based methods are inefficient for repeated use, and QKD faces scalability issues due to hardware needs. In contrast, the proposed model avoids complex polynomial operations, supports IoT and cloud applications, and operates without specialized hardware beyond standard quantum platforms.

The secret key will be generated by the QRNG generator, which is used in encryption and decryption. Since the secret key is a quantum state, which is protected from various attacks and post-quantum cryptography attacks, as the quantum state will collapse after it is measured.

This article presents a practical realization of a symmetric-key cryptography model on quantum computers. Unlike lattice-, multivariate-, hash-, or QKD-based methods, the proposed approach leverages large-number multiplication and QRNG for key generation, providing both efficiency and resilience against post-quantum attacks. Scalability considerations, hardware resource limitations, and implementation trade-offs relevant for deployment on existing and emerging quantum platforms are also discussed.

Protocol

This article employs the algorithm, utilizing quantum arithmetic and Quantum Fast Fourier Transformation¹³, to decrypt the message by dividing the ciphertext by the symmetric key. The primary objective of this study is to demonstrate the quantum implementation of symmetric key-based cryptography by generating a random key, employing a large multiplication algorithm, and performing a large number of divisions on the IBMQ Environment v1.7.4. Figure 1 depicts the end-to-end process for implementing symmetric key-based encryption. It is assumed that the symmetric key and ciphertext are transferred from the source device (where encryption occurs) to the target device (where decryption occurs) via a quantum channel. The equipment and software used are listed in the Table of Materials.

1. QuRNG generation (Quantum Random Number Generator)

Quantum circuit for generating a large symmetric key. This circuit generates a large random number, i.e., a symmetric key, by using 'hadamard', 'CRZ and 'swap' gates. Considering plain text length is 'x', this circuit generates a symmetric key with a length of '2x'. The QRNG circuit for the random number generator is shown in Figure 2.

2. Multiplication stage

Quantum circuit for multiplying plain text with a large symmetric key to encrypt the plain text to generate cipher text, shown in Figure 3. Quantum multiplier is implemented for n-bit input plain text P and n input QRNG Q

1. First iteration circuit
   In the first iteration, the 0^th input of P is used as the control input of n input CQFFT (controlled Quantum Fourier Transformation) Gate. R be the n target output. After CQFFT, CCZ(Controlled controlledZ) Gate Q is the target input of CQFFT. CCZ gate made multiplication of P and Q. Next 0^th input of P is used as control input of n input CQIFFT (controlled Quantum Inverse Fourier Transformation) Gate. R be the n target output will give resultant multiplication of P and Q, R = P*Q.
2. n^th iteration circuit
   In the first iteration, n^th input of P is used as the control input of the n-input CQFFT (controlled Quantum Fourier Transformation) Gate. R be the n target output. After CQFFT, CCZ (Controlled controlledZ ) Gate Q is the target input of CQFFT. CCZ gate made multiplication of P and Q. Next n^th input of P is used as control input of n input CQIFFT (controlled Quantum Inverse Fourier Transformation) Gate. R be the n target output will give resultant multiplication of P and Q, R = P*Q.

3. Shuffler

Quantum circuit for shuffling the symmetric key. It uses quantum 'swap' gates to shuffle symmetric post encryption of the message, and before sending to the target device via a quantum channel. Quantum 'swap' gate internally uses three 'CNOT' gates. The shuffler circuit is shown in Figure 4.

4. Reshuffler

Quantum circuit forreshuffling the symmetric key to get the original symmetric key. It uses quantum 'swap' gates to reshuffle the symmetric post-receiving the symmetric key through the quantum channel into the target device. Quantum 'swap' gate internally uses three 'CNOT' gates. Reshuffler is shown in Figure 5.

5. Division

A quantum circuit for division to decrypt the ciphertext by dividing the ciphertext by a reshuffled symmetric key is depicted in Figure 6.

6. Encryption and decryption

Multiplication^14,15 and division¹⁶circuits are used for quantum Fast Fourier Transformation(FFT), inverse FFT, controlled FFT, and controlled inverse FFT¹³for the implementation of encryption and decryption. In Figure 7, the Quantum gate implementation of the Fast Fourier Transformation (FFT) is shown, which utilizes the 'Hadamard' gate and 'CRz' gate to implement Quantum FFT.

where, cRz (k) =

In Figure 8, the Quantum gate implementation Inverse Fast Fourier Transformation (QIFFT) is depicted. QIFFT is implemented using the 'hadamard' gate and 'cRz' gate, Quantum inverse FFT is implemented. The controlled Quantum Fast Fourier Transformation (CQFFT) implementation is described in Figure 9. Quantum gate implementation of controlled inverse Fast Fourier Transformation (CIFFT) is shown in Figure 10. All steps are executed by the IBMQ Environment v1.7.4.

Results

All the components of the above-mentioned circuit (Figure 1) have been implemented using Python code (Supplementary Files 1-3) with IBM Qiskit and executed on a Local and IBMQ simulator. However, they are not able to execute on quantum devices due to the lack of freely available qubits in existing quantum devices. The histogram output in the Local and IBMQ simulators for all the key components is depicted below.

<...

Discussion

The success of the proposed quantum cryptography protocol relies on three critical stages: Quantum Random Number Generation (QRNG), Quantum Arithmetic Operations using Quantum Fast Fourier Transformation (QFFT and QIFFT), and Quantum Key Shuffling and Reshuffling. The QRNG stage establishes the foundation of security by generating truly random symmetric keys³. The arithmetic operations, executed using controlled QFFT and inverse QFFT gates, ensure accurate encryption and decryption, while the shuf...

Materials

List of materials used in this article

Name	Company	Catalog Number	Comments
GPU A100	NVIDIA		80G GPU
ibm_brisbane	IBM	https://quantum.ibm.com/	The superconducting quantum computer in the IBM Quantum Eagle family.
python3.10	Python Software Foundation	https://www.python.org/downloads/release/python-3100/
Qiskit	IBM	https://www.ibm.com/quantum/qiskit	An open-source SDK for working with quantum computers at the level of extended quantum circuits, operators, and primitives.