The underlying principles of modern cryptography rely on fascinating mathematical problems which removes the dependency of covert key sharing between parties to communicate with utmost privacy even in the presence of an adversary.
To formulate such a system, Public Key Cryptography/Asymmetric Cryptography was released which used a pair of keys (pk, sk) where pk denotes the public key and (sk) is the secret key.
The Public Key is available to all the users but the private key is kept hidden. Both the keys are intertwined through a mathematical function such that encryption can be performed with the public key that can only be decrypted with the private key and vice versa.
The relationship between the public key and the private key is through a special kind of one-way functions called Trapdoor functions.
What are One way Functions?
One way functions possess this hardness property such that it is easy to compute the one-way function but hard to invert. ”Easy” corresponds to the fact that the function can be computed efficiently and ”hard” means that any algorithm attempting to invert it will succeed with a very small probability.
Trapdoor functions are one-way functions with additional trapdoor information which allows the inverse to be easily computed. Secure Public-Key Crypto systems are built using a one-way function that has a trapdoor.
Consider a public-key crypto system with a pair of keys generated by a key generation algorithm as (pk, sk). If Alice wants to send a message to Bob she uses the public key of Bob to encrypt the message. On other hand, Bob uses his private key pk to decrypt the message. Here pk is the trapdoor information with which the legitimate user Bob could decrypt the message in polynomial time.
The candidates of one-way functions and trapdoor functions used in modern cryptography are derived from number theory. Some of the examples of such functions are
* Discrete Logarithm Problem,
* Factorization and RSA
Discrete Logarithm Problem
Discrete Logarithm Problem is the construction behind the very first public-key cryptosystem primitive ”Diffie Hellman Key Exchange”.
It is based on finding x in the following equation where G is an element in a special algebraic structure called Fields where any power of x of G generates an element in that field.
Factorization and RSA
Imagine factoring 12 into its prime parts. Within a matter of seconds, one can properly answer 3 and 12. Again for a healthy brain exercise try to calculate the factorization of 128 -- may require some piece of paper, after computing that goes on to a number like 14567978. Here is where the problem starts.
Without a calculator or a program, it may take more than a few minutes to solve it. Similarly what if I say factorize a 1024 bits number? Now the situation is out of hand and it seems impossible without a method to solve it. RSA is based on this difficulty of factoring a large number. Of course with a trapdoor as a secret key which is the inverse of the number.
Can TrapDoors Expire?
Trapdoor functions are the basis of modern cryptography and in turn the heart of cryptographic applications like Blockchains. These functions have single-handedly upheld the security of such networks with goals ranging from encryption to identity management and authenticated transfers. These paradigms have been securing our data since its inception by Diffie-Hellman in the 1990s by iterating to better possibilities and to be universally applicable. But a series of twists have altered the thoughts from cryptographic agility to mere doubts on its security. In 1996, Peter Shor proposed a quantum algorithm that was able to solve the sorcery behind modern cryptography within a feasible time.
More precisely, to factor a number N, it takes a time complexity of O(log N).
In layman terms, it means an attacker can hijack your account within two hours.
So, How are we going to secure our credit card and other sensitive information while purchasing online? What about cryptocurrencies that at the core rely on these paradigms?
The answer to the above question lies in the concept of Post-Quantum cryptography which promises to secure our infrastructure from the quantum apocalypse.
Uniris realises this threat posed by quantum cryptography and has progressed in parallel to research in the field of cryptography by adding backward compatibility and giving choice to the users for the algorithms.
The 2nd article in this series will cover in detail more about Post-quantum cryptography and how it helps in Quantum-Resistant Blockchains.