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

Daniel Van Geest <Daniel.VanGeest@isara.com> Tue, 02 October 2018 16:41 UTC

From: Daniel Van Geest <Daniel.VanGeest@isara.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, "cfrg@ietf.org" <cfrg@ietf.org>
Thread-Topic: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt
Thread-Index: AQHURgd0Wlc1oDVkL0im/uX/5JYnL6TjyDEAgAAr1AD///FlAIAo0IGA
Date: Tue, 02 Oct 2018 16:40:58 +0000
Message-ID: <17F09E9B-91F6-4180-A10F-C5A83EC38D53@isara.com>
References: <153625508014.11624.7422048043039435025@ietfa.amsl.com> <006c15b806634cc980aea19ac5a8daa8@XCH-RTP-006.cisco.com> <F4D0516F-44CB-4598-85ED-512C0D593371@isara.com> <ef30838fb11f40d8b6e6ae0d8e6023d6@XCH-RTP-006.cisco.com>
In-Reply-To: <ef30838fb11f40d8b6e6ae0d8e6023d6@XCH-RTP-006.cisco.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
Content-Type: text/plain; charset="utf-8"
Content-ID: <D9EBEB0CC33D1042897A068C2728CF6F@isara.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/CSjdmfhpPKlIr7illFMeKkfrVLM>
Subject: Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt
Precedence: list

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.

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?

Thanks,
Daniel

On 2018-09-06, 9:24 PM, "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> wrote:

    > -----Original Message-----
    > From: Daniel Van Geest <Daniel.VanGeest@isara.com>
    > Sent: Thursday, September 06, 2018 2:17 PM
    > To: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com>; cfrg@ietf.org
    > 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.

[Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.txt internet-drafts
Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.… Scott Fluhrer (sfluhrer)
Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.… Daniel Van Geest
Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.… Scott Fluhrer (sfluhrer)
Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.… Daniel Van Geest
Re: [Cfrg] I-D Action: draft-mcgrew-hash-sigs-13.… Scott Fluhrer (sfluhrer)