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

"Paul Hoffman" <> Fri, 21 July 2017 16:27 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 5533C131B29 for <>; Fri, 21 Jul 2017 09:27:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id MpbJDsrBqGyc for <>; Fri, 21 Jul 2017 09:27:05 -0700 (PDT)
Received: from (Opus1.Proper.COM []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A3EFF131891 for <>; Fri, 21 Jul 2017 09:27:05 -0700 (PDT)
Received: from [] ([]) (authenticated bits=0) by (8.15.2/8.14.9) with ESMTPSA id v6LGQ8Vf051406 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Fri, 21 Jul 2017 09:26:11 -0700 (MST) (envelope-from
X-Authentication-Warning: Host [] claimed to be []
From: Paul Hoffman <>
To: Philip Lafrance <>
Date: Fri, 21 Jul 2017 18:26:56 +0200
Message-ID: <>
In-Reply-To: <>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 8bit
X-Mailer: MailMate (1.9.6r5347)
Archived-At: <>
Subject: Re: [Cfrg] Comments on draft-hoffman-c2pq-01
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 21 Jul 2017 16:27:07 -0000

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

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


> 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

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 

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