The Riddle of Post-Quantum Cryptography
Riddle of Post-quantum Cryptography - A brief overview of What's and Who's.
One of our team members recently presented her Master's thesis titled "Securing Blockchains for Future" where the examiner quickly interrogated her by asking
“Are you questioning the foundations of cryptography built over the last two decades?” to which she was smart enough to quickly reply saying that: It would take 30 minutes to break the Elliptic Curve Discrete Log Problem by a quantum computer with a certain number of qubits and error rate. The inception of Post-Quantum cryptography lies in the mere scrapping of the 20 years of toiling done by cryptography researchers worldwide.
We have decided to start a series that covers the inception (Who’s and Why’s) of Post - Quantum cryptography
Before you dive deep into this article, we suggest you read Part 1 in the series called “Trapdoors and Cryptography” (https://www.linkedin.com/pulse/trapdoors-cryptography-uniris/?trackingId=HRfKix1x2r3qmoQv7yh9tg%3D%3D) to get a better understanding of the underlying principles involved in Modern Cryptography.
In Classical Cryptography, one-way functions and trapdoor functions are the key components of encryption and signature paradigms.
But in 1994 with the development of the Quantum computer, Peter Shor introduced an algorithm that factored any RSA in O(logn) simple operations on a quantum computer leading to the complete breakage of the scheme.
Fortunately, cryptography does not limit itself to the hardness of factorization and Discrete Log Problem but there are several classes of cryptographic schemes that work beyond the current mathematical paradigms whose hardness properties are resistant against quantum attacks. This domain of mathematical problems is the foundation to build Post Quantum Cryptography standards.
The goal of Post-quantum cryptography is securing our current systems from both classical and quantum adversaries without the usage of qubits or sophisticated quantum environments. Here, enterprises can move to secure alternatives against quantum adversaries in an efficient and granular manner with the existing infrastructure.
On the Spotlight
The so-called quantum-resistant cryptography utilizes open questions in various fields of mathematics from- Linear Algebra to Multivariate Equation and Mathematics of Elliptic curves.
The candidates on the spotlight are:
Hash-based Cryptography:
Introduced by Leslie Lamport in the 1970s, Hash-based cryptography is based on the security of hash functions but limited to only signature schemes. This scheme is best for crypto-agility because of its dependency on the underlying hash function thus if the hash is broken a stronger hash function can be replaced. Unfortunately, it leads to larger signature sizes and hence a lot of optimizations is required before its full ledged usage.
Code-based cryptography:
Developed in 1978, Code-based cryptography based on hard problems of coding theory which says that it is difficult to retrieve a message with random errors. McEllice's schemes were proposed 40 years ago and till now no attack has posed a serious threat on this system, not even quantum computers.
Multivariate Quadratic Equation-Based Cryptography:
Based on the difficulty of solving functions with multiple variables over a finite field instead of single-variable functions. This family is considered as one of the major families of Post Quantum Cryptography that could resist potentially even the powerful quantum computers of the future. The work arose in the 1980s by the combined effort of Shigeo Tsujii and Hideki Imai.
Lattice-Based Cryptography:
Lattice-based cryptography is derived from special geometric constructions called lattices. The early works of Miklós Ajtai had introduced Lattices into realizing its importance in Computational problems. Further researchers recognized its application in cryptographic applications. These are one of the most promising post-quantum cryptography candidates with practical realisations. They possess strong security proofs based on worst-case hardness and have relatively efficient Implementation.
Elliptic Curve Isogeny based cryptography:
This young field that began in the 2000s has its roots in the widely used Elliptic Curve Cryptography(ECC). In 2011 Luca De Feo, David Jao, And Jer´Ome Plut presented Supersingular isogeny Diffie–Hellman key exchange (SIDH), a key exchange scheme parallel to Diffie-Hellman scheme except that it used Isogenies between two elliptic curves.
Zero-Knowledge Protocol based:
Researchers at MIT first started developing the concept of a zero-knowledge proof in the 1980s led by Shafi Goldwasser and Goldriech Micali. Zero-Knowledge protocols, proof the knowledge of a secret without leaking any part of the secret. Multiparty computation based systems used zero-knowledge protocols for proving their identity and integrity. The construction is generally prefered for post-quantum signature schemes. This paradigm is most suitable for applications where secure verification and privacy is important like Blockchains. Archethic makes use of zero-knowledge as a concept to provide identity management on a blockchain. Usage of zero-knowledge protocols could enhance it in terms of efficiency and computation.
NIST’s Post Quantum Standardisation process has taken a proactive step in this domain and opened up competition for cryptographic algorithms from the above paradigms. Currently, it's in the 3rd round of the process with the following algorithms as finalists:
Even if the above primitives are recognised to be quantum secure, it cannot be directly replaced because quantum safety comes with a price of large memory and computational cost making it infeasible for real-life implementations.
Secondly, due to the parallel growth of quantum computing research, there is a certain unpredictability that quantum algorithms against the above post-quantum schemes may be developed in the near future.
Therefore there is no guarantee that if these primitives are standardized then a quantum algorithm can’t break them. Keeping cryptographic agility into consideration, the complete migration to one of these schemes would not be a wise decision.
To achieve this agility, hybrid schemes are constructed such that they would provide sufficient quantum safety with acceptable cost and easier migration efforts.
For implementing such schemes into real-world applications, it was realised that not every one of the above suites is suitable for all applications. That means one uniform scheme cannot provide security for various kinds of applications. Therefore algorithms for applications should be chosen rather than making it universal.
The Race Among Candidates
All the above post-quantum candidates offer provable quantum security, but for real-world scenarios like cloud, IoT, blockchain and internet to sum up not all of these schemes are at the stage of direct implementation.
Super Singular Elliptic Curve Isogeny based Cryptography is computationally complex. Key Exchange Mechanism based on this requires more than 18 seconds on a 32-bit Cortex-M4 and more than 11 minutes on a 16-bit MSP430 making it impractical for resource-constrained devices.
For Hash-based Signature Schemes computationally, complexity is the biggest advantage, it could be utilized for applications requiring the faster generation of signatures. Still, it takes auxiliary memory to store hashes in the form of a tree and incurs a cost on the size of signatures.
Hash-Based Signatures like SPHINCS and XMSSS takes 41KB and 10KB of signature size respectively. Code-based Cryptography goes in the same lines of Hash-based cryptography with a high public key size of about 0.5MB that could lead to bigger cipher texts.
One of the most computationally efficient schemes selected for NIST’s 3rd Round is the Multivariate Cryptography based signature “Rainbow”. This scheme is most suitable for ubiquitous computing applications like RFIDs, smart cards and biometric identification applications because it incurs simple mathematical operations like multiplication and addition. Small devices used for authentication could be best suited for Multivariate schemes as it generates very low signature size. The only drawback of this scheme is its high public key size of about 100KB.
Zero-Knowledge Protocols provides privacy solutions especially for applications that require computation from various users. This kind of scenario often occurs in cloud infrastructures. Multiparty computation protocols with underlying zero-knowledge schemes offer authentication and privacy in such use cases. The signature scheme based on this paradigm is PICNIC- based on symmetric primitive with low computational cost and signature size.
The One You Can’t Ignore.
Among the candidates and algorithms mentioned in the above table, Lattice-based schemes seem to dominate overall, be it encryption or digital signature schemes mainly because of their efficient and agile implementations. For the upcoming internet revolution with Blockchains, Lattice schemes could be one of the algorithms that could be implemented in the near future.
Lattices provide low computational and memory costs with underlying quantum secure mathematical assumptions and modular implementation such that security can be increased by being at par with the adversary’s power.
Conclusion
Each of the above post-quantum schemes has its own virtues and adversities yet they are best suited for different applications ranging from RFIDs to fully-fledged data encryption engines and cloud computing applications. Therefore no single scheme can be announced to be universally agreed to be used in diverse applications, therefore hybridising schemes or using one scheme for a family of applications could be useful.
For example, Lattice Schemes could perform great for applications like Blockchains because of forward secrecy and minimal computational cost and memory cost but would not be able to fully cover the problems of blockchain-like privacy and pseudonymity.
Combining Lattice schemes with Zero-Knowledge Protocols could be a technique to ensure privacy and offer all security features of asymmetric cryptography with quantum resistance. Still, a lot of research and benchmarking is required for the above combination for realising their potential real P2P infrastructure.
We will discuss Lattice-Based Schemes and ZKP and their suitability, practical implementation over a wide range of applications especially for resource-constrained and agility driven applications like Blockchains and IoT in the next article of this series.
Archethic Public Blockchain
Archethic is a Layer 1 aiming to create a new Decentralized Internet.
Its blockchain infrastructure is the most scalable, secure & energy-efficient solution on the market thanks to the implementation of a new consensus: "ARCH".
Archethic smart contracts expand developers' boundaries by introducing internal oracle, time-triggers, editable content & interpreted language.
Through native integration for DeFi, NFTs & decentralized identity; Archethic offers an inclusive and interoperable ecosystem for all blockchains.
In order to achieve the long-term vision of an autonomous network in the hands of the world population, we developed a biometric device respecting personal data privacy (GDPR compliant).
Making the blockchain world accessible with the tip of a finger. Be the only key! https://www.archethic.net/
Archethic Foundation Non-profit in order to manage decentralized governance of the public blockchain
Do you want to learn more?
White Paper
Yellow Paper