Re: [Cfrg] Signatures: curves, algorithms, etc

[Mike Hamburg <[e-mail]>]

On 01/30/2015 08:32 AM, David Leon Gil wrote:
> Some brief notes:
>
> 1. Hash functions. I'd really like to see a better hash function for 
> any options besides Ed25519. Two options for Ed25519:
>
> 1. Same point format. Keep the hash the same. Don't break compatibility.
>
> 2. New point format. Replace SHA2 with Blake2 or Prefix-MAC(SHAKE128).
>
> For higher security strength curves, the EC-Schnorr security proofs 
> suggest 2s hashing. Only SHAKE256 seems to work for that.
Which hashing step, the nonce derivation or the challenge?  And what's s?

The nonce needs to be close to uniform, but if the curve's order is 2^n 
+ ~2^(n/2) then even n bits would be enough.  Otherwise 1.5n bits are 
enough.

Is there a strong bound on the challenge?
> I mildly prefer EC-Schnorr to ECDSA, Franken- or not.
I also prefer EC-Schnorr, though I don't have a strong preference 
between Bernstein's formulation (kP, s) and Schnorr's (r,s).

I also think some users will be annoyed if we specify a Schnorr variant 
which precludes a streaming API.
> --
>
> 2. Signature schemes with coupons and tight reductions to CDH. Hashing 
> to an EC group is really easy with a variable-output-length keyed PRF. 
> (Does this have to be done in constant time?)
Not for signatures, though it leaks information about the (hash of) the 
message to be signed.  But you'd want to implement it in constant time 
so that SPEKE, SPAKE2 EE, Dragonfly and possibly EKE EE can use the same 
function.

By the way, usually for schemes where you hash to the curve, the hash 
doesn't need to be uniform or onto, just kinda-almost-onto and 
not-too-nonuniform.  (It's where the discrete log challenge is injected 
through the ROM, but ECDLP is randomly self-reducible so the challenger 
can easily rejection sample.)  As a result, a single call to either SWU 
or Elligator (1 or 2) is good enough.  This is pretty easy to do in 
constant time, with a single exp, and with only a field element's worth 
of hash output.

If you need a uniform hash, the BCIMRT solution is to hash twice and add.

See for example:
http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/src/decaf.c
http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/include/decaf.h
"decaf_point_from_hash_[non]uniform".
> Pointcheval(?) has an interesting scheme involving 'coupons', in which 
> all scalar muls can be done *before* signing a message. The scheme has 
> a tight reduction to CDH.
Link?  I'm most familiar with 
https://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf, but it's not by 
Pointcheval and its couponized sigs are only reducible to DDH.
> This strikes me as potentially much more efficient than even 
> Schnorr-EC for signers: The scalarmuls are no longer in the critical 
> path. So you get asymmetric signatures for (very slightly more than) 
> the latency of computing a MAC[*]
>
> [*] Note that this means you can compute coupons at periods of low 
> computational demand, which may be a substantial cost savings.
You can use coupons with Schnorr or even with ECDSA.  I've suggested its 
use in my company's products to reduce latency.  Though a tight 
reduction to CDH would be nice.

Cheers,
-- Mike
> David Leon Gil
> Senior Paranoid
> Yahoo!
>
> PS. Sending via Gmail because the CFRG mailing list software attempts 
> to forge @yahoo-inc.com <http://yahoo-inc.com> FROM addresses. And 
> Yahoo sets a DMARC p=reject. Could a list admin please configure the 
> IRTF listserv to not blatantly violate the IETF DMARC standard?
> On Thu, Jan 29, 2015 at 9:27 PM Damien Miller <[e-mail] 
> <mailto:[e-mail]>> wrote:
>
>     On Tue, 27 Jan 2015, Tony Arcieri wrote:
>
>     > I would like to hear the opinions of the chairs and other CFRG
>     participants
>     > on the following:
>     > - Ed25519 and EdDSA
>     > - FrankenECDSA (ECDSA in Edwards)
>     > - ECDSA with Edwards keys on the wire (converted to Weierstrass
>     to do ECDSA)
>     > - Other interesting thoughts on digital signatures
>
>     As you probably already know OpenSSH is already using Ed25519 for
>     user and host authentication. We chose it because:
>
>     1) It's secure; well-reviewed and based on good "bones" (e.g.
>     Schnorr sigs)
>     1a) It avoids the terrible failure modes of DSA/ECDSA
>     1b) It's hard for implementors to get wrong
>     2) It's fast
>     3) There are excellent reference implementations available
>
>     We're not interested in adding more DSA/ECDSA variants unless
>     there is some
>     compelling reason (and I don't see any). EdDSA just seems a better
>     algorithm.
>
>     We're not super-interested in WF >2^128 EdDSA either, but would
>     possibly
>     consider EdDSA at ~WF 2^256 if our users start asking for it.
>
>     We aren't likely to benefit from batch signing/verification.
>
>     -d
>
>
>     _______________________________________________
>     Cfrg mailing list
>     [e-mail] <mailto:[e-mail]>
>     http://www.irtf.org/mailman/listinfo/cfrg
>
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg