[Cryptography] Announcing the P11_260 Signature System

[Kyle Butt]

[Cross Posted to curves at moderncrypto.org]

I'd like to announce a complete signature system based off a Granger Moss
Prime:
P11_260.
The primes is 260 bits, and is equal to t^11/(t - 1) for t = 2^26 - 15.
p is congruent to 3 mod 4 for cheap square roots.

The curve is an edwards curve with d = -49142, and is the smallest such d
with cofactor 4 and twist cofactor 4.
All of the safe curves tests pass.

I currently have key generation running in 66928 cycles on haswell, and
signing of 59 bytes in 70618 cycles. Verification is 248108 cycles.
Verification could be sped up by using NAF instead of fixed sized windows.
All of those measurements were made with supercop, HT and turbo off, with
cset shield and are the median readings of 32 runs.

For both signing and generation,

The code is implemented for AVX2, as well as a reference implementation
that is slow, but provides a comparison point and is easier to follow.

The code is available here:
https://github.com/iteratee/p11_260

The signature system is similar to EdDSA, with 2 deviations:
The keys are not washed (setting the high bits), so that they form a group.
If you use signed-all-bits-set, you don't have to worry about stopping
early, because there are no zeroes.
Also, we don't clear the low bits. For signatures, this isn't necessary.

Another deviation is session key derivation. Session key derivation uses
entropy, and also hashing. This helps avoid both weak-entropy attacks and
fault attacks.

The signature equation is R = sB + h(R, compress(A), M)A.

To facilitate simpler encoding and decoding, points on the curve are
encoded not as 260-bits mod p, but as 10 26-bit coefficients mod t. This
doesn't change the space requirements, and points never leave this domain.

The code could be adapted to other Granger-Moss primes with little
difficulty. The same multiplication routine and similar reduction routines
would work up to 290 bits (t ~= 2^29).

Signing and Key Generation spend over 1/3 of their time in inversion. I
suspect that due to the unaligned loads, there are some pipeline stalls
that can't be fixed with vector register forwarding. There are still places
that I could squeeze, but I'm fairly happy with the way things are shaping
up, and thought that the work was at a point it was worth sharing.

Hopefully you find something interesting here,
Kyle.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20190618/e80872e3/attachment.html>