The rise of post-quantum cryptography
You may have heard that the future security of Internet is in danger because of the developments in quantum technologies. Let us dive into this topic and examine what danger an attacker with quantum computing power poses to the modern systems.
Pre-quantum cryptography
Cryptography invisibly surrounds almost all our actions in the digital world — accessing a website, authenticating to a website, digitally signing documents, approving bank transactions, exchanging messages with your friends, etc. There are two big families of cryptographic algorithms — symmetric cryptography and asymmetric cryptography. Asymmetric (or public key cryptography) allows secure connection to be created (1 step in the picture), while symmetric cryptography enables data transfer (2nd step in the picture).
The main public-key cryptographic algorithms that underly the security of Internet are key establishment and digital signature schemes. Key establishment allows parties, who want to securely communicate (for example, your browser and the server hosting website you want to access) agree on a secret key that can be used to encrypt messages exchanged during communication. Digital signature scheme, as the name suggests, allows creating digital signatures that are used for authenticity and data integrity properties. Most commonly used algorithms include RSA, DH, (EC)DSA, EdDSA, etc. All of those are vulnerable to the quantum attack presented by Peter Shor. Therefore, it is essential to plan and implement a protection against quantum computer attacks to our digital infrastructure.
Quantum adversary?
Quantum computers are built on principles of quantum mechanics and therefore have properties that cannot be achieved by classical computers. Quantum algorithms, that are set of instructions for quantum computers, are developed specifically to exploit those properties. The security of many cryptographic schemes relies on complex mathematical problems. Most common mathematical problems used in modern public key cryptography are integer factorisation and discrete logarithm problems. In 1994, Peter Shor published an algorithm that is able to break both those problems. And the quantum adversary is an attacker who has access to large enough quantum computer that is used to attack systems.
There are quantum algorithms that influence the security of symmetric primitives (hash functions, block ciphers) as well. Important distinction is that symmetric primitives are not completely broken by those algorithms, increasing key length will be enough to maintain security.
Post-quantum cryptography
To safeguard our future in presence of a sufficiently large quantum computer, we can use post-quantum cryptography. Those algorithms work on our classical computers and are secure against both classical and quantum adversaries. Fortunately, we already have upcoming standards for post-quantum algorithms for the main functionalities — digital signatures and key establishment. US National Institute of Standards and Technology (NIST) has initiated post-quantum standardisation competition in 2016. Many schemes for digital signatures and key agreement have been submitted to the competition and have undergone analysis by cryptographers around the world. In 2023, NIST announced algorithms that will be soon standardised: Crystals-Kyber for key agreement and several signature schemes — Crystals-Dilithium, Falcon and Sphincs+.
However, integrating post-quantum cryptography to our current infrastructure requires a careful approach. It is essential to take into account limitations of different systems (e.g., computational power, storage, backward compatibility) and maintain interoperability of the systems. Additionally, for more cryptographically complicated systems, like i-voting, and SmartID authentication and signing, switching to post-quantum algorithms is more challenging since having KEM and regular digital signature scheme is not enough. New post-quantum algorithms should be developed to fit into the existing infrastructure. Necessity of developing migration strategy and implementing post-quantum cryptography is an urgent priority.
Cybernetica's research
Cybernetica is currently investigating application of post-quantum cryptography to the various digital identity services as SplitKey, UXP and i-voting protocols.