Create an EdDSA scheme using Ristretto and Blake3 about o1c HOT 6 CLOSED

After experimenting a bit and reading more about EdDSA and Blake3, it seems like the adjustments to Ed25519 can be the following:

• Replace SHA-2 hashes with keyed Blake3 hashes. Instead of hashing the key first in each of the hash steps, these can put the first 32 bytes in the key. Specifically, this changes the following places:
  • Use the private key (seed) as the key to a Blake3 keyed hash. Finalize this output to 64 bytes with the first 32 bytes being clamped and parsed as the secret scalar and the second 32 bytes being used to initialize another keyed Blake3 hash which will be later used as the "challenge" hash for generating the R-half of signatures and is known as the "prefix" part of the expanded key.
  • When signing a message, instead of hashing the prefix, we start with this challenge hash, update with the message to be signed, then finalize the output to 64 bytes. Those bytes are reduced to a scalar r the same way as in Ed25519. Using this reduction step simplifies implementations modifying an existing Ed25519 library similar to other things Ristretto255 optimizes for.
  • This scalar is multiplied by the Ristretto base point which is the same as the Ed25519 base point, but its compressed output (used for the R-half of the signature) uses the Ristretto point compression encoding rather than the usual compressed Edwards coordinates.
  • The compressed point R is then used as the key for another Blake3 hash. This is then updated with the Ristretto encoding of the public key (earlier secret scalar multiplied by Ristretto base point) followed by the message contents. This is similar to the Ed25519 step but with R used as the hash key rather than as part of the initial hash followed by the public key and message as usual. This hash is finalized to 64 bytes and reduced to a scalar k using the same scalar reduction as before.
  • This scalar k is multiplied by the secret scalar, then their product is added to the scalar r. This resulting scalar s is serialized as the S-half of the signature.
  • Verification works as the inverse which uses the R-half of the signature to initialize a Blake3 hash, updates with the public key and message, then finalizes 64 bytes and reduces them to calculate k.
  • The verification equation can be validated by multiplying the negated public key by k and adding that to the product of s and the Ristretto base point, then checking if that resulting Ristretto element is equivalent to the point encoded in R.

There is one outstanding design choice to make here that might make things less "neat" but more correct: the value of R may be attacker-controlled during verification, but it has to satisfy the algebra and the hash output, so it might or might not benefit from using a plain Blake3 hash rather than a keyed hash for this step.

The nice thing about this algorithm is that it meshes better with the Ristretto signcryption scheme and Ristretto key exchange scheme rather than requiring special-purpose algorithms for different concerns (a common point of confusion by developers; see for example misuse of RSA when exposed improperly).

from o1c.

Switching the R value to initialize as hash input makes sense. After getting a proof of concept version working in both Java and C, there are a couple open issues:

• Hash-to-scalar: can we just use the default 256-bit Blake3 output and reduce from there, or do we finalize a 512-bit Blake3 output and reduce that value to a scalar the same way Ed25519 does to the SHA-512 output? Another algorithm may need to be added to the C code to support the small reduction without the added overhead of a full 512-bit reduction.
• Re-using the double-scalar-vartime algorithm from this paper which is already used in the Ed25519 code. The current version results in projective coordinates which will need to be math-checked to see how it can adapt to the ristretto equality check (might be a drop-in since projective and extended coordinates have a bit of overlap).

from o1c.

Possible red herring, but CFRG is looking at KangarooTwelve as a keyed XOF which, like Blake3, reduces the rounds of a more conservative design (in this case SHAKE from SHA-3) to something still provably secure.

from o1c.

For hash-to-scalar, I think this should use the 512-bit variant as there's a defined algorithm for mapping a uniform 64-byte string to a scalar, but for a 32-byte string, this only mentions that it should be validated to be within the proper scalar field range and rejected otherwise (in the case of uniform strings; serialization of scalars needs to reduce to within the range first). I believe that trying to reduce from a 32-byte uniform string will introduce some bias that would break security assumptions somewhere. :)

from o1c.

Just curious if you were able to get ed25519 to use BLAKE3...

from o1c.

Yeah, though there are options on how to implement it. The simplest approach is to take the RFC and swap SHA-2 with Blake3 in hash mode. Another alternative I considered was to use it in keyed hash mode using the private key seed as the key there and its hash output as basis for the private key and signing half (I forget the exact details; it's been a few months).

from o1c.