Suramya's Blog : Welcome to my crazy life…

September 12, 2020

Post-Quantum Cryptography

Filed under: Computer Related,Quantum Computing,Techie Stuff — 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,Techie Stuff — 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 — 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

Filed under: Computer Security,Interesting Sites,Quantum Computing — Suramya @ 1:23 PM

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