Quantum computing
Tuesday, April 20, 2021

Quantum Computing — An Acute Threat to Encryption?

What impact do quantum computers and the use of quantum computing have on current encryption methods? What are the benefits of developing such computers? And how will the methods used today evolve? Fabian Hauser, who joined our tech team in March 2021, addressed these questions among others in his bachelor’s thesis. In the following, we present an excerpt from his work.

Quantum Computing: Its Potential Impact on Current Encryption Methods

Nowadays, there are many different encryption methods for a wide variety of applications. These methods often use their own procedures to disguise the message. For example, in public-key encryption, finding a key pair is based on mathematical problems (1) that are virtually unsolvable by even the most powerful supercomputers. What happens, however, if the problems on which these methods are based can suddenly be solved by another kind of computer?

As early as 1997, Peter Shor showed that it is possible in theory to solve two of these problems, prime factorization and finding discrete logarithms, with the use of quantum mechanics (2).

There are still several mathematical problems today that cannot be computed efficiently on general-purpose computers, including factoring integers and finding discrete logarithms. Due to this lack of efficient computation, these two problems have given rise to several encryption schemes, such as the elliptic curve method (ECC)(3) and RSA (4). For example, if an average computer were to attempt to crack an RSA algorithm with a by the National Institute of Standards and Technology (NIST) recommended key length of 2048 bits and thus solve its prime factorization, it would take a time of over 14 billion years (6).

In 1997, however, Peter Shor published a paper in which he presented methods that could theoretically solve these problems on a quantum computer (2). From that point on, it was clear that current encryption methods were in acute danger due to the completion of powerful quantum computers.

Encryption of Files: Using Boxcryptor as an Example

However, let us first look at encryption methods currently used in practice, using the encryption software Boxcryptor as an example. Boxcryptor proceeds the encryption of files as follows: First, a random and secure file key is generated for each file. This key is an AES key and in the next step, it is also responsible for encrypting and decrypting the plaintext of the file. In addition to these file keys, each user also has their own RSA key pair (user key) with a public and a private key which goes into action in the next step. This is then used to encrypt the previously generated file key with the RSA public key. Finally, this encrypted file key is stored together with the previously ciphered data in the encrypted file.

When decrypting the file later, this procedure is reversed. Initially, the file key is decrypted using the private user key, and then the encrypted contents of this file are decrypted again using this key. An AES algorithm “with a key length of 256 bits, CBC (Cipher Block Chaining) and PKCS7 padding” is used for the file key, while an RSA algorithm “with a key length of 4096 bits and OAEP padding” is used for the user key.

When looking at the previously described file encryption chain, however, it is noticeable that this sequence depends on the secrecy of the private RSA key. If attackers get hold of this, the file key can be decrypted with it, and thus, also the contents of the file. Therefore Secomba GmbH, as the company behind the software Boxcryptor, is interested in advances in encryption technology. Should quantum computers be powerful enough to crack a 4096-bit RSA encryption in a few years, the security of all customers’ data would no longer be guaranteed. To specifically secure users’ sensitive documents against attacks such as industrial espionage, the Boxcryptor encryption solution must be able to guarantee the security of data also in a post-quantum era.

Quantum Computing: Status Quo and Current Challenges

23 years after Peter Shor was able to show in theory that it is possible to solve prime factorization and finding discrete logarithms with the use of quantum mechanics, research is at a very advanced stage. The first quantum computers now manage to compute such mathematical problems faster than the best supercomputers in the world (7). However, current quantum computers require high computation time for smaller combinatorial problems. This is especially due to the high error-proneness, which is amplified by external influences such as vibration, temperature fluctuations, or electromagnetic waves (8).

Therefore, on this type of computer algorithms must run through a certain number of repetitions to get a realistic result. The disadvantage is that in most cases this repeated execution causes the previously gained computing time to be forfeited again since otherwise, the error rate would be too high.

Experts believe that a time of about 20 years is still needed for the development of universal quantum computers (9 & 10). Nevertheless, the development of the last 20 years must be considered. Few scientists would probably have imagined that nowadays the first 54-qubit quantum computers (Google’s Sycamore) are already available, and the algorithms designed in theory at that time, such as Shor, can already be practically applied to some cases. Accordingly, it is difficult to predict the extent to which this field of research will continue to develop, as even single breakthroughs can mean major advances.

But there are still some problems that need to be solved, such as effective cooling of the system so that the qubits are protected from external temperature effects. If any of these turn out to be particularly complex and take several years to solve, progress can also quickly stagnate. According to the current state of research, however, quantum computers of such high performance do not yet exist, which would put the methods currently in use, and probably those of the next decade, in danger.

Excursus: Quantum Computing and Simulation Platforms: IBM Quantum Composer and Microsoft Q

So far, a few companies have managed to build quantum computers with a few qubits. For example, Paris 53-qubit from IBM (11) or Sycamore 54-qubit from Google (12). However, these are mainly for research. Private individuals do not have the opportunity to experiment with them. Due to the increasing interest of the public, it is only logical that more and more people turn to this topic to gain their first experience in this field. To meet this demand, several companies have already started attempts to develop so-called simulation platforms of quantum computers, which are freely accessible and allow dealing with quantum bits.

Since simulation platforms are run on classical computers, they obviously do not have access to qubits due to physical constraints. However, to simulate n qubits, the machine needs a storage capacity and computation time of 22N (13, p. 1073). If now numbers should be computed, for whose representation some bits are needed, the computational effort for the platforms increases thus enormously, which finally results in a very long computation time.

