Subject: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt

From: [email-masked]
Date: Thu, 06 Sep 2018 10:31:20 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : Hash-Based Signatures
        Authors         : David McGrew
                          Michael Curcio
                          Scott Fluhrer
	Filename        : draft-mcgrew-hash-sigs-13.txt
	Pages           : 60
	Date            : 2018-09-06

Abstract:
   This note describes a digital signature system based on cryptographic
   hash functions, following the seminal work in this area of Lamport,
   Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in
   1995.  It specifies a one-time signature scheme and a general
   signature scheme.  These systems provide asymmetric authentication
   without using large integer mathematics and can achieve a high
   security level.  They are suitable for compact implementations, are
   relatively simple to implement, and naturally resist side-channel
   attacks.  Unlike most other signature systems, hash-based signatures
   would still be secure even if it proves feasible for an attacker to
   build a quantum computer.

   This document is a product of the Crypto Forum Research Group (CFRG)
   in the IRTF.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-mcgrew-hash-sigs-13
https://datatracker.ietf.org/doc/html/draft-mcgrew-hash-sigs-13

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-mcgrew-hash-sigs-13

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 6 Sep 2018 17:39:44 +0000

This update provides a set of clarifications and nit-fixes that were requested by reviewers.

It does not address any 'mandatory to implement' issues; nor does it address concerns from IANA (which I'm still not quite sure what they are...)

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of [email-masked]
> Sent: Thursday, September 06, 2018 1:31 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Daniel Van Geest <[email-masked]>
Date: Thu, 6 Sep 2018 18:16:35 +0000

On the topic of options (and the possible addition of more, sorry), Scott wrote this paper https://eprint.iacr.org/2017/811.pdf (Grover's algorithm doesn't parallelize well, so it is possible to truncate hashes and still maintain 128 bits of quantum security).  The results could be used to reduce a Sphincs signature from 41000 bytes to about 23k.  How would it affect HSS signature sizes?

If it has a significant effect, is it worth adding as an option?

What does CFRG think of the paper's results?  Are they worth applying to XMSS or any future hash-based signature algorithms which come through here?

Thanks,
Daniel

On 2018-09-06, 7:40 PM, "Cfrg on behalf of Scott Fluhrer (sfluhrer)" <[email-masked] on behalf of sfluhrer=[email-masked]> wrote:

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 6 Sep 2018 19:24:20 +0000

> From: Daniel Van Geest <[email-masked]>
> Sent: Thursday, September 06, 2018 2:17 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>; [email-masked]
> Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt
> 
> On the topic of options (and the possible addition of more, sorry), Scott
> wrote this paper https://eprint.iacr.org/2017/811.pdf (Grover's algorithm
> doesn't parallelize well, so it is possible to truncate hashes and still maintain
> 128 bits of quantum security).  The results could be used to reduce a Sphincs
> signature from 41000 bytes to about 23k.  How would it affect HSS signature
> sizes?

Reduces it by perhaps 40%.  For example, for H=20 (W=8, single level), it reduces the signature size from 1776 bytes to 1144 bytes.

> What does CFRG think of the paper's results?  Are they worth applying to
> XMSS or any future hash-based signature algorithms which come through
> here?

BTW: Sphincs+ already uses this; for their "NIST Level 3" parameter sets, they use 192 bit hashes.