Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

[Laurens Van Houtven <[e-mail]>]

Picking 1: #1. In order of preference: #1, #3, #2.

#2, for reasons already elucidated, is a non-starter. A collision-resistance constraint is nowhere near as painful as a one-shot constraint. #3 solves that, but at the expense of additional complexity.

lvh


> On May 20, 2015, at 2:16 PM, Alexey Melnikov <[e-mail]> wrote:
> 
> Signature schemes have, traditionally, hashed the message to be signed to
> a representative value and then actually signed that value. This has led
> to APIs that follow the Init, Update*, Final (IUF) pattern that allows for
> fragmented or very large messages to be signed with constant memory usage.
> 
> Alternatively, some signature schemes hash the message to be signed twice,
> where a prefix of the second hash depends on the result of the first.
> Ed25519 is an example of a scheme of this type. This typically allows the
> signature scheme to require fewer assumptions about the strength of the
> hash function that is employed. However, this approach implies that the signing
> algorithm would have to buffer the entire message. That could lead to
> unacceptable memory usage for applications that sign very large messages.
> 
> Penalising large messages might be seen as a positive by some because
> signing arbitrarily large messages invites implementations to process
> unauthenticated data because of its potential size. Also, designs that
> really wish to do this can always define that the message to be signed is
> actually a hash of the data. In doing so they would reintroduce the
> requirement that the hash function be collision resistant, but can
> implement an IUF API in constant space again.
> 
> On the other hand, if we wish a signature primitive to be easy to
> substitute into existing protocols then supporting a constant-space IUF
> API might be seen as a requirement.
> 
> Chairs wish to poll the group on the following topic (please pick one):
> 
> #1: The signature scheme should follow the traditional model of hashing
> the message to be signed, thus trivially supporting IUF APIs in
> constant-space, at the cost of requiring collision resistant hash
> functions.
> 
> #2: The signature scheme should not depend on collision resistance, at the
> cost of the signing algorithm having to buffer messages to be signed.
> 
> #3: option #2, but with an additional "large message" mode defined for
> protocols that feel that they need it, where the message to be signed is
> actually a hash of the true message.
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg