Suramya's Blog : Welcome to my crazy life…

November 14, 2022

IBM Unveils the worlds largest Quantum Computer with 433 qubits

Filed under: My Thoughts,Quantum Computing — Suramya @ 2:01 AM

Scaling up Quantum computers has become a race between the various players in the market and IBM has raised the stakes by unveiling a 433 qubits Quantum computer that is more than a 3x increase from their previous setup of 127 qubits. Even with this massive gain they are still ways off from a making a 4000 qubit computer by 2025 which is their goal.

In this new setup IBM replaced the “quantum chandelier” used in the previous processors with flexible ribbon cables that are designed for cryogenic environments. These new cables allow a more efficient flow of microwave signals which in turn decreased the interference caused by the cables. This gave them a 77% increase in the number of connections to the chip, which in turn enabled them to scale up more easily. They also separated the wires and components for control and readout into their own layers, which further reduced the interference with the qubits.

The new setup also includes a state of the art cryo-CMOS prototype controller chip implemented using 14-nanometer FinFET technology that reduces the power requirement for the setup from about 100 watts per qubit to about 10 milliwatts per qubit. The new beta update for Qiskit Runtime allows the user to trade speed for reduced error count and a new option called Qiskit primitives called a “resilience level” lets users dial in the cost/accuracy trade that is suitable to the task being worked on. Both functionality is expected to be ready for production release by 2025.

Quantum computing makes my head hurt but there is no doubt that it is changing the computing world in a massive way.

Source:
* IEEE Spectrum: IBM Unveils 433-Qubit Osprey Chip
* New Scientist: IBM unveils world’s largest quantum computer at 433 qubits

– Suramya

August 6, 2022

Post Quantum Encryption: Another candidate algorithm (SIKE) bites the dust

Filed under: Computer Security,Computer Software,Quantum Computing — Suramya @ 8:23 PM

Quantum Computing has the potential to make the current encryption algorithms obsolete once it gets around to actually being implemented on a large scale. But the Cryptographic experts in charge of such things have been working on Post Quantum Cryptography/Post Quantum Encryption (PQE) over the past few years to offset this risk. SIKE was one of KEM algorithms that advanced to the fourth round earlier this year and it was considered as an attractive candidate for standardization because of its small key and ciphertext sizes.

Unfortunately while that is true researchers have found that the algorithm is badly broken. Researchers from the Computer Security and Industrial Cryptography group at KU Leuven published a paper over the weekend “An Efficient Key Recovery Attack on SIDH” (Preliminary Version) that describes a technique which allows an attacker to recover the encryption keys protecting the SIKE Protected transactions in under an hours time using a single traditional PC. Since the whole idea behind PQE was to identify algorithms that are stronger than the traditional ones this immediately disqualifies SIKE from further consideration.

Abstract. We present an efficient key recovery attack on the Supersingular Isogeny Diffie–Hellman protocol (SIDH), based on a “glue-and-split” theorem due to Kani. Our attack exploits the existence of a small non-scalar endomorphism on the starting curve, and it also relies on the auxiliary torsion point information that Alice and Bob share during the protocol. Our Magma implementation breaks the instantiation SIKEp434, which aims at security level 1 of the Post-Quantum Cryptography standardization process currently ran by NIST, in about one hour on a single core.

The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known. The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for fault attacks, the GPST adaptive attack, torsion point attacks, etc.

This is not a bad thing as the whole testing and validation process is supposed to weed out weak algorithms and it is better to have them identified and removed now than after their release as then it becomes almost impossible to phase out systems that use the broken/compromised encryption algorithms.

Source: Schneier on Security: SIKE Broken

– Suramya

April 25, 2022

Rainbow Algorithm (one of the candidates for post-quantum Cryptography) can be broken in under 53 hours

Quantum Computing has the potential to make the current encryption algorithms obsolete once it gets around to actually being implemented on a large scale. But the Cryptographic experts in charge of such things have been working on Post Quantum Cryptography over the past few years to offset this risk. After three rounds they had narrowed down the public-key encryption and key-establishment algorithms to Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER and te finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow.

Unfortunately for the Rainbow algorithm, Ward Beullens at IBM Research Zurich in Switzerland managed to find the corresponding secret key for a given Rainbow public key in 53 hours using a standard laptop. This would allow anyone with a laptop to ‘prove’ they were someone else by producing the secret key for a given public key.

