[CFRG] FW: I-D Action: draft-fluhrer-lms-more-parm-sets-12.txt

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

Didn’t realize he asked on the mailing list…

From: Scott Fluhrer (sfluhrer)
Sent: Friday, April 5, 2024 1:32 PM
To: Andrey Jivsov <[e-mail]>
Subject: RE: [CFRG] I-D Action: draft-fluhrer-lms-more-parm-sets-12.txt

No, 2**(192-t) is correct.

If we have a Quantum Computer that can perform 2**t successive hash computations, it could attack a space of size 2**(2t) using Grover’s algorithm (not counting constant factors, which in this case turn out to be pretty close to 1).
To cover the entire space of 192 bits, we would need 2**192 / 2**(2t) = 2**(192-2t) such Quantum Computers.
So, the total computation would be done by 2**(192-2t) Quantum Computers, each doing 2**t hash evaluations, for a total of 2**(192-t) hash evaluations.

From: Andrey Jivsov <[e-mail]<mailto:[e-mail]>>
Sent: Friday, April 5, 2024 12:47 PM
To: Scott Fluhrer (sfluhrer) <[e-mail]<mailto:[e-mail]>>
Subject: Re: [CFRG] I-D Action: draft-fluhrer-lms-more-parm-sets-12.txt

This is because if we limit
the time taken by Grover's algorithm to 2**t steps (for t < 96), then
to attack a hash preimage problem of 192 bits, it requires a total of
2**(192-t) hash computations (rather than the 2**(192/2) hash
computations it would require if we did not limit the time taken).
For example, if the adversary is willing to wait for the 2**64 times
the time taken by a hash computation, this implies that a total of
2**(192-64) = 2**128 hash computations will need to be performed
(performing the computations on 2**64 separate Quantum Computers,
each of which computes 2**64 hash evaluations).

I think that /2 is missing above.

2**(192-t) hash computations
needs to be

2**((192-t)/2) hash computations

2**(192-64) = 2**128
needs to be

2**((192-64)/2) = 2**64


Can h=15 be added, please?
LMS_SHA256_M24_H15
LMOTS_SHA256_N24_W4

Thank you.

On Fri, Apr 5, 2024 at 9:15 AM <[e-mail]<mailto:[e-mail]>> wrote:
Internet-Draft draft-fluhrer-lms-more-parm-sets-12.txt is now available. It is
a work item of the Crypto Forum (CFRG) RG of the IRTF.

   Title:   Additional Parameter sets for HSS/LMS Hash-Based Signatures
   Authors: Scott Fluhrer
            Quynh Dang
   Name:    draft-fluhrer-lms-more-parm-sets-12.txt
   Pages:   24
   Dates:   2024-04-05

Abstract:

   This note extends HSS/LMS (RFC 8554) by defining parameter sets by
   including additional hash functions.  These include hash functions
   that result in signatures with significantly smaller size than the
   signatures using the current parameter sets, and should have
   sufficient security.

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

The IETF datatracker status page for this Internet-Draft is:
https://datatracker.ietf.org/doc/draft-fluhrer-lms-more-parm-sets/

There is also an HTML version available at:
https://www.ietf.org/archive/id/draft-fluhrer-lms-more-parm-sets-12.html

A diff from the previous version is available at:
https://author-tools.ietf.org/iddiff?url2=draft-fluhrer-lms-more-parm-sets-12

Internet-Drafts are also available by rsync at:
rsync.ietf.org::internet-drafts


_______________________________________________
CFRG mailing list
[e-mail]<mailto:[e-mail]>
https://mailman.irtf.org/mailman/listinfo/cfrg