# How to survive Quantum Apocalypse

Long wait is over! On July 5, 2022, the US National Institute of Standards and Technology (NIST) announced it will standardize [four quantum-safe cryptography algorithms](https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022), including:

* [Kyber](https://pq-crystals.org/kyber/) (a lattice based public-key encryption (PKE) and key-establishment algorithm) [Dilithium](https://pq-crystals.org/dilithium/)( a lattice based digital signature scheme),[Falcon](https://falcon-sign.info) (another lattice based digital signature scheme),[SPHINCS+](https://sphincs.org)( a hash based digital signature scheme).

As may you notice , NIST is very bullish on Lattices but also appriciate stateless hash based signature SPHINCS+ as an alternative.

NIST plans to standardize both Kyber and Dilithium first, followed by Falcon and SPHINCS+. Each standard isexpected to take roughly one year to complete. Changes in parameters are possible between the final standard and what is submitted to the 3rd round.
#
# What is Quantum Apocalypse

Our entire public key infrastructure is now built on the foundation of two mathematical problems: integer factorization and discrete logarithm problems. When you open an HTTPS connection, the TLS protocol is invoked, which negotiates a session key over an elliptic curve group using the Diffie-Hellman key exchange protocol. Another example, closer to our blockchain community, when you make an ETH transfer, you use your secret key to sign your transaction using the ECDSA digital signature scheme.

Peter Shor discovered an algorithm that finds the period of a given function in linear time over a quantum computer in 1994. This result implies that both the integer factorization and discrete logarithm problems are easily solved with quantum computers, thereby eliminating the need for the current PKIs. This can be really apocalyptic event for systems are not ready to quantum attacks.

In order to survive post-quantum attack big tech already started to implementaion and development of secure infrastructure, here is the one of example : [AWS Maven Project ](https://aws.amazon.com/blogs/security/how-to-tune-tls-for-hybrid-post-quantum-cryptography-with-kyber/) offers configuration and code example that will show you how to get started using our assembly-optimized, hybrid post-quantum TLS configuration with Kyber.

# The Realm of Lattices

---

[](https://zhenfeizhang.github.io/why)

---

In lattice-based systems, a popular strategy is for the user to take a common reference value "A" and a private value "s," and make public a value b = As + e that contains s (due to the As term) but "hide" it ( the e term). If s and e are "big enough," this effectively hides s; if s and e are "small enough," this public value b uniquely identifies s and allows signatures or shared secrets to be calculated. 

Because there is a broad range of values of s and e that are both large enough in the first sense and small enough in the second sense, lattice-based cryptography is made practical. This approach offers quantum resistance when compared to earlier ones, such the elliptic curve Diffie-Hellman algorithm. Additionally, it is provably secure in the sense that if a and e have specific forms, it can be demonstrated that breaking these "Ring Learning with Errors cryptosystems" is as difficult as solving an underlying lattice problem on random lattices, i.e. the attacker is not given an advantage by the special form of this problem.

Although this method is shown to be secure, it is significantly bigger than previous systems; a lattice-based key exchange takes roughly 2000 bytes in each direction, whereas an elliptic curve-based solution requires less than 100 bytes.The purpose of solutions is to reduce the amount of the payload. One option is to use rounding functions instead of errors.

Cryptographic proofs are subtle, nevertheless. Ring Learning with Errors cryptosystems' evidence is compromised when the probabilistic errors became deterministic. Practical challenges are still on the table with R-LWE and Computational Learning With Rounding over rings (R-CLWR) problems. However, The result is therefore a significant step forward in post quantum cryptography.

# Trust no one, Hail the Math Proofs!

As we know, cryptography world is not rainbows and unicorns. It is a dark forest filled with many adversaries.

Cryptographers are stubborn people, and we have good imaginations. So we’ve come up with a daydream, a way to pretend that random functions are practical — just for the purposes of our security proof.

Most of the time, cryptographers do not understand a lot of sophisticated mathematics that has been published in the mathematical literature. I consider myself to be one of the many cryptography researchers who do not comprehend as much mathematics as we should. So, sometimes all that is required is for someone to notice the application of existing theoretical arithmetic to these new cryptosystems. That is exactly what occurred here.

SIKE, which stands for Supersingular Isogeny Key Encapsulation, is now likely out of the race, owing to research published over the weekend by academics from KU Leuven's Computer Security and Industrial Cryptography lab. The study, titled [An Efficient Key Recovery Attack on SIDH (Preliminary Version)](https://eprint.iacr.org/2022/975), suggested a strategy for recovering the encryption keys protecting SIKE-protected transactions using difficult mathematics and a single standard PC. The entire procedure takes only approximately an hour. The achievement qualifies the researchers, Wouter Castryck and Thomas Decru, for a $50,000 Microsoft prize. Congratulations!

# A Hope in Hell : ZKPs

Zero-knowledge proofs were first conceived in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their paper "[The Knowledge Complexity of Interactive Proof-Systems](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf)".

[The Zero Knowledge Protocol (ZKP)](https://en.wikipedia.org/wiki/Zero-knowledge_proof) is a method of authentication in which no credentials are shared, meaning that they cannot be stolen. This is wonderful because it secures and protects your communication so that no one else can learn out what you're talking about or what files you're exchanging with each other. Like End to End encryption used in [iMessage, iCloud applications](https://blog.cryptographyengineering.com/2013/06/26/can-apple-read-your-imessages/) in Apple services, but more elegant.

ZKPs has many applications areas such as [Authentication Systems, Ethical Behaviour,Nuclear Disarmament, Blokchains( ZK-SNARKs.)
](https://en.wikipedia.org/wiki/Zero-knowledge_proof#History)
Let's dig deeper in [ZK-SNARKs](https://vitalik.eth.limo/general/2022/06/15/using_snarks.html):

[Private transactions](https://z.cash), [Verifiable Delay Function](https://eprint.iacr.org/2018/601.pdf), [Single Secret Leader Selection](https://eprint.iacr.org/2020/025.pdf), [zk-rollups](https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/zk-rollups/), [zkEVMs](https://vitalik.eth.limo/general/2022/08/04/zkevm.html), and other applications are made possible by zero knowledge proofs. There are several types of snark systems, which are divided into two categories:
>
> 1. Pairing or elliptic curve based, such as Groth16, vanilla PLONK, Marlin, BulletProof, etc.
> 2. Hash based, such as Stark and Plonky2.

Quantum computers will be able to attack the first category.

For both cases, moving to a quantum-safe snark system like[ Stark ](https://eprint.iacr.org/2018/046.pdf)or [Plonky2 ](https://github.com/mir-protocol/plonky2)provides solid answers, however significant work is required to concretize the solutions. But wait? What if [Lattice-Based Zero-Knowledge](https://eprint.iacr.org/2019/747)? Yes please ! And please see this creative way of introduction to the Scientific World :[Lattice-Based ZKPs Shorter, Simpler, and More General](https://www.youtube.com/watch?v=2uVsVYtedVQ&list=WL&index=10) by IBM Research Zurich.

# A Quantum Dream

Well, every cryptographer dreams to build a secure system which protects users from malicious attacks but cannot guarantee everlasting security, this is why being a realistic is very important in our World. You often hear lots of claims about Quantum Cryptography will end the game and solve all human beings problems: This is just a wishful thinking like this below:

>[ "Quantum cryptography solves the problem of key distribution by allowing the exchange of a cryptographic key between two remote parties with absolute security, guaranteed by the fundamental laws of physics."](https://arxiv.org/abs/1803.04520)

This statement is meaningless if the underlying theoretical definition of QKD is compatible with physical laws. An auditor who digs deeper into the "security proofs" will find no application of Maxwell's equations. This supports removing Maxwell's equations as a hypothesis, but it also strongly argues that Alice and Bob's hidden physical operations do not include any electricity or magnetism. How could one possible establish anything about the effects of electromagnetic operations without invoking the applicable physical laws?

Anyone who claims that the security of QKD is guaranteed by physical laws must rationally show that these physical acts by Alice and Bob are not QKD: the only physical actions that qualify as QKD are those that satisfy the assumptions of the theorems.

Let's be honest here, QKD is the core advertisement for quantum cryptography and we need to use our definitions carefully. We have a lots of brilliant minds working diligently and trying to build robust systems to replace retired systems with better ones. And we all know , security cannot be guaranteed. We can only mitigate risk of attacks. Let's say that we achieved to build robust Quantum Computers which I believe that we will, there still will be attacks such as optical(light) and signal(noise) by nature and adversaries will own their Quantum Computers( a.k.a goverments, Big Tech etc.) Lastly, For the sake of commercializing, we should not sacrifice the ["Security Proofs of QKD](https://www.etsi.org/deliver/etsi_gs/qkd/001_099/005/01.01.01_60/gs_qkd005v010101p.pdf)". This a call for the reality check!...

Until next time stay curios and think quantum!