The Rainbow signature scheme [8], proposed by Ding and Schmidt in 2005, is one of the oldest and most studied signature schemes in multivariate cryptography. Rainbow is based on the (unbalanced) Oil and Vinegar signature scheme [16, 11], which, for properly chosen parameters, has withstood all cryptanalysis since 1999. In the last decade, there has been a renewed interest in multivariate cryptography, because it is believed to resist attacks from quantum adversaries. The goal of this paper is to improve the cryptanalysis of Rainbow, which is an important objective because Rainbow is currently one of three finalist signature
schemes in the NIST Post-Quantum Cryptography standardization project.

This obviously disqualifies the algorithm from being standardised as it has a known easily exploitable weakness. It goes on to prove that cryptography is not easy and the only way to ‘prove’ the strength of an algorithm is to let others test them for vulnerabilities. Or as Bruce Schneier put it in Schneier’s Law: ‘Anyone can create an algorithm that they themselves can’t break.’ , you need others to validate that claim.

Paper: Breaking Rainbow Takes a Weekend on a Laptop by Ward Beullens (PDF)
Source: New Scientist: Encryption meant to protect against quantum hackers is easily cracked

– Suramya

April 22, 2022

Implications and Impact of Quantum Computing on Existing Cryptography

As all of you are aware the ability to break encryption of sensitive data like financial systems, private correspondence, government systems in a timely fashion is the holy grail of computer espionage. With the current technology it is unfeasible to break the encryption in a reasonable timeframe. If the target is using a 256-bit key an attacker will need to try a max of 2256 possible combinations to brute-force it. This means that even with the fastest supercomputer in the world will take millions of years to try all the combinations (Nohe, 2019). The number of combinations required to crack the encryption key increase exponentially, so a 2048-bit key has 22048 possible combinations and will take correspondingly longer time to crack. However, with the recent advances in Quantum computing the dream of breaking encryption in a timely manner is close to becoming reality in the near future.

Introduction to Quantum Computing

So, what is this Quantum computing and what makes it so special? Quantum computing is an emerging technology field that leverages quantum phenomena to perform computations. It has a great advantage over conventional computing due to the way it stores data and performs computations. In a traditional system information is stored in the form of bits, each of which can be either 0 or 1 at any given time. This makes a ‘bit’ the fundamental using of information in traditional computing. A Quantum computer on the other hand uses a ‘qubit’ as its fundamental unit and unlike the normal bit, a qubit can exist simultaneously as 0 and 1 — a phenomenon called superposition (Freiberger, 2017). This allows a quantum computer to act on all possible states of a qubit simultaneously, enabling it to perform massive operations in parallel using only a single processing unit. In fact, a theoretical projection has postulated that a Quantum Computer could break a 2048-bit RSA encryption in approximately 8 hours (Garisto, 2020).

In 1994 Peter W. Shor of AT&T deduced how to take advantage of entanglement and superposition to find the prime factors of an integer (Shor, 1994). He found that a quantum computer could, in principle, accomplish this task much faster than the best classical calculator ever could. He then proceeded to write an algorithm called Shor’s algorithm that could be used to crack the RSA encryption which prompted computer scientists to begin learning about quantum computing.

Introduction to Current Cryptography

Current security of cryptography relies on certain “hard” problems—calculations which are practically impossible to solve without the correct cryptographic key. Just as it is easy to break a glass jar but difficult to stick it back together there are certain calculations that are easy to perform but difficult to reverse. For example, we can easily multiply two numbers to get the result, however it is very hard to start with the result and work out which two numbers were multiplied to produce it. This becomes even more hard as the numbers get larger and this forms the basis of algorithms like the RSA (Rivest et al., 1978) that would take the best computers available billions of years to solve and all current IT security aspects are built on top of this basic foundation.

There are multiple ways of classifying cryptographic algorithms but in this paper, they will be classified based on the keys required for encryption and decryption. The main types of cryptographic algorithms are symmetric cryptography and asymmetric cryptography.

Symmetric Cryptography

