This is a special episode in the Series: Quadrans Essentials! Make sure you have read the previous episodes in the series before diving into this one.
Episode 1: Series: Quadrans Essentials Unveils the Beauty and Magic of Peer-to-Peer Networks (P2P)
Episode 2: Series: Quadrans Essentials Brings You Post-Quantum Cryptography (a Movie on Secrets Vs. Technology)
Episode 3: Series: Quadrans Essentials Presents The Beauty and Magic of Public-Key Cryptography
Today the security of all sensitive data relies on encryption — whether it is credit card transactions, databases containing health and genomic data, or private conversations...
Classical computers would require an almost unimaginable amount of time to unravel the cryptographic algorithms that protect our data and digital systems, but Quantum computers exploiting qubits may rely on processing power that could break even today’s best encryption algorithms.
Would the spread of super-powerful Quantum computers capable of overcoming conventional cryptographic defences pose a threat to everyone’s security? Yes, but we are not unprepared to deal with it.
Quantum resistance is already considered the next level of security standards addressed as critical R&D to provide the highest level of security for the privacy of our data.
Quadrans blockchain infrastructure, a public, open-source and decentralised platform for Smart Contracts and dApps, has been designed to be Quantum-Proof ready and make use of special post-quantum signature algorithms based on lattice theory, linear codes, and polynomial equations.
What does this all mean? How is a robust cypher capable of withstanding Quantum attacks designed?
Cryptography and Mathematics
The relationship between Cryptography and Mathematics was not obvious from the beginning. It took until 1939 for Adrian A. Albert to present his Keynote Speech at the Conference of the American Mathematical Society in which he stated:
We shall see that Cryptography is more than a subject permitting mathematical formulation, for indeed it would not be an exaggeration to state that abstract Cryptography is identical with abstract Mathematics.
Ten years later, the same thought was taken up and expanded by C. Shannon with his landmark paper “Communication Theory of Secrecy Systems” which stated:
The problem of good cipher design is essentially one of finding difficult problems. We may construct our cipher in such a way that breaking it is equivalent to solving laborious problems.
Thus, to construct a good cryptographic code, very difficult mathematical problems need to be used.
When a code is constructed based on a very difficult mathematical problem, it is difficult for the attackers to crack the code as the underlying mathematical problem is extremely hard.
So some questions arise: what makes mathematical problems hard? Are there any very difficult problems? Well, for a long time we didn’t have any…
All is not as it seems
As the years passed, mathematicians and cryptographers added necessary pieces to arrive in 1971 at the definition of what a “difficult and laborious problem” is — and it became clear that there are two kinds of such problems.
1- Problems that we “think” are difficult
There are problems that we believe to be hard. We think that factoring a product of large primes is hard, that finding discrete logarithm is hard, etc.
Often these problems are related to Number Theory — but there is no underlying reason why these problems should be hard!
2- Problems that we can “prove” are difficult
In mathematical terms, they are called NP-hard problems.
In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally “at least as hard as the hardest problems in NP”.
These are problems arising mainly from lattice theory, linear codes, or polynomial equations.
The Quantum Threat
We now enter the heart of the conversation. When cryptographers started doing modern Cryptography in 1976, they based most cryptographic systems on problems that they believed to be hard — but we don’t know if they truly are.
And the funny thing is — a Quantum computer could easily break all the problems that are based on:
- Discrete Logarithm in Finite Fields;
- Discrete Logarithm in Elliptic Curves;
- Integer Factorisation;
- And other Number Theory stuff.
Blockchain Applications & Post-Quantum Digital Signatures
Satoshi Nakamoto (2008), in his revolutionary paper “Bitcoin: a Peer-to-Peer Electronic Cash System” brought into the world the first blockchain — this immutable and infinite digital ledger we all appreciate.
Let’s simplify Satoshi Nakamoto’s paper as much as possible to extrapolate the two cryptographic algorithms necessary for the creation of any blockchain, i.e.:
- Digital Signature
- Hash Function
The Digital Signature that was used for Bitcoin is based on the supposed hardness of problems related to elliptic curves. We don’t have any proof of the hardness of these problems.
Unfortunately, a Quantum computer could easily break Bitcoin’s signature and steal all the millions of Bitcoin in the world — that’s millions, trillions of dollars!
This flaw raises many security concerns and increases the need to find systems that can withstand a quantum attack.
However, as of today, we do not know what will withstand a quantum computer attack. What we do know is what will withstand a classical computer.
Can’t we start with that?
There are cryptographic algorithms, including digital signatures, which are based on problems whose hardness is mathematically proved.
Quantum computers do not have any significant advantage compared to classical computers when it comes to provably-hard problems. So, problems that are difficult for a classical computer, apparently are also difficult for a quantum computer.
This is what “Post-Quantum Cryptography” is all about — it wants to build cryptographic systems based on really hard problems that might resist quantum computer attacks.
Quadrans blockchain, a public, open-source, decentralised infrastructure for Smart Contract and dApps, was designed to be Quantum-Proof ready.
With solid input from members of the Crypto Board of the Quadrans Foundation, including the President of the Scientific Committee, Professor Massimiliano Sala, Quadrans blockchain was designed to contain within its architecture innovative encryption methods that have a chance to resist quantum computer attacks.
Quadrans exploits the flexible adoption of various digital signature algorithms to let each user balance security and computational cost.
In Quadrans Blockchain Yellow Paper a distinction has been made between transaction-signing and block-signing, requiring much higher levels of security for block signatures.
Considering the relative proportion between blocks and transactions (the former comprise hundreds of instances of the latter) we can employ signatures that consume much more block space without debilitating overall efficiency. For these reasons, Quadrans blocks must be signed with Post-Quantum secure algorithms.
In particular, the Quadrans team has worked on three families of post-quantum algorithms:
1- Digital Signatures based on Lattice Theory
Why do mathematicians like lattice theory? Well, there has been an important result in complexity theory recently that proves that random keys or random instances of a problem to be solved, are as hard to break as the worst-case keys.
However, in Cryptography, keys are constructed randomly, without necessarily searching for the worst-case scenario. There is thus a possibility that a randomly constructed key is very easy to break.
However, complexity theory is usually based on a worst-case analysis. Problems based on lattice theory show some tangible proofs that random keys are as hard to break as worst-case keys.
The United States is also considering adopting lattice-based systems as a new standard, so we decided to include digital signatures based on lattice theory within Blockchain Quadrans.
2- Digital Signatures based on Linear Codes
Quadrans digital signatures are not limited to lattices. We have also worked on signatures based on linear codes.
Linear codes don’t have this strong link between worst and average, but they have another advantage: it has been proved that if you provide a large part of the input or a large part of the key and provide infinite pre-processing, infinite time, infinite computers — all this will not help solve the problem.
Knowing part of the key is no advantage whatsoever in solving the problem. That’s why we’ve been working on this as well and have included digital signatures also based on linear codes in the Quadrans Blockchain.
3- Digital Signatures based on Polynomial
Finally, we have also studied signatures based on solving systems of binary polynomial equations — also called Multivariate Cryptography.
Well, these systems are less popular and one of the standards proposed called Rainbow has just been recently broken.
They don’t have any special properties like the other two families have, but we have proved that the main decision problem associated with an equation which is called MQ is isomorphic to the main decision problem used in linear codes, which is called MLD.
We have thus demonstrated the isomorphism between the two languages or, if you prefer, between the two problems that make this theory remarkable and fitting for inclusion among the digital signatures proposed in the Quadrans Yellow Paper.
To see the complete list of proposed Digital Signature Algorithms, please refer to Quadrans Yellow Paper section 3.1.1 Available Digital Signature Algorithms.
Today, there are a lot of critical systems that rely on vulnerable cryptography, including most blockchains that use either the Elliptic Curve Digital Signature Algorithm (ECDSA) for public-key Cryptography or some variant of it.
Quadrans is one of the blockchains focused on building quantum-resistant solutions. More specifically, Quadrans developers will support additional signature schemes in the future. Ensuring Quadrans blockchain is quantum computing-resistant is one of the top priorities as of right now.
This article is based on Full Professor of Mathematics Massimiliano Sala's Keynote Speech “Technical Overview on Post-Quantum Cryptography and Applications to Blockchain Technology” which was presented during the 5th Edition of the qBATS (Quantum & Biomedical Applications Technologies & Sensors) on June 20, 2022, in Lugano, Switzerland.
About 200 mathematicians, professors, and researchers from all over the world took turns on stage to present the latest innovations in the Quantum and Biomedical fields.
The Quadrans blockchain was presented in its most unique features, such as being Quantum-Proof ready and making use of special digital signatures based on complex mathematical theories.
A recording of his speech can be seen here:
About Prof. Massimiliano Sala
- Full Professor of Mathematics and Head of the Laboratory of Cryptography of the Department of Mathematics at the University of Trento — the “CryptoLabTN” is the first and so far only Cryptography centre in Italy, established back in 2010 and now composed of more than 20 young researchers;
- Acting Director of the Italian association “De Componendis Cifris” — the national initiative aims to nurture the Italian cryptographic community and develop robust and flexible cyphers suitable for the modern era, fostering the rise of new talent dedicated to the cryptographic sciences.
- Consultant in Cryptography and Cyber Security — covers activities including design, security, and evaluation of algorithms and protocols, analysis of Ransomware and Malware, and decryption of files.
- President of the Crypto Board of the Quadrans Foundation — within the Quadrans Crypto Board, the Scientific Committee of the Quadrans Foundation, are distinguished and international personalities who contribute to the research and development of the Quadrans infrastructure. Prof. Massimiliano Sala played a key role in the design of the Quadrans blockchain architecture and the development of the unique features presented in the Quadrans Blockchain Yellow Paper.
