1
$\begingroup$

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario.
Post-quantum cryptography like lattice-based cryptography is designed to be secure even if quantum computers are available. The Question that pops on my head are:

  • How can we define post-Quantum Cryptography?
  • What is the specification that makes it somehow impossible to break?
  • Can post Quantum Cryptography makes it somehow impossible to break for a long time?
$\endgroup$
4
$\begingroup$

How can we define post-Quantum Cryptography?

You pretty much included a relatively accurate informal gist in the sentence before this question:

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario.

The more interesting question follows:

What is the specification that makes it somehow impossible to break?

First a minor clarification: few algorithms are impossible to break in a conceptual sense - worst case scenario, guessing the key is always a viable strategy (the exceptions are one-time-pads and the analogous one-time authenticators). So it's a matter of cost rather than possibility, namely how much time it would require to defeat the system (space can also play a role in addition to time).

Post-Quantum cryptography usually refers to asymmetric algorithms (key agreement, public key encryption, and digital signatures) that are not known to be vulnerable to Shor's algorithm.

There are other quantum algorithms, but Shor's algorithm appears to be the main concern for cryptography.

The relevant mathematical problem appears to be "The Hidden Subgroup Problem":

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.

The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons:

  • Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
  • The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the $\operatorname{poly}(n)$ unique SVP.

So post-quantum algorithms are built from problems that aren't equivalent to the Hidden Subgroup Problem for finite Abelian groups.

Symmetric Algorithms

For symmetric algorithms, the relevant threat is Grover's algorithm, which provides a speed up for the generic brute force search. Defending against this is simpler than defending against Shor's algorithm: Simply double the size of your keys and hashes, and everything should be ok.

This is why AES-256 (and 256-bit keys in general) are recommended for "long-term security" - a 128-bit key could be broken for 64 bits worth of cost once your adversary has a full scale quantum computer capable of running Grover's algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.