Subject: [Cfrg] Signature proposal

From: Watson Ladd <[email-masked]>
Date: Sun, 21 Jun 2015 20:54:59 -0700

Dear all,
I'm proposing the following signature scheme. This incorporates the
ideas of a number of people, but shouldn't be seen as endorsed by any
of them.

We write E: (-1)y^4+x^4=1+dx^2y^2 as the affine form of an Edwards
curve, possibly twisted over p. We represent values in F_p as
little-endian fixed width length vectors of bytes of the
representative in {0,1,\ldots p-1}. Define a value in F_p as negative
if its smallest representative is less than p-1/2, and positive
otherwise. We encode a point on E as the y coordinate followed by a
byte which is 0 if the x coordinate negative, 1 if the x coordinate
positive. Let q be the order of the large prime subgroup of E.

A signer has a public key A that is a point on E, and a private key
(v,k), where A=kG for G the generator of the prime order subgroup of
E, and s is a floor(log_2(p)+7)/8 string of bytes.  Let H be a hash
function. We let r=H(v||M) mod q  where H is taken as a little-endian
string of bytes, compute R=rG, and let c=H(M||R) mod q. Then let
s=r-ck. The signature is (R,s).

A verifier computes c=H(M||R) mod q, and verifies that sG+cA=R. This
scheme is secure in the ROM as it is yet another Schnorr signature
variation. For wide-pipe designs it's somewhat collision resistant.

Sincerely,
Watson Ladd

---

From: "Paterson, Kenny" <[email-masked]>
Date: Mon, 22 Jun 2015 09:11:56 +0000

Hi Watson,

Thanks a lot for proposing this scheme. This is the the level of detail we
were looking for at this stage, so it serves as a good example for any
other proposers.

See below for some comments on security.

>variation. For wide-pipe designs it's somewhat collision resistant.

A few of us discussed a scheme like this off-list a while back. We were
not convinced about its inherent collision resistance, and it seems you
may also be aware of the issue given your use of the word "somewhat" in
connection with wide-pipe designs.

For everyone else's benefit, here's the problem (credit due to Adam
Langley):
 
Consider an adversary who can find messages M_1, M_2 such that the partial
hashes of M_1 and M_2 under H are equal - here we are thinking of H being
the usual kind of hash function that processes its inputs in blocks, with
the intermediate hash value being fed forward to the next stage - think of
SHA-256 with its compression function. This assumption is not quite the
same as breaking collision resistance of H, but it's close enough.

Then, since inner collisions lead to full collisions, the full hashes of
M_1 || R and M_2 || R will also be equal for *any* R. But the "form" of R
is not checked during verification - the verifier can't regenerate R and
check that it's of the form rG where r = H(v || M) for the right M, for
obvious reasons. This means (informally) that "any R will do" as far as
verification is concerned.

So if the adversary obtains a valid signature (R,s) for M_1, then (R,s)
will also be a valid signature for M_2.

Hence, the proposal does seem to depend on collision resistance of H for
its security, at least for H's of the assumed form (and which I would
venture we are likely to adopt in our selected signature scheme).

[Technical note 1: this requirement on H should not be too much of a
surprise, assuming the correctness of your earlier hypothesis about the
incompatibility between supporting the IUF interface and achieving
collision resistance: your proposal could be implemented in constant space
for an IUF interface by employing two running hash computations: one for
H(v ||M), the other for H(M || R), with the latter only being finalised
once R has been computed after the finalisation of the former.

Technical note 2: Ed25519 follows Schnorr and uses H(R || A || M), putting
R first and thereby not allowing the attacker the same flexibility in
finding collisions in the above attack scenario.]

Cheers,

Kenny

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 23 Jun 2015 11:00:11 +0300

> positive. Let q be the order of the large prime subgroup of E.

Did you mean E: (-1)x^2+y^2=1+dx^2y^2? AFAIK, Usually the a twist
factor is on x, and usually the lhs terms are quadric.

Also, isn't the usual negative/positive criteria when working on
curves that are possibly of fields of size 4k+1 the LSB of the
representative? I think that might be easier to get than comparing
the coordinate with (p-1)/2.

-Ilari