Subject: [Cfrg] Comments on draft-hoffman-c2pq-01

From: Philip Lafrance <[email-masked]>
Date: Fri, 21 Jul 2017 08:01:18 -0400

Hello all,

So I can't express enough how much I support this document.

I gave it a cursory read and prepared some remarks (see below).

Since I was up at 3am today (IPSECME meeting was at 5:50 am my time) I kind
of want to go home and sleep. So, I'll give a more detailed review sometime
next week (hopefully with some input from my quantum crypto colleagues).

Comments:

Section 1.3

            -The definition given for “post-quantum cryptography” is pretty
limited and kind of inaccurate. The definition as given would suggest that
ECC is post-quantum as it does not rely on factoring large numbers or
determine the discrete log of a large composite number.

Maybe something like:

 "The term "post-quantum cryptography" refers to the invention and study of
cryptographic techniques (including encryption, signature and key exchange
algorithms) that are implementable on a classical computer and are based on
problems that are believed to be difficult for a quantum computer to solve.
In particular, this includes algorithms based on lattices, isogenies,
hash-functions, multivariate polynomial systems, and coding theory. It
excludes systems whose security relies on factoring numbers, or the
difficulty of determining the discrete log of one group element with
respect to another."

Section 1.6

            -The good folks at the Institute for Quantum Computing have a
good textbook which would be a nice reference (here is a link
http://hep.fcfm.buap.mx/cursos/2014/MCI/An_Intro_to_Quantum.pdf)

Section 2.1

            -This section seems to only be concerned with using quantum
algorithms to recover secret key. Why not also mention for example using
Grover to find collisions to forge signatures?

            -We should maybe consider replacing “large-scale” quantum
computer with “universal” quantum computer.

-Maybe some discussion about the differences between quantum annealing and
a universal quantum computer. This would be useful because, for example
D-Wave is a quantum annealer, not a universal quantum computer, but the
difference is lost on most people. Understanding the difference is
important if we’re talking about when to transition.

That's all for now.

All the best folks! Safe travels home from Prague!

-Philip Lafrance

---

From: "Paul Hoffman" <[email-masked]>
Date: Fri, 21 Jul 2017 18:26:56 +0200

> So I can't express enough how much I support this document.

Thanks!

> difficulty of determining the discrete log of one group element with

Yes, great.

> http://hep.fcfm.buap.mx/cursos/2014/MCI/An_Intro_to_Quantum.pdf)

That book is more limited (and, to my eye, harder to read) than the more 
popular Nielsen and Chuang. (Side-note: posting URLs to ripped copies of 
books is a bit tacky...)

> Grover to find collisions to forge signatures?

Finding collisions in greater than 2^128 quantum steps doesn't seem like 
an interesting threat (assuming that you are using a hash like SHA256 or 
better).

> computer with “universal” quantum computer.

I definitely need to work on the terminology here. I'll send out 
separate messages after I have incorporated some other off-list 
suggestions in this area that I have received.

> important if we’re talking about when to transition.

This sounds great. Suggestions of text are welcome!

--Paul Hoffman