Symmetric cryptography is a type of encryption that uses the same key for both encryption and decryption. This requires the sender and receiver to exchange the encryption key securely before encrypted data can be exchanged. This type of encryption is one of the oldest in the world and was used by Julius Caesar to protect his communications in Roman times (Singh, 2000). Caesar’s cipher, as it is known is a basic substitution cypher where a number is used to offset each alphabet in the message. For example, if the secret key is ‘4’ then each alphabet would be replaced with the 4th letter down from it, i.e. A would be replaced with E, B with F and so on. Once the sender and receiver agree on the encryption key to be used, they can start communicating. The receiver would take each character of the message and then go back 4 letters to arrive at the plain-text message. This is a very simple example, but modern cryptography is built on top of this principle.

Another example is from world war II during which the Germans were encrypting their transmissions using the Enigma device to prevent the Allies from decrypting their messages as they had in the first World War (Rijmenants, 2004). Each day both the receiver and sender would configure the gears and specific settings to a new value as defined by secret keys distributed in advance. This allowed them to transmit information in an encrypted format that was almost impossible for the allied forces to decrypt. Examples of symmetric encryption algorithms include Advanced Encryption Standard (AES), Data Encryption Standard (DES), and International Data Encryption Algorithm (IDEA).

Symmetric encryption algorithms are more efficient than asymmetric algorithms and are typically used for bulk encryption of data.

Asymmetric Cryptography

Unlike symmetric cryptography asymmetric cryptography uses two keys, one for encryption and a second key for decryption (Rouse et al., 2020). Asymmetric cryptography was created to address the problems of key distribution in symmetric encryption and is also known as public key cryptography. Modern public key cryptography was first described in 1976 by Stanford University professor Martin Hellman and graduate student Whitfield Diffie. (Diffie & Hellman, 1976)

Asymmetric encryption works with public and private keys where the public key is used to encrypt the data and the private key is used to decrypt the data (Rouse et al., 2020). Before sharing data, a user would generate a public-private keypair and they would then publish their public key on their website or in key management portals. Now, whoever wants to send private data to them would use their public key to encrypt the data before sending it. Once they receive the cipher-text they would use their private key to decrypt the data. If we want to add another layer of authentication to the communication, the sender would encrypt the data with their private key first and then do a second layer of encryption using the recipient’s public key. The recipient would first decrypt the message using their private key, then decrypt the result using the senders public key. This validates that the message was sent by the sender without being tampered. Public key cryptography algorithms in use today include RSA, Diffie-Hellman and Digital Signature Algorithm (DSA).

Quantum Computing vs Classical Computing

Current state of Quantum Computing

Since the early days of quantum computing we have been told that a functional quantum computer is just around the corner and the existing encryption systems will be broken soon. There has been significant investment in the field of Quantum computers in the past few years, with organizations like Google, IBM, Amazon, Intel and Microsoft dedicating a significant amount of their R&D budget to create a quantum computer. In addition, the European Union has launched a Quantum Technologies Flagship program to fund research on quantum technologies (Quantum Flagship Coordination and Support Action, 2018).

As of September 2020, the largest quantum computer is comprised of 65 qubits and IBM has published a roadmap promising a 1000 qbit quantum computer by 2023 (Cho, 2020). While this is an impressive milestone, we are still far away from a fully functional general use quantum computer. To give an idea of how far we still have to go Shor’s algorithm requires 72k3 quantum gates to be able to factor a k bits long number (Shor, 1994). This means in order to factor a 2048-bit number we would need a 72 * 20483 = 618,475,290,624 qubit computer which is still a long way off in the future.

Challenges in Quantum Computing

There are multiple challenges in creating a quantum computer with a large number of qubits as listed below (Clarke, 2019):

  • Qubit quality or loss of coherence: The qubits being generated currently are useful only on a small scale, after a particular no of operations they start producing invalid results.
  • Error Correction at scale: Since the qubits generate errors at scale, we need algorithms that will compensate for the errors generated. This research is still in the nascent stage and requires significant effort before it will be ready for production use.
  • Qubit Control: We currently do not have the technical capability to control multiple qubits in a nanosecond time scale.
  • Temperature: The current hardware for quantum computers needs to be kept at extremely cold temperatures making commercial deployments difficult.
  • External interference: Quantum computes are extremely sensitive to interference. Research at MIT has found that ionizing radiation from environmental radioactive materials and cosmic rays can and does interfere with the integrity of quantum computers.

