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

["Paul Hoffman" <[e-mail]>]

On 21 Jul 2017, at 14:01, Philip Lafrance wrote:

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

Thanks!

> 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."

Yes, great.

> 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)

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...)

> 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?

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).

>             -We should maybe consider replacing “large-scale” 
> quantum
> 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.

> -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.

This sounds great. Suggestions of text are welcome!

--Paul Hoffman