Discussion:
qDSA signatures
(too old to reply)
Joost Renes
2017-06-06 15:46:36 UTC
Permalink
Hi all,

Yesterday Ben Smith and I have published a draft of our recent research
on an x-only signature scheme, which we named qDSA (short for quotient
Digital Signature Algorithm). It can be found here:

http://eprint.iacr.org/2017/518.pdf,

with accompanying code at http://www.cs.ru.nl/~jrenes/.

One of the main benefits is that it removes the need to switch between
DH keys (eg. Curve25519 keys) and EdDSA keys (eg. Ed25519 keys). This
can be done by only minor modifications to the EdDSA scheme, essentially
by doing verification "up to sign". We provide a relatively standard
proof of security to gain confidence in its security.

Initially, this was motivated by the goal of reducing stack usage in the
genus 2 signature scheme by CCS [A], which we implemented on
microcontrollers [B]. In this case, converting between the Kummer
surface and the Jacobian is particularly expensive, so we want to avoid
this. We define qDSA by altering EdDSA in such a way that such
conversions are completely unnecessary, and dedicate much of the paper
to showing how one could implement this efficiently. The main
complication to overcome is signature verification, where seemingly a
group operation would be necessary.

Perhaps more interestingly, qDSA can also be instantiated with
Curve25519 (\S3 of the paper). The result is a signature scheme for
which key pairs are equal to X25519 key pairs, and where any conversion
to the (twisted) Edwards form is obsolete. Unsurprisingly, it ends up
being quite close to Mike Hamburg's Strobe [C] implementation, but with
the added benefit of having a proof of security.

Since almost all arithmetic needed in qDSA is identical to that used in
X25519, this allows for especially compact and memory-friendly
implementations. On the other hand, a small loss of efficiency in
verification is expected. Its main use would be for memory-constraint
environments, but it may extend beyond that.

We would be very interested and happy to hear any comments, feedback, or
questions that you might have.

Kind regards,
Joost

[A] Chung et al., http://eprint.iacr.org/2016/777.pdf

[B] R. et al., http://eprint.iacr.org/2016/366.pdf

[C] Hamburg, http://eprint.iacr.org/2017/003.pdf
Mike Hamburg
2017-06-06 18:43:57 UTC
Permalink
Hello Joost and Ben,

This is cool work! I like that you did hyperelliptic Kummer surfaces too.
I have a few questions about it.

Do you run into any problems where x:z = 0:0 in any of the formulas? That
would make Check always return true, but maybe it can’t happen?

Likewise, do you run into any problems if one of the points is on the twist?
It might be that eg Q is on the twist but [c]Q = small torsion point is on both the
curve and the twist, and so the verification goes through. But maybe it’s hard
to cause this so the proof works anyway.

Do you know a good way to make the signature nonmalleable? I settled for
malleable ones in STROBE, but it would be neat if there were a way to make
it nonmalleable.

Finally, are you sure that your trick of setting c <- Z_N+ is necessary? It
seems to me that the probability that c1 = -c2 is negligible anyway, so the
proof would work just as well without this modification. In that case, your
proof would probably cover STROBE’s implementation as well, except
that STROBE depends on the hash’s collision resistance.

