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

[Rene Struik <[e-mail]>]

Dear colleagues:

I still do not understand some of the statements below. Please see 
inline (RS>>, <<RS).

I think having to buffer messages, as with some deterministic Schnorr 
scheme variants, would be highly undesirable. So, based on this I should 
vote against #2. However, I am not sure whether that statement, 
including logical implications, is correct. Similarly, if I wanted 
constant-size I/Os, as #1 seems to suggest, would I then always be stuck 
with requiring collision resistance? Or, do I just not understand what 
is meant with "buffering", and IUF "pattern" in the email poll below?

Best regards, Rene

On 5/20/2015 5:16 PM, Alexey Melnikov 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.
RS>> Isn't the double signing merely an artifact of running the Schnorr 
signature scheme in a mode where the ephemeral private key is 
deterministically derived from message and private info?
I don't see how this would apply with the original Schnorr scheme, since 
there one simply has s:= k - e d (mod n), where e=h(m,R), where R:=kG, 
where n size of prime-order subgroup, and where k is randomly picked. 
Only with deterministic versions, such as EdDSA, does one also have 
k=f(m,d), for some suitably chosen function f. So, buffering concerns 
only seem at play with deterministic signature schemes. Or, am I missing 
something here?
<<RS
>
> 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.
RS>> I do not understand this, since with non-deterministic schemes one 
does not seem to have this buffering issue on the signing side. For 
verification, obviously one needs to do some computations that depends 
on the entire data-to-be-signed into account, so one can only really 
release this data after positive result of the consistency check 
{whether or not one uses a deterministic or non-deterministic signature 
scheme}.
<<RS
> 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.
RS>>
The question seems to be whether requiring constant-space IUF would rule 
out particular solution directions. For non-deterministic Schnorr, where 
k is obtained from an independent RNG source, couldn't one simply 
compute e:=H(m,R) in a streaming fashion, assuming one has a pair (k, 
R:=kG) available?
<<RS

> RS>> Not sure whether the implicit assumptions underlying these choices.
<<RS

>
> 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.
RS>> Not sure whether this statement is universally correct.
<<RS
>
> #2: The signature scheme should not depend on collision resistance, at the
> cost of the signing algorithm having to buffer messages to be signed.
RS>> As suggested before, non-deterministic Schnorr seems to fall into 
this category, while not requiring buffering. Again, if I need stronger 
coffee, please let me know.
<<RS
>
> #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


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]