9
$\begingroup$

Is there some definition or theorem about what a quantum computer can achieve from which post-quantum cryptographic schemes (eg lattice cryptography, but not quantum cryptography) can justify their security? I know the period finding function is capable of breaking RSA and discrete logs, but is it the only algorithm relevant to breaking encryption schemes? Can I say that if a scheme is not susceptible to the period finding function it is not susceptible to quantum computing? If not, is there some similar, alternative statement of the form "if an encryption scheme cannot be broken by algorithm X, it cannot be broken by quantum computing"?

For example, is it sufficient to prove that an encryption scheme can only be broken by trying all possible keys, and the best that quantum computing can do in this regard is square root search time with Grover's algorithm?

$\endgroup$
  • 1
    $\begingroup$ You have inspired me to ask this question. $\endgroup$ – user1271772 Jun 29 '18 at 5:01
  • $\begingroup$ Related: crypto.stackexchange.com/questions/30055/… . In short: most crypto-systems are proven secure by assuming some problem is 'hard'. However, the hardness of that problem is usually based more on empirical arguments (e.g. 'we don't know how to solve this'), rather than theoretical arguments from computational complexity theory. $\endgroup$ – Discrete lizard Jun 29 '18 at 13:02
5
$\begingroup$

This is essentially the realm of computational complexity classes. For example, the class BQP may crudely described as the set of all problems that can be efficiently solved on a quantum computer. The difficulty with complexity classes is that it's hard to prove separations between many classes, i.e. the existence of problems which are in one class but not another.

In a sense, it is sufficient to be able to say "if this quantum algorithm cannot break it, it is safe", you just have to use the right algorithm. You need a BQP-complete algorithm such as finding roots of the Jones polynomial - any quantum algorithm can be cast as an instance of a BQP-complete algorithm. However, how that algorithm might be used for the cracking is completely unclear and non-trivial. It's not enough to see that you can't directly brute force things. So, that approach is probably not so helpful.

What do we want from a post-quantum crypto scenario? We need:

  • a function $y=f(x)$ that we can easily compute for the purposes of encryption.
  • for which the inverse, $f^{-1}(y)$ cannot easily be computed on a quantum computer, i.e. the problem class is outside BQP.
  • given some secret, $z$, there is a classically efficiently computable function $g(y,z)=x$, i.e. with the supplementary information, the function $f(x)$ can be inverted. This is so that the right person (who has the private key, $z$) can decrypt the message.

This last bullet is (essentially) the definition of the complexity class NP: the problems for which it may be hard to find a solution, but for which a solution is easily verified when given a proof (corresponding to the private key in our case).

So, what we're after are problems in NP but not in BQP. Since we don't know if NP=BQP, we don't know that such things exist. However, there's a good route for looking at solutions: we consider NP-complete problems. These are the hardest instances of problems in NP, so if BQP$\neq$ NP (which is widely believed to be the case), NP-complete problems are certainly not in BQP. (If a problem is complete for a complexity class, it means that if you can solve it efficiently, you can solve all instances of the class efficiently.) So, this is kind of the guidance for where one might look for post-quantum algorithms.

The additional subtlety that complicates matters, however, is roughly (I'm not an expert) that complexity classes talk about worst case complexity, i.e. for a given problem size, it's about how hard the hardest possible instance of the problem is. But there could be only one such problem instance, which would mean that if we fix the problem size (as is standard, e.g. you might talk about 1024 bit RSA; the 1024 bits is the problem size), there's only be one private key. If we know that, an eavesdropper can just use that private key to decrypt messages. So, we actually need that this computational complexity reasoning applies for a large proportion of possible inputs. This gets you into the world of average-case complexity where, as I understand it, it becomes much harder to make such statements.

It may help to make a comparison to RSA, a public key crypto-system, and ignoring the existence of quantum computers. It is based on the difficulty of factoring large composite numbers. This problem is not (believed to be) in P, so it is believed to be difficult for a hacker with a classical computer to get at the answer. Meanwhile, it is in NP because the solution is readily verified (if you're given one factor, you can easily check it's a factor). That means it can be decrypted using a classical computer by the rightful recipient.

$\endgroup$
4
$\begingroup$

Is there some definition or theorem about what a quantum computer can achieve from which post quantum cryptographic schemes (eg lattice cryptography, but not quantum cryptography) can justify their security?

No. Just because your post-quantum cryptographic scheme works today, doesn't mean Peter Shor won't find a quantum algorithm to break it tomorrow."

I know the period finding function is capable of breaking RSA and discrete logs, but is it the only algorithm relevant to breaking encryption schemes?

No. An example of another algorithm is Grover's algorithm, which is relevant to breaking cryptosystems based on the Transcendental Logarithm Problem.

Can I say that if a scheme is not susceptible to the period finding function it is not susceptible to quantum computing?

No. Schemes based on the Transcendental Logarithm Problem are not susceptible to period finding, but are susceptible to quantum enhanced speed-ups.

If not, is there some similar, alternative statement of the form "if an encryption scheme cannot be broken by algorithm X, it cannot be broken by quantum computing"?

No. We do not know every single quantum algorithm in possible existence. Even if a scheme is resilient to period finding and Grover's algorithm, it might be possible to use quantum computers to break it more efficiently than classical computers. We might just need to make Peter Shor interested enough to come up with a quantum enhanced decryption scheme for it.

Is it sufficient to prove that an encryption scheme can only be broken by trying all possible keys, and the best that quantum computing can do in this regard is square root search time with Grover's algorithm?

No. Just because a classical computer cannot break your scheme except by trying all possible keys, doesn't mean a quantum computer cannot.

Here is a question that does have a yes answer:

What can we do to prove that an encryption scheme is safe against quantum computers?

Answer: Prove that decrypting the code is a QMA complete or QMA hard problem. QMA hard problems are problems that are hard for quantum computers in the way that NP hard problems are hard for classical computers.

This has inspired me to ask this question, which I do not know the answer to!

$\endgroup$
  • $\begingroup$ Very succinct and to the point, especially with your question in bold. I also learned from the related question you asked. But for extra info and clarification of relevant complexity classes, I accepted the other answer. $\endgroup$ – Joseph Johnston Jun 30 '18 at 5:30

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.