Cheers,
— Mike
Post by Joost Renes
Hi all,
Yesterday Ben Smith and I have published a draft of our recent research
on an x-only signature scheme, which we named qDSA (short for quotient
http://eprint.iacr.org/2017/518.pdf,
with accompanying code at http://www.cs.ru.nl/~jrenes/.
One of the main benefits is that it removes the need to switch between
DH keys (eg. Curve25519 keys) and EdDSA keys (eg. Ed25519 keys). This
can be done by only minor modifications to the EdDSA scheme, essentially
by doing verification "up to sign". We provide a relatively standard
proof of security to gain confidence in its security.
Initially, this was motivated by the goal of reducing stack usage in the
genus 2 signature scheme by CCS [A], which we implemented on
microcontrollers [B]. In this case, converting between the Kummer
surface and the Jacobian is particularly expensive, so we want to avoid
this. We define qDSA by altering EdDSA in such a way that such
conversions are completely unnecessary, and dedicate much of the paper
to showing how one could implement this efficiently. The main
complication to overcome is signature verification, where seemingly a
group operation would be necessary.
Perhaps more interestingly, qDSA can also be instantiated with
Curve25519 (\S3 of the paper). The result is a signature scheme for
which key pairs are equal to X25519 key pairs, and where any conversion
to the (twisted) Edwards form is obsolete. Unsurprisingly, it ends up
being quite close to Mike Hamburg's Strobe [C] implementation, but with
the added benefit of having a proof of security.
Since almost all arithmetic needed in qDSA is identical to that used in
X25519, this allows for especially compact and memory-friendly
implementations. On the other hand, a small loss of efficiency in
verification is expected. Its main use would be for memory-constraint
environments, but it may extend beyond that.
We would be very interested and happy to hear any comments, feedback, or
questions that you might have.
Kind regards,
Joost
[A] Chung et al., http://eprint.iacr.org/2016/777.pdf
[B] R. et al., http://eprint.iacr.org/2016/366.pdf
[C] Hamburg, http://eprint.iacr.org/2017/003.pdf
_______________________________________________
Curves mailing list
https://moderncrypto.org/mailman/listinfo/curves
Joost Renes
2017-06-08 10:31:52 UTC
Permalink
Hi Mike,

Thanks for having a look, and for your questions.
Post by Mike Hamburg
This is cool work! I like that you did hyperelliptic Kummer surfaces too.
Thanks!
Post by Mike Hamburg
Do you run into any problems where x:z = 0:0 in any of the formulas? That
would make Check always return true, but maybe it can’t happen?
Indeed, if you were to end up with the point (0 : 0) in verification,
everything will vanish and Check returns true. Assuming honest
execution, this never happens. The xDBLADD function computes the correct
result if the difference is not in the 2-torsion, and in all of our
calls we have as a difference a point of large prime order. Note that
even if the scalar is a (multiple of) the group order, the ladder
returns the point at infinity, which is (1 : 0).

You could potentially run into trouble if P (public generator) or Q
(public key) are in the 2-torsion. In the first case your system
parameters are simply not defined well, in which case you lose security
(of course). In the second someone provides you with an invalidly
generated public key, which you may want to check for. But this should
not be any different than scenario's in other Schnorr/EdDSA protocols
where public keys are invalid, and the same countermeasures should apply.
Post by Mike Hamburg
Likewise, do you run into any problems if one of the points is on the twist?
It might be that eg Q is on the twist but [c]Q = small torsion point is on both the
curve and the twist, and so the verification goes through. But maybe it’s hard
to cause this so the proof works anyway.
There are no problems here. We make a remark about this at the end of
section 2.1, but let me elaborate.

The crucial idea is that verification does not assume rationality. If a
Kummer point does not lift to J(F_p), it will indeed lift to J'(F_p).
But, actually, it also lifts to J(F_p^2). That is, the Kummer point will
always lift to J, but it may or may not be F_p-rational. The
verification algorithm assumes the Kummer points to be images of points
of J, but does not care whether those points on J were F_p-rational or not.
Post by Mike Hamburg
Do you know a good way to make the signature nonmalleable? I settled for
malleable ones in STROBE, but it would be neat if there were a way to make
it nonmalleable.
We are not sure what you mean exactly. There is a trivial malleability,
as both (R,s) and (R,-s) will be valid signatures. You could get rid of
this by only accepting signatures where s is positive, for example. You
may have to slightly adapt the proof to deal with this. In any case,
this only allows you to get a valid signature on a message and public
key for which you already have a valid signature, so the usefulness will
be limited. As remarked in the original EdDSA paper, this is not all
that significant for signature security.
Post by Mike Hamburg
Finally, are you sure that your trick of setting c <- Z_N+ is necessary? It
seems to me that the probability that c1 = -c2 is negligible anyway, so the
proof would work just as well without this modification. In that case, your
proof would probably cover STROBE’s implementation as well, except
that STROBE depends on the hash’s collision resistance.
We chose to do this because, arguably, it seems quite natural. It allows
for a nice proof, cf. the original Schnorr signatures, without any error
probabilities. As you say, allowing c to be in Z_N shouldn't be a
problem. The soundness will only be true up to some error factor where
c1 = -c2. Assuming that the probability of this happening is negligible,
everything should work.

Joost
Mike Hamburg
2017-06-08 16:35:34 UTC
Permalink
Thanks for your answers, Joost!

Sent from my phone. Please excuse brevity and typos.
Post by Joost Renes
Hi Mike,
Thanks for having a look, and for your questions.
Post by Mike Hamburg
This is cool work! I like that you did hyperelliptic Kummer surfaces too.
Thanks!
Post by Mike Hamburg
Do you run into any problems where x:z = 0:0 in any of the formulas? That
would make Check always return true, but maybe it can’t happen?
Indeed, if you were to end up with the point (0 : 0) in verification,
everything will vanish and Check returns true. Assuming honest
execution, this never happens. The xDBLADD function computes the correct
result if the difference is not in the 2-torsion, and in all of our
calls we have as a difference a point of large prime order. Note that
even if the scalar is a (multiple of) the group order, the ladder
returns the point at infinity, which is (1 : 0).
You could potentially run into trouble if P (public generator) or Q
(public key) are in the 2-torsion. In the first case your system
parameters are simply not defined well, in which case you lose security
(of course). In the second someone provides you with an invalidly
generated public key, which you may want to check for. But this should
not be any different than scenario's in other Schnorr/EdDSA protocols
where public keys are invalid, and the same countermeasures should apply.
I see. So you might want to prevent someone from setting PK=2tor so that all signatures are valid, but otherwise you don't need to check.
Post by Joost Renes
Post by Mike Hamburg
Likewise, do you run into any problems if one of the points is on the twist?
It might be that eg Q is on the twist but [c]Q = small torsion point is on both the
curve and the twist, and so the verification goes through. But maybe it’s hard
to cause this so the proof works anyway.
There are no problems here. We make a remark about this at the end of
section 2.1, but let me elaborate.
The crucial idea is that verification does not assume rationality. If a
Kummer point does not lift to J(F_p), it will indeed lift to J'(F_p).
But, actually, it also lifts to J(F_p^2). That is, the Kummer point will
always lift to J, but it may or may not be F_p-rational. The
verification algorithm assumes the Kummer points to be images of points
of J, but does not care whether those points on J were F_p-rational or not.
Makes sense.
Post by Joost Renes
Post by Mike Hamburg
Do you know a good way to make the signature nonmalleable? I settled for
malleable ones in STROBE, but it would be neat if there were a way to make
it nonmalleable.
We are not sure what you mean exactly. There is a trivial malleability,
as both (R,s) and (R,-s) will be valid signatures. You could get rid of
this by only accepting signatures where s is positive, for example. You
may have to slightly adapt the proof to deal with this. In any case,
this only allows you to get a valid signature on a message and public
key for which you already have a valid signature, so the usefulness will
be limited. As remarked in the original EdDSA paper, this is not all
that significant for signature security.
Oh right, this is only tricky to do if you want both the standard verify algorithm and the x-only one to work.
Post by Joost Renes
Post by Mike Hamburg
Finally, are you sure that your trick of setting c <- Z_N+ is necessary? It
seems to me that the probability that c1 = -c2 is negligible anyway, so the
proof would work just as well without this modification. In that case, your
proof would probably cover STROBE’s implementation as well, except
that STROBE depends on the hash’s collision resistance.
We chose to do this because, arguably, it seems quite natural. It allows
for a nice proof, cf. the original Schnorr signatures, without any error
probabilities. As you say, allowing c to be in Z_N shouldn't be a
problem. The soundness will only be true up to some error factor where
c1 = -c2. Assuming that the probability of this happening is negligible,
everything should work.
Joost
Thanks!
-- Mike

Loading...