r255b3: schnorr signatures using ristretto255 and blake3.

This crate provides short Schnorr signatures based on Ristretto255 and Blake3.

Note: This is not Ed25519, if you want Ed25519, please use the excellent ed25519-dalek crate.

Warning! This is a slightly novel cryptographic primitive. It has not been audited! Use at your own (not others') risk!

The API and cryptographic construction may change in response to an audit, but may be considered relatively stable starting with version 0.3.0.

Why?

The initial motivation was to provide a minimal footprint for embedded versions of converge. It already used the Blake3 hash function extensively, and that wasn't going to change to SHA512 just for Ed25519 signatures.

That said, there are other benefits over Ed25519:

• smaller keys using the Schnorr signature formulation.
• proper (and enforced) support for domain separation.
• well specified secret keys, and no malleability in the public keys, or signatures.
• the default mode supports streaming, and signing data with a single pass.
• uses the much faster hash function, much faster for large inputs.

How?

The Schnorr signature scheme has accumulated many variations, this one:

• provides built-in domain separation
• uses a scalar as the secret key and the group generator times that scalar as the public key
• uses a small scalar, large scalar tuple as the signature
• derives a deterministic random nonce from the domain, message, secret key, and public key
• mixes the public key into the message hash

Key Generation

r255b3 uses Ristretto255 scalars as secret keys. These are generated by sampling 256 bits of secure randomness then reducing by the group order. This group order is relatively slightly more than 2²⁵², which limits the total deviation from a uniform distribution to roughly 2⁻¹²⁶.

sk ←ᴿ Scalars
pk := sk*B

Message Hash Preparation

We first derive a keyed hash from the domain, using Blake3's context hashing:

hk := Blake3Ctx("Schnorr-Ristretto255-Blake3", domain)

Signing

Next we generate a scalar nonce, k, either by sampling a random value or deterministically:

k := Blake3Keyed(hk, message || "Secret Nonce for Schnorr-Ristretto255-Blake3" || sk || pk)

Now k scales the generator to get the Ristretto255 point r. r is compressed, concatenated with the message and public key, and fed to Blake3 to used to derive the short scalar e.

r = k*B
e = Blake3(hk, message || "Message Hash for Schnorr-Ristretto255-Blake3" || pk || r)

e here is the first 128 bits of the hash, the second 128 bits are discarded.

Note that the hashes for k and e share a common prefix, this enables us to duplicate the hash state before feeding the context strings, keys, and points used once into the hash.

Finally, we multiply e by the secret key, and subtract their product from k, yielding the (full size) scalar s. This produces our signature, which is the tuple of e and s.

s = k - sk * e
sig = (e, s)

e is 16 bytes, and s is 32 bytes, resulting in a 48 byte signature.

Verifying

Verification proceeds by reconstructing r.

rᵥ = s*B + e*pk = (k - sk*e)*B + (e*sk*B) = k*B - sk*e*B + e*sk*B = k*B

Now that we have rᵥ, we hash the message with our keyed Blake3 exactly as was done during signing. This yields another copy of e, which we call eᵥ.

eᵥ = Blake3(hk, message || "Message Hash for Schnorr-Ristretto255-Blake3" || pk || r)

Finally, we can compare eᵥ with the e from the signature, and if they match we have a valid signature.

Test Vectors

Secret Key: "Did gyre and gimble in the wabe\n" Public Key: 161bf5685cfbb674ad88dbbb266e15ec5aa93406135ec471704acb79cd246564 On Domain: "All mimsy were the borogroves," On Message: "And the mome raths outgrabe" Signature: 9028a67bf5ca00771b15ab30535bba69d4991415d864503cd87e589712d0e0186d4c03629416d51e639817ba9009520c

License

This project is dedicated to the public domain, see the UNLICENSE for details.