Ristretto255

Ristretto is a new unified point compression format for curves over large-characteristic fields, which divides the curve’s cofactor by 4 or 8 at very little cost of performance, efficiently implementing a prime-order group.

libsodium 1.0.18+ implements ristreto255: ristretto on top of the Curve25519 curve.

Compared to Curve25519 points encoded as their coordinates, ristretto makes it easier to safely implement protocols originally designed for prime-order groups.

Example

Perform a secure two-party computation of f(x) = p(x)^k. x is the input sent to the second party by the first party after blinding it using a random invertible scalar r, and k is a secret key only known by the second party. p(x) is a hash-to-group function.

  1. // -------- First party -------- Send blinded p(x)
  2. unsigned char x[crypto_core_ristretto255_HASHBYTES];
  3. randombytes_buf(x, sizeof x);
  5. // Compute px = p(x), a group element derived from x
  6. unsigned char px[crypto_core_ristretto255_BYTES];
  7. crypto_core_ristretto255_from_hash(px, x);
  9. // Compute a = p(x) * g^r
  10. unsigned char r[crypto_core_ristretto255_SCALARBYTES];
  11. unsigned char gr[crypto_core_ristretto255_BYTES];
  12. unsigned char a[crypto_core_ristretto255_BYTES];
  13. crypto_core_ristretto255_scalar_random(r);
  14. crypto_scalarmult_ristretto255_base(gr, r);
  15. crypto_core_ristretto255_add(a, px, gr);
  17. // -------- Second party -------- Send g^k and a^k
  18. unsigned char k[crypto_core_ristretto255_SCALARBYTES];
  19. randombytes_buf(k, sizeof k);
  21. // Compute v = g^k
  22. unsigned char v[crypto_core_ristretto255_BYTES];
  23. crypto_scalarmult_ristretto255_base(v, k);
  25. // Compute b = a^k
  26. unsigned char b[crypto_core_ristretto255_BYTES];
  27. if (crypto_scalarmult_ristretto255(b, k, a) != 0) {
  28.     return -1;
  29. }
  31. // -------- First party -------- Unblind f(x)
  32. // Compute vir = v^(-r)
  33. unsigned char ir[crypto_core_ristretto255_SCALARBYTES];
  34. unsigned char vir[crypto_core_ristretto255_BYTES];
  35. crypto_core_ristretto255_scalar_negate(ir, r);
  36. crypto_scalarmult_ristretto255(vir, ir, v);
  38. // Compute f(x) = b * v^(-r) = (p(x) * g^r)^k * (g^k)^(-r)
  39. //              = (p(x) * g)^k * g^(-k) = p(x)^k
  40. unsigned char fx[crypto_core_ristretto255_BYTES];
  41. crypto_core_ristretto255_add(fx, b, vir);

Encoded element validation

  1. int crypto_core_ristretto255_is_valid_point(const unsigned char *p);

The crypto_core_ristretto255_is_valid_point() function checks that p is a valid ristretto255-encoded element.

This operation only checks that p is in canonical form.

The function returns 1 on success, and 0 if the checks didn’t pass.

Random group element

  1. void crypto_core_ristretto255_random(unsigned char *p);

Fills p with the representation of a random group element.

Hash-to-group

  1. int crypto_core_ristretto255_from_hash(unsigned char *p, const unsigned char *r);

The crypto_core_ristretto255_from_hash() function maps a 64 bytes vector r (usually the output of a hash function) to a group element, and stores its representation into p.

Scalar multiplication

  1. int crypto_scalarmult_ristretto255(unsigned char *q, const unsigned char *n,
  2.                                    const unsigned char *p);