Two well-known platforms through which private persons interested in the development of quantum algorithms can already carry out small experiments today and thus set foot into the world of quantum computing are IBM Quantum Composer and Microsoft Q#.

IBM Quantum Composer

The Quantum Composer offers a very easy introduction to quantum computing, as it is a graphical user interface that can be used to click together entire quantum circuits using simple drag-and-drop. The advantage of this is that no programming language needs to be learned, and individual algorithms can be easily recreated to understand how quantum algorithms and qubits work. In addition, it is possible to execute the built circuits either on simulations or on real quantum computers without major detours.

Visit here the website of the IBM Quantum Composer.

Microsoft Q

Microsoft announced its programming language specifically for quantum computing at the annual Ignite conference in 2017. This open-source programming language is part of Microsoft’s Quantum Development Kit (QDK), which includes Q# libraries, a simulator, and extensions for other programming environments. The syntax of Q# has strong influences from Python, C#, and F# and includes new quantum operations and data structures as well as common programming components such as loops or if-else branches. Here, all common quantum gates are implemented and syntactically quite similar executable.

Visit here the website of the Microsoft Q#.

Conclusion

Quantum computing is a very exciting topic and, compared to previous years, is no longer completely theoretical. With the help of simulation platforms, interested private persons can nowadays work with qubits and thus reproduce the first quantum algorithms. This is an important step, as it increases the general interest in the topic, and more and more the importance of this research area is recognized. Even if a universal quantum computer were to be developed soon, it will never replace the digital computer we are familiar with, but it will be used as a certain supplement for individual problems.

Especially regarding encryption methods, an interesting aspect is that with the development of such computers, previous methods can be considered insecure. At the same time, a rethinking takes place since new paths are also opened for other methods. “Quantum cryptography” deals with these new possible methods. Nonetheless, neither quantum computing nor post-quantum methods are at a level that can be practically applied in today’s world.

However, we will keep an eye on the subject area of quantum computing. Should the progress of science in this field be faster than expected so far, we, the team of Secomba GmbH, will react and take on the implementation of a post-quantum encryption method with our new colleague Fabian Hauser. Until then, however, you can be sure that your data worth protecting will remain your secret.

Sources:

(1) Martin E. Hellman. “The Mathematics of Public-Key Cryptography”. en. In: Scientific American 241.2 (Aug. 1979), S. 146–157. ISSN: 0036-8733. DOI: 10.1038/scientificamerican0879-146.

(2) Peter W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. In: SIAM Journal on Computing 26.5 (Okt. 1997), S. 1484–1509. ISSN: 0097-5397, 1095-7111. DOI: 10 . 1137 / S0097539795293172. arXiv: quant - ph /9508027.

(3) Sheetal Kalra und Sandeep K. Sood. “Elliptic Curve Cryptography: Current Status and Research Challenges”. In: High Performance Architecture and Grid Computing. Hrsg. von Archana Mantri u. a. Communications in Computer and Information Science. Berlin, Heidelberg: Springer, 2011, S. 455–460. ISBN: 978-3-642-22577-2. DOI: 10.1007/978-3-642-22577-2_62.

(4) R. L. Rivest, A. Shamir und L. Adleman. “A Method for Obtaining DigitalSignatures and Public-Key Cryptosystems”. In: Communications of the ACM 21.2 (Feb. 1978), S. 120–126. ISSN: 0001-0782. DOI: 10.1145/359340.359342.

(5) Elaine B. Barker und Quynh H. Dang. Recommendation for Key Management Part 3: Application-Specific Key Management Guidance. en. Techn. Ber. NIST SP 800-57Pt3r1. National Institute of Standards and Technology, Jan. 2015, NIST SP 800–57Pt3r1. DOI: 10.6028/NIST.SP. 800-57Pt3r1.

(6) All about SSL Cryptography. URL: https://www.digicert.com/faq/ssl-cryptography.htm.

(7) Rafi Letzter. China Claims It’s Achieved ’Quantum Supremacy’ With The World’s Fastest Quantum Computer. Aug. 2020. URL: https://www.sciencealert.com/china-has-developed-the-fastestand-most-powerful-quantum-computer-yet

(8) Maximilian Schlosshauer. “Quantum Decoherence”. In: Physics Reports 831 (Okt. 2019), 1?57. ISSN: 0370-1573. DOI: 10.1016/j.physrep. 2019.10.001.

(9) Wolfgang Marquardt. “In Den Nächsten 20 Jahren Wird Der Quantencomputer Realität Werden”. June 2020.

(10) Wolfgang Wernsdorfer. Quantencomputer Erst in 20 Jahren? May 2017.

(11) Edwin Pednault und John Gunnels. On “Quantum Supremacy”. Oct. 2019. URL: https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/.

(12) Elizabeth Gibney. “Hello Quantum World! Google Publishes Landmark Quantum Supremacy Claim”. In: Nature 574.7779 (Okt. 2019), S. 461–462.DOI: 10.1038/d41586-019-03213-z.

(13) Seth Lloyd. “Universal Quantum Simulator”. In: American Association for the Advancement of Science. New Series 273 (Aug. 1996), S. 1073–1078.

(14) Wolfgang Wernsdorfer. Quantencomputer Erst in 20 Jahren? May 2017.

Start protecting your Dropbox, Google Drive or your favorite cloud with Boxcryptor

End-to-end encryption gives you full control and protection of your data. Start protecting your data and your privacy in the cloud now.

Share this post