Cryptographic algorithms vulnerable to Quantum Computing

Symmetric encryption schemes impacted

According to NIST, most of the current symmetric cryptographic algorithms will be relatively safe against attacks by quantum computer provided a large key is used (Chen et al., 2016). However, this might change as more research is done and quantum computers come closer to reality.

Asymmetric encryption schemes impacted

Unlike symmetric encryption schemes most of the current public key encryption algorithms are highly vulnerable to quantum computers because they are based on the previously mentioned factorization problem and calculation of discrete logarithms and both of these problems can be solved by implementing Shor’s algorithm on a quantum computer with enough qubits. We do not currently have the capability to create a computer with the required number of qubits due to challenges such as loss of qubit coherence due to ionizing radiation (Vepsäläinen et al., 2020), but they are a solvable problem looking at the ongoing advances in the field and the significant effort being put in the field by companies such as IBM and others (Gambetta et al., 2020).

Post Quantum Cryptography

The goal of post-quantum cryptography is to develop cryptographic algorithms that are secure against quantum computers and can be easily integrated into existing protocols and networks.

Quantum proof algorithms

Due to the risk posed by quantum computers, the National Institute of Standards and Technology (NIST) has been examining new approaches to encryption and out of the initial 69 submissions received three years ago, the group has narrowed the field down to 15 finalists and has now begun the third round of public review of the algorithms (Moody et al., 2020) to help decide the core of the first post-quantum cryptography standard. They are expecting to end the round with one or two algorithms for encryption and key establishment, and one or two others for digital signatures (Moody et al., 2020).

Quantum Key Distribution

Quantum Key Distribution (QKD) uses the characteristics of quantum computing to implement a secure communication channel allowing users to exchange a random secret key that can then be used for symmetrical encryption (IDQ, 2020). QKD solves the problem of secure key exchange for symmetrical encryption algorithms and it has the capability to detect the presence of any third party attempting to eavesdrop on the key exchange. If there is an attempt by a third-party to eavesdrop on the exchange, they will create anomalies in the quantum superpositions and quantum entanglement which will alert the parties to the presence of an eavesdropper, at which point the key generation will be aborted (IDQ, 2020). The QKD is used to only produce and distribute an encryption key securely, not to transmit any data. Once the key is exchanged it can be used with any symmetric encryption algorithm to transmit data securely.

Conclusion

Development of a quantum computer may be 100 years off or may be invented in the next decade, but we can be sure that once they are invented, they will change the face of computing forever including the field of cryptography. However, we should not panic as this is not the end of the world as the work on quantum resistant algorithms is going much faster than the work on creating a quantum computer. The world’s top cryptographic experts have been working on Quantum safe encryption for the past three years and we are nearing the completion of the world’s first post-quantum cryptography standard (Moody et al., 2020). Even if the worst happens and it is not possible to create a quantum safe algorithm immediately, we still have the ability to encrypt and decrypt data using one-time pads until a safer alternative or a new technology is developed.

References

Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016). Report on Post-Quantum Cryptography. https://doi.org/10.6028/nist.ir.8105

Cho, A. (2020, September 15). IBM promises 1000-qubit quantum computer-a milestone-by 2023. Science. https://www.sciencemag.org/news/2020/09/ibm-promises-1000-qubit-quantum-computer-milestone-2023.

Clarke, J. (2019, March). An Optimist’s View of the Challenges to Quantum Computing. IEEE Spectrum: Technology, Engineering, and Science News. https://spectrum.ieee.org/tech-talk/computing/hardware/an-optimists-view-of-the-4-challenges-to-quantum-computing.

Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6), 644–654. https://doi.org/10.1109/tit.1976.1055638

Freiberger, M. (2017, October 1). How does quantum computing work? https://plus.maths.org/content/how-does-quantum-commuting-work.

Gambetta, J., Nazario, Z., & Chow, J. (2020, October 21). Charting the Course for the Future of Quantum Computing. IBM Research Blog. https://www.ibm.com/blogs/research/2020/08/quantum-research-centers/.

Garisto, D. (2020, May 4). Quantum computers won’t break encryption just yet. https://www.protocol.com/manuals/quantum-computing/quantum-computers-wont-break-encryption-yet.

