Re: [Cfrg] Alternatives to McGrew's hash based signatures

[David Leon Gil <[e-mail]>]

On Thu, Oct 9, 2014 at 11:54 AM, Zooko Wilcox-OHearn
<[e-mail]> wrote:
> To me, the idea that you have to guarantee that a state update (i.e. a
> previously unused sequence number or nonce) is durably written, or
> else you leak your private signing key to an attacker… that's a
> show-stopper. I disbelieve that any commodity hardware and software in
> use today can do that safely.

I don't think this is out of reach, really; the only trick is writing
the new key
to durable storage before you write the signature. (In fact, I'd write the key
to high-durability/availability distributed storage....wait. :)

(Getting to, say, a 2^-128, or other cryptographically small,
probability of failure
does seem out of reach.)

On Thu, Oct 9, 2014 at 4:41 AM, Alyssa Rowan <[e-mail]> wrote:
> Maybe we do: these are different schemes with different sets of desirable properties?

I think these schemes can be hybridized:

Take a stateful hash signature system (say tree-based); but use a small SPHINCS
instance at each leaf node. In that case, the size of the SPHINCS instances
only needs to be large enough for "misuse-resistance", not collision-resistance.
(It seems possible to, instead, embed stateful leaves into a SPHINCS
instance, but
perhaps less convenient unless the leaves are chains.)