The crypto_scalarmult_ristretto255() function multiplies an element represented by p by a scalar n (in the [0..L[ range) and puts the resulting element into q.

q should not be used as a shared key prior to hashing.

The function returns 0 on success, or -1 if q is the identity element.

  1. int crypto_scalarmult_ristretto255_base(unsigned char *q, const unsigned char *n);

The crypto_scalarmult_ristretto255_base() function multiplies the generator by a scalar n ([0..L[ range) and puts the resulting element into q.

The function returns -1 if n is 0, and 0 otherwise.

Element addition/subtraction

  1. int crypto_core_ristretto255_add(unsigned char *r,
  2.                                  const unsigned char *p, const unsigned char *q);

The crypto_core_ristretto255_add() function adds the element represented by p to the element q and stores the resulting element into r.

The function returns 0 on success, or -1 if p and/or q are not valid encoded elements.

  1. int crypto_core_ristretto255_sub(unsigned char *r,
  2.                                  const unsigned char *p, const unsigned char *q);

The crypto_core_ristretto255_sub() function subtracts the element represented by p to the element q and stores the resulting element into r.

The function returns 0 on success, or -1 if p and/or q are not valid encoded elements.

Scalar arithmetic over L

The crypto_core_ristretto255_scalar_*() function set operates over scalars in the [0..L[ interval, L being the order of the ristretto255 group: (2^252 + 27742317777372353535851937790883648493).

Non-reduced inputs are expected to be within that interval.

A random scalar can be obtained using the crypto_core_ristretto255_scalar_random() function:

  1. void crypto_core_ristretto255_scalar_random(unsigned char *r);

crypto_core_ristretto255_scalar_random() fills r with a crypto_core_ristretto255_SCALARBYTES bytes representation of the scalar in the ]0..L[ interval.

A scalar in the [0..L[ interval can also be obtained by reducing a possibly larger value:

  1. void crypto_core_ristretto255_scalar_reduce(unsigned char *r, const unsigned char *s);

The crypto_core_ristretto255_scalar_reduce() function reduces s to s mod L and puts the crypto_core_ristretto255_SCALARBYTES integer into r.

Note that s is much larger than r (64 bytes vs 32 bytes). Bits of s can be left to 0, but the interval s is sampled from should be at least 317 bits to ensure almost uniformity of r over L.

  1. int crypto_core_ristretto255_scalar_invert(unsigned char *recip, const unsigned char *s);

The crypto_core_ristretto255_scalar_invert() function computes the multiplicative inverse of s over L, and puts it into recip.

  1. void crypto_core_ristretto255_scalar_negate(unsigned char *neg, const unsigned char *s);

The crypto_core_ristretto255_scalar_negate() function returns neg so that s + neg = 0 (mod L).

  1. void crypto_core_ristretto255_scalar_complement(unsigned char *comp, const unsigned char *s);

The crypto_core_ristretto255_scalar_complement() function returns comp so that s + comp = 1 (mod L).

  1. void crypto_core_ristretto255_scalar_add(unsigned char *z,
  2.                                          const unsigned char *x, const unsigned char *y);

The crypto_core_ristretto255_scalar_add() function stores x + y (mod L) into z.

  1. void crypto_core_ristretto255_scalar_sub(unsigned char *z,
  2.                                          const unsigned char *x, const unsigned char *y);

The crypto_core_ristretto255_scalar_sub() function stores x - y (mod L) into z.

  1. void crypto_core_ristretto255_scalar_mul(unsigned char *z,
  2.                                          const unsigned char *x, const unsigned char *y);

The crypto_core_ristretto255_scalar_mul() function stores x * y (mod L) into z.

Constants

  • crypto_scalarmult_ristretto255_BYTES
  • crypto_scalarmult_ristretto255_SCALARBYTES
  • crypto_core_ristretto255_BYTES
  • crypto_core_ristretto255_HASHBYTES
  • crypto_core_ristretto255_SCALARBYTES
  • crypto_core_ristretto255_NONREDUCEDSCALARBYTES

Notes

As Ristretto encodes a field element that is always smaller than 2^255, the top bit is not used.

It can be thus used by applications to encode additional data.

Forcing the top bit to zero in order to ignore it:

  1. s[31] &= 0x7f;

Rejecting a key that has the top bit set:

  1. if ((s[31] & 0x80) != 0) {
  2.     return;
  3. }

Algorithms

  • ristretto255

References