IDQ. (2020, May 6). Quantum Key Distribution: QKD: Quantum Cryptography. ID Quantique. https://www.idquantique.com/quantum-safe-security/overview/quantum-key-distribution/.
Moody, D., Alagic, G., Apon, D. C., Cooper, D. A., Dang, Q. H., Kelsey, J. M., Yi-Kai, L., Miller, C., Peralta, R., Perlner R., Robinson A., Smith-Tone, D., & Alperin-Sheriff, J. (2020). Status report on the second round of the NIST post-quantum cryptography standardization process. https://doi.org/10.6028/nist.ir.8309

Nohe, P. (2019, May 2). What is 256-bit encryption? How long would it take to crack? https://www.thesslstore.com/blog/what-is-256-bit-encryption/.
Quantum Flagship Coordination and Support Action (2018, October). Quantum Technologies Flagship. https://ec.europa.eu/digital-single-market/en/quantum-technologies-flagship

Rijmenants, D. (2004). The German Enigma Cipher Machine. Enigma Machine. http://users.telenet.be/d.rijmenants/en/enigma.htm.

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. https://doi.org/10.1145/359340.359342

Rouse, M., Brush, K., Rosencrance, L., & Cobb, M. (2020, March 20). What is Asymmetric Cryptography and How Does it Work? SearchSecurity. https://searchsecurity.techtarget.com/definition/asymmetric-cryptography.

Shor, P. w. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, 124–134. https://doi.org/10.1109/sfcs.1994.365700

Singh, S. (2000). The code book: The science of secrecy from Egypt to Quantum Cryptography. Anchor Books.

Vepsäläinen, A. P., Karamlou, A. H., Orrell, J. L., Dogra, A. S., Loer, B., Vasconcelos, F., David, K. K., Melville A. J., Niedzielski B. M., Yoder J. L., Gustavsson, S., Formaggio J. A., VanDevender B. A., & Oliver, W. D. (2020). Impact of ionizing radiation on superconducting qubit coherence. Nature, 584(7822), 551–556. https://doi.org/10.1038/s41586-020-2619-8


Note: This was originally written as a paper for one of my classes at EC-Council University in Q4 2020, which is why the tone is a lot more formal than my regular posts.

– Suramya

September 12, 2020

Post-Quantum Cryptography

Filed under: Computer Related,Quantum Computing,Tech Related — Suramya @ 11:29 AM

As you are aware one of the big promises of Quantum Computers is the ability to break existing Encryption algorithms in a realistic time frame. If you are not aware of this, then here’s a quick primer on Computer Security/cryptography. Basically the current security of cryptography relies on certain “hard” problems—calculations which are practically impossible to solve without the correct cryptographic key. For example it is trivial to multiply two numbers together: 593 times 829 is 491,597 but it is hard to start with the number 491,597 and work out which two prime numbers must be multiplied to produce it and it becomes increasingly difficult as the numbers get larger. Such hard problems form the basis of algorithms like the RSA that would take the best computers available billions of years to solve and all current IT security aspects are built on top of this basic foundation.

Quantum Computers use “qubits” where a single qubit is able to encode more than two states (Technically, each qubit can store a superposition of multiple states) making it possible for it to perform massively parallel computations in parallel. This makes it theoretically possible for a Quantum computer with enough qubits to break traditional encryption in a reasonable time frame. In a theoretical projection it was postulated that a Quantum Computer could break a 2048-bit RSA encryption in ~8 hours. Which as you can imagine is a pretty big deal. But there is no need to panic as this is something that is still only theoretically possible as of now.

However this is something that is coming down the line so the worlds foremost Cryptographic experts have been working on Quantum safe encryption and for the past 3 years the National Institute of Standards and Technology (NIST) has been examining new approaches to encryption and data protection. Out of the initial 69 submissions received three years ago the group narrowed the field down to 15 finalists after two rounds of reviews. NIST has now begun the third round of public review of the algorithms to help decide the core of the first post-quantum cryptography standard.

They are expecting to end the round with one or two algorithms for encryption and key establishment, and one or two others for digital signatures. To make the process easier/more manageable they have divided the finalists into two groups or tracks, with the first track containing the top 7 algorithms that are most promising and have a high probability of being suitable for wide application after the round finishes. The second track has the remaining eight algorithms which need more time to mature or are tailored to a specific application.

