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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

> -----Original Message-----
> From: Daniel Van Geest <[e-mail]>
> Sent: Tuesday, October 02, 2018 12:41 PM
> To: Scott Fluhrer (sfluhrer) <[e-mail]>; [e-mail]
> Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt
> 
> Hi Scott,
> 
> That is a good savings.  We have implemented HSS and are interested in the
> 192-bit hash optimization.  If it was included we would definitely implement
> it.

My current thinking is that this isn't the time to add new parameter sets.  Instead, I was thinking about going an RFC with the current draft, and then do a follow-up RFC to define additional parameter sets (both truncated SHA-256, and also for SHA-512, which others have asked for).

Does the Research Group agree with this strategy?  If the Research Group generally agreed that the draft should reflect some or all of these additional parameter sets, we could certainly add them.

> 
> I'm also told by a colleague who implemented HSS that w=1 in the
> parameters doesn't give any speed advantage but has a large signature size
> disadvantage.  It takes (2^w)*p hashes to create a leaf node (including the
> hashing required to turn the a seed into the first node of a chain).  Thus per
> the parameters in the draft we have:
> w=1, p=265 => # hashes = 530
> w=2, p=133 => # hashes = 532
> On average the number of hashes for signature creation will be half those
> values.
> 
> So those two winternitz values are effectively equivalent in speed for both
> node and signature creation (in addition to the math, I've seen this
> confirmed in benchmarking).  But w=1 gives 8480 byte signatures and w=2
> gives 4256 byte signatures.
> 
> Given this, is there a reason not to remove w=1 from the parameters?

Actually, there's another use case where W=1 makes sense; FPGA image validation.

When an FPGA loads an image, we have a need to verify that the image is what the manufacturer intended.  One possibility is to use LMS to sign the image; have the public key burned into on-FPGA fuses, and have some hardware on the FPGA validate the image.  In this case, W=1 makes this validation logic simpler (and we don't really care much about the computation, or the signature size).

> 
> Thanks,
> Daniel
> 
> 
> On 2018-09-06, 9:24 PM, "Scott Fluhrer (sfluhrer)" <[e-mail]>
> wrote:
> 
> 
>     > -----Original Message-----
>     > From: Daniel Van Geest <[e-mail]>
>     > Sent: Thursday, September 06, 2018 2:17 PM
>     > To: Scott Fluhrer (sfluhrer) <[e-mail]>; [e-mail]
>     > 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.
> 
>     >
>     > 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?
> 
>     BTW: Sphincs+ already uses this; for their "NIST Level 3" parameter sets,
> they use 192 bit hashes.
> 
> 
>