14
$\begingroup$

I apologize as this question is not really mathematical, and therefore perhaps not well-suited for this site. Please feel free to close it if you think it is not. My reason for asking it here is that I am not satisfied (that is not convinced in any sense) by many discussions relative to that question I have seen on various forums (in particular some devoted to bitcoins),

So, the basic fact is that currently used method of cryptography, based on prime factorizations or elliptic curves, would not work anymore when a quantum computer is available, as proved by Shor. My main question is:

Do we know other cryptographic algorithms that would work in a world were quantum computers exist ?

If yes, will they be easy to implement quickly when quantum computers appear ? If not, are people working on this ? have we hope to find such algorithms anytime soon ? Is there some theoretical obstruction to the existence of such algorithm ?

To be honest, let me give more argument to close the question by indicating my motivation for asking this question, which is not mathematical. I am curious about the real-world implications of quantum-computers in particular on bitcoins. Cryptography is currently used in many transaction using real-world currencies and, by design, in all transactions using bitcoins. If cryptography became unusable because of the appearance of quantum computers, either for ever or for a sufficiently long period of time (in years), this would likely have enormous implication on the economy and the real world. To be sure, real money have worked for centuries without cryptography and if needed, one could go back to this. But cryptography and anonymity seems embedded in bit coin in a fundamental way, so would the appearance of quantum computers doom bitcoin?

Improve this question
$\endgroup$
17
  • 12
    $\begingroup$ Couldn't you try google first? en.wikipedia.org/wiki/Post-quantum_cryptography $\endgroup$
    – Felipe Voloch
    Commented Apr 20, 2013 at 15:56
  • 2
    $\begingroup$ Read the last chapter of Simon Singh's Code Book. $\endgroup$
    – Chandan Singh Dalawat
    Commented Apr 20, 2013 at 16:10
  • 3
    $\begingroup$ It should also be noted that considerable parts of todays cryptography would be completely unaffected by this. Only puplic-key cryptography and some related things [in the current form] would be affected. (This is also mentioned behind the link Felipe Voloch gives, but still I wanted to mention it here, mainly since I find the use of the unmodified word cryptography in the question unfortunate.) $\endgroup$
    – user9072
    Commented Apr 20, 2013 at 16:31
  • 1
    $\begingroup$ I am even more hesitant to comment on practical aspects of crypto than I am doing so regarding theoretical ones, but since I involved myself in this: one point was already made by Felipe Voloch (mainly sym crypto not asym crypto is used). To add to this the two main big 'standard' searches related to crypto I remember are the already mentioned AES (a sym crypto standard, no public key and much effect of QC there) and SHA-3 (hash function, same here). So, crypto not affected (in a substabtial way, there is some change by Grover's algorithm and so on but nothing 'major'; the double key... $\endgroup$
    – user9072
    Commented Apr 20, 2013 at 23:54
  • 1
    $\begingroup$ ...size Joe Silverman mentioned, to compensate the quadratic yet not exponential(!), as for factorization speed-up) seems quite relevant. Now, sure it is convenient and even somehow fascinating on purely abstract grounds that A and B can communicated shielded of from the rest of the world even if they never met before (asym crypto). But how relevant is this really in practise. I would say, in particular now as we are used to using the internet for all kinds of things, not so much. Sure if as of tomorrow these these things would stop working/being secure this would be a problem. However,... $\endgroup$
    – user9072
    Commented Apr 21, 2013 at 0:00

3 Answers 3

Reset to default
16
$\begingroup$

This question seems a bit vague, but one answer is that there are cryptosystems such as NTRU that are based on (special cases) of the closest vector problem (CVP). At present, quantum computers would not significantly speed up the solution of the CVP. If I understand correctly, they would require doubling the length of the keys.

Disclaimer: Jeff Hoffstein, Jill Pipher, and I are the ones who devised NTRU. But there are other lattice-based systems out there (though generally not as efficient). In any case, I think a good answer to your question is that you should look at lattice-based cryptography for examples.

Improve this answer
$\endgroup$
4
  • $\begingroup$ But isn't it the case that an efficient quantum algorithm for the dihedral hidden subgroup problem would break these vector cryptosystems? $\endgroup$
    – Sam Hopkins
    Commented Apr 20, 2013 at 18:00
  • 1
    $\begingroup$ Ummmm... Possibly, I'm not sure what the "dihedral hidden subgroup problem" is. But one might as easily say "a polynomial time quantum algorithm to solve CVP would break these cryptosystems." My point was that at the moment, we don't know a quantum algorithm that would break these lattice-based cryptosystems in subexponential time (much less polynomial time). Might such algorithms exist? Sure. But lacking lower bounds in complexity theory, all we can do is talk about the best known algorithms. OTOH, for factoring, DLP, and ECDLP, we already have poly time quantum algorithms. $\endgroup$
    – Joe Silverman
    Commented Apr 20, 2013 at 18:28
  • $\begingroup$ Fair enough. I know that there has at least been a good deal of research into breaking codes of this sort via quantum computers. See en.wikipedia.org/wiki/Hidden_subgroup_problem#Motivation. Although the crypto-optimist might as easily argue that the fact that there has been research but no results shows the systems to be safe. $\endgroup$
    – Sam Hopkins
    Commented Apr 20, 2013 at 18:49
  • 4
    $\begingroup$ Quantum algorithms for CVP and SVP have been studied since Shor's original paper, which points to them as interesting problems to study. But I would never try to argue that lattice-based cryptosystems are safe simply because some people have spent some time trying to break them. All that one can currently honestly say about any practical cryptosystem is that as of today, no one has publicly given an algorithm that breaks it. (Notice both the phrase "as of today" and the word "publicly" in that last sentence!) $\endgroup$
    – Joe Silverman
    Commented Apr 20, 2013 at 19:09
13
$\begingroup$

There is a very good book that you can find your answer there completely. This book's name is:

"Post-Quantum Cryptography" by "Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen".

As a part of this book, today we know that these cryptosystems can be broken by quantum computers:

$1)$ RSA public key encryption

$2)$ Diffie-Hellman key-exchange

$3)$ Elliptic curve cryptography

$4)$ Buchmann-Williams key-exchange

$5)$ Algebraically Homomorphic

and these cryptosystems (and also with some variants) are safe:

$1)$ McEliece public key encryption

$2)$ NTRU public key encryption

$3)$ Lattice-based public key encryption

Also, the good cryptosystems is not usable today because of the storage space problem and complexity. We have some limit on quantum computers that help us to design some good cryptosystems. There are some problems that if we have very large quantum computer and the best quantum algorithm,still we need exponential time for solving them. For example, searching among very large database to find special data, is very hard problem for quantum computer. We can prove that if we have $N$ cases that there is only one suitable case, the best quantum algorithm need $O(N^\frac{1}{2})$ to solve it. Also, it is proved that there is not better result. So, we can hope that we can find some efficient algorithms against the power of quantum computer and quantum algorithms.

Improve this answer
$\endgroup$
0
7
$\begingroup$

There is a web site and conference series on post-quantum cryptography, leading up to Bernstein et al's book mentioned by Shahrooz. See:

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great site: the first paragraph contains the answer to all my questions to and concerns. $\endgroup$
    – Joël
    Commented Apr 20, 2013 at 23:22

Not the answer you're looking for? Browse other questions tagged .