The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER. The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow. These finalists will be considered for standardization at the end of the third round. In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+. These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round. NIST hopes that the announcement of these finalists and additional candidates will serve to focus the cryptographic community’s attention during the next round.

You should check out this talk by Daniel Apon of NIST detailing the selection criteria used to classify the finalists and the full paper with technical details is available here.

Source: Schneier on Security: More on NIST’s Post-Quantum Cryptography

– Suramya

September 1, 2020

Background radiation causes Integrity issues in Quantum Computers

Filed under: Computer Related,My Thoughts,Quantum Computing,Tech Related — Suramya @ 11:16 PM

As if Quantum Computing didn’t have enough issues preventing it from being a workable solution already, new research at MIT has found that ionizing radiation from environmental radioactive materials and cosmic rays can and does interfere with the integrity of quantum computers. The research has been published in Nature: Impact of ionizing radiation on superconducting qubit coherence.

Quantum computers are super powerful because their basic building blocks qubit (quantum bit) is able to simultaneously exist as 0 or 1 (Yes, it makes no sense which is why Eisenstein called it ‘spooky action at a distance’) allowing it process a magnitude more operations in parallel than the regular computing systems. Unfortunately it appears that these qubits are highly sensitive to their environment and even minor levels of radiation emitted by trace elements in concrete walls and cosmic rays can cause them to loose coherence corrupting the calculation/data, this is called decoherence. The longer we can avoid decoherence the more powerful/capable the quantum computer. We have made significant improvements in this over the past two decades, from maintaining it for less than one nanosecond in 1999 to around 200 microseconds today for the best-performing devices.

As per the study, the effect is serious enough to limit the performance to just a few milliseconds which is something we are expected to achieve in the next few years. The only way currently known to avoid this issue is to shield the computer which means putting these computers underground and surrounding it with a 2 ton wall of lead. Another possibility is to use something like a counter-wave of radiation to cancel the incoming radiation similar to how we do noise-canceling. But that is something which doesn’t exist today and will require significant technological breakthrough before it is feasible.

“Cosmic ray radiation is hard to get rid of,” Formaggio says. “It’s very penetrating, and goes right through everything like a jet stream. If you go underground, that gets less and less. It’s probably not necessary to build quantum computers deep underground, like neutrino experiments, but maybe deep basement facilities could probably get qubits operating at improved levels.”

“If we want to build an industry, we’d likely prefer to mitigate the effects of radiation above ground,” Oliver says. “We can think about designing qubits in a way that makes them ‘rad-hard,’ and less sensitive to quasiparticles, or design traps for quasiparticles so that even if they’re constantly being generated by radiation, they can flow away from the qubit. So it’s definitely not game-over, it’s just the next layer of the onion we need to address.”

Quantum Computing is a fascinating field but it really messes with your mind. So I am happy there are folks out there spending time trying to figure out how to get this amazing invention working and reliable enough to replace our existing Bit based computers.

Source: Cosmic rays can destabilize quantum computers, MIT study warns

– Suramya

October 15, 2019

Theoretical paper speculates breaking 2048-bit RSA in eight hours using a Quantum Computer with 20 million Qubits

Filed under: Computer Security,My Thoughts,Quantum Computing,Tech Related — Suramya @ 12:05 PM

If we manage to get a fully functional Quantum Computer with about 20 million Qubits in the near future then according to this theoretical paper we would be able to factor 2048-bit RSA moduli in approximately eight hours. The paper is quite interesting, although the math in did give me a headache. However this is all still purely theoretical as we only have 50-60 qBit computers right now and are a long way away from general purpose Quantum computers. That being said I anticipate that we would be seeing this technology being available in our lifetime.

