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? 



Will quantum computing kill cryptography ?
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. 


