[Cryptography] Post Quantum Crypto

[Philipp Gühring]

Hi,

> > the scalability was demonstrated by D-Wave in the recent years
> 
> You should probably have noticed that D-Wave is building a machine that
> isn’t suitable for running Shor’s algorithm.

Yes, I am well aware that D-Wave´s processor architecture isn´t suitable
for Shor´s algorithm.
 
> As far as I know, it is an open problem if the D-Wave machine is
> suitable for anything. See Scott Aaronson’s blog.

>From my point of view, D-Wave isn´t a quantum computer that can run Shor´s
algorithm or Grover´s algorithm, but is a quantum computer in the larger
sense. Yes, those qubits are quite analog, I agree. So I would categorize
it as mixed-signal technology (both digital and analog). It´s not purely
analog, I would say.

The important thing D-Wave showed from my point of view is that Quantum
computers (albeit not the ones we cryptographers are interested in) are
scalable in practice. In 2007, it wasn´t clear, whether *any* kind of
quantum computer could be scalable to something larger than 5 Qubits. Now,
D-Wave has more than 1000 Qubits, so they prooved that there is at least
one kind of quantum computer that can be scaled up.

2 years ago, I worked myself through the D-Wave website for about 3 weeks,
reading and understand the papers and the architecture and scalability of
D-Wave´s chip design. I compared the technical details that D-Wave was
providing and the arguments the people who spoke against D-Wave, and back
then D-Wave´s documents looked more plausible, coherent and meaningful to
me. I´ve been personally studying electrical engineering and chip-design
for about 3 years now. There is a chance that I got it wrong, and it´s
likely that things will turn out differently, because inventions in the
future are hard to guess. But I think I invested a reasonable amount of
time and energy to research the topic myself to come to my own conclusions
about the topic, to be able to build a reasonable risk-analysis.


> That is not to say that quantum computers won’t be a problem, but
> your premise is faulty, so your reasoning does not apply.

I tried to keep the reasoning short, because I didn´t wanted to bore
people with details and wanted to concentrate on the crypto-related
things, if everyone agrees on the result of the risk-analysis already. It
seems I made it too short, so feel free to dig deeper and ask me more
questions, I don´t mind discussing it in more detail and explaining the
reasoning behind my risk-analysis more deeply.


> As for the question: How do we find a key exchange algorithm with the
> same properties as DH?
> 
> In general, you can turn any PKE with a reasonable message space into a
> two-move DH-like key exchange algorithm:
> 
> Alice generates a ephemeral key pair (ek, dk) and sends the public key
> ek to Bob.
> 
> Bob encrypts a random message x1 using Alice’s key ek to get c. Bob
> sends c to Alice.
> 
> Alice decrypts c to get x1.
> 
> Now Bob and Alice can both compute k = H(ek, c, x1).
> 
> Alice erases dk and x1. Bob erases x1.
 
> If the cryptosystem is reasonably secure, then this is secure against
> passive adversaries. You make it secure against active adversaries
> using digital signatures, just like with DH.
 
> The interesting question is: Can you do better than this, say like
> (H)MQV? Can you get more symmetry?

I think that the algorithm I designed is a bit more symmetrical, but
perhaps your algorithm is faster.

I just noticed that I hadn´t provided PDF versions of my papers and
slides, so here they are:

http://www2.futureware.at/PostQuantum/NTRU%20Key%20Exchange.pdf

Best regards,
Philipp Gühring