We significantly reduce the cost of factoring integers and computing discrete logarithms over finite fields on a quantum computer by combining techniques from Griffiths-Niu 1996, Zalka 2006, Fowler 2012, EkerÃ¥-HÃ¥stad 2017, EkerÃ¥ 2017, EkerÃ¥ 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10−3, a surface code cycle time of 1 microsecond, and a reaction time of 10 micro-seconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction’s spacetime volume is a hundredfold less than comparable estimates from earlier works (Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3n+0.002nlgn logical qubits, 0.3n3+0.0005n3lgn Toffolis, and 500n2+n2lgn measurement depth to factor n-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

Bruce Schneier talks about how Quantum computing will affect cryptography in his essay Cryptography after the Aliens Land. In summary “Our work on quantum-resistant algorithms is outpacing our work on quantum computers, so we’ll be fine in the short run. But future theoretical work on quantum computing could easily change what “quantum resistant” means, so it’s possible that public-key cryptography will simply not be possible in the long run.”

Well this is all for now will post more later

– Suramya

May 27, 2019

Microsoft and Brilliant launch Online Quantum Computing Class that actually looks useful

Quantum computing (QC) is the next big thing and everyone is eager to jump on the bandwagon. So my email & news feeds are usually flooded with articles on how QC will solve all my problems. I don’t deny that there are some very interesting usecases out there that would benefit from Quantum Computers but after a while it gets tiring. That being said I just found out that Microsoft & Brilliant have launched a new interactive course on Quantum Computing that allows you to build quantum algorithms from the ground up with a quantum computer simulated in your browser and I feel its pretty cool and a great initiative. The tutorial enables you to learn Q# which is Microsoft’s answer to the question of which language to use for Quantum computing code. Check it out if you are interested in learning how to code in Q#.

The course starts with basic concepts and gradually introduces you to Microsoft’s Q# language, teaching you how to write ‘simple’ quantum algorithms before moving on to truly complicated scenarios. You can handle everything on the web (including quantum circuit puzzles) and the course’s web page promises that by the end of the course, “you’ll know your way around the world of quantum information, have experimented with the ins and outs of quantum circuits, and have written your first 100 lines of quantum code — while remaining blissfully ignorant about detailed quantum physics.”
Brilliant has more than 8 million students and professionals worldwide learning subjects from algebra to special relativity through guided problem-solving. In partnership with Microsoft’s quantum team, Brilliant has launched an interactive course called “Quantum Computing,” for learning quantum computing and programming in Q#, Microsoft’s new quantum-tuned programming language. The course features Q# programming exercises with Python as the host language (one of our new features!). Brilliant and Microsoft are excited to empower the next generation of quantum computer scientists and engineers and start growing a quantum workforce today.

Starting from scratch

Because quantum computing bridges the fields of information theory, physics, mathematics, and computer science, it can be difficult to know where to begin. Brilliant’s course, integrated with some of Microsoft’s leading quantum development tools, provides self-learners with the tools they need to master quantum computing.
The new quantum computing course starts from scratch and brings students along in a way that suits their schedule and skills. Students can build and simulate simple quantum algorithms on the go or implement advanced quantum algorithms in Q

Once you have gone through the tutorial you should also check out IBM Q that allows you to code on a Quantum computer for free.

– Suramya

August 7, 2015

Books For Non-Physicists Who Want To Understand Quantum Physics

Filed under: Interesting Sites,Quantum Computing — Suramya @ 1:37 AM

If you have ever wanted to understand Quantum Physics but found that all the physics gobbledy gook went over your head then you should check out this list of books by Chad Orzel that try to explain Quantum Physics to non-physicists.

Chad has also written a book on how to How to Teach Quantum Physics to Your Dog (Not sure why you would want to do that, but hey… who am I to judge). The title is interesting enough that I am tempted to buy it to check it out.

Example entry from the list:

How the Hippies Saved Physics by David Kaiser is, as the title promises, a highly readable look at the role counterculture and “New Age” thinking played in sparking the renewed interest in quantum foundations that started in the 1980′s and has exploded into the modern field of quantum information. While none of their colorful attempts to explain ESP through quantum phenomena actually pan out, showing why they can’t work proved surprisingly fruitful.

Check it out if you have some free time and want to learn.

– Suramya

March 23, 2008

Quantum Computing: Hype vs. Reality

A lot of you must have heard about quantum computing(QC) and a lot of articles have been written by people on how Quantum Computers could break any crypto in a short time. (Even I have written about it)

So I found the following blog post a really good read. It discusses the possible future of QC in a very interesting fashion with emphasis on how it might affect the world of Cryptology. Check it out over here: Emergent Chaos: Quantum Progress

Thanks to: Schneier on Security for the link.

– Suramya

Powered by WordPress