# Ristretto

[Ristretto](https://ristretto.group) 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.

```c
// -------- First party -------- Send blinded p(x)
unsigned char x[crypto_core_ristretto255_HASHBYTES];
randombytes_buf(x, sizeof x);

// Compute px = p(x), a group element derived from x
unsigned char px[crypto_core_ristretto255_BYTES];
crypto_core_ristretto255_from_hash(px, x);

// Compute a = p(x) * g^r
unsigned char r[crypto_core_ristretto255_SCALARBYTES];
unsigned char gr[crypto_core_ristretto255_BYTES];
unsigned char a[crypto_core_ristretto255_BYTES];
crypto_core_ristretto255_scalar_random(r);
crypto_scalarmult_ristretto255_base(gr, r);
crypto_core_ristretto255_add(a, px, gr);

// -------- Second party -------- Send g^k and a^k
unsigned char k[crypto_core_ristretto255_SCALARBYTES];
crypto_core_ristretto255_scalar_random(k);

// Compute v = g^k
unsigned char v[crypto_core_ristretto255_BYTES];
crypto_scalarmult_ristretto255_base(v, k);

// Compute b = a^k
unsigned char b[crypto_core_ristretto255_BYTES];
if (crypto_scalarmult_ristretto255(b, k, a) != 0) {
    return -1;
}

// -------- First party -------- Unblind f(x)
// Compute vir = v^(-r)
unsigned char ir[crypto_core_ristretto255_SCALARBYTES];
unsigned char vir[crypto_core_ristretto255_BYTES];
crypto_core_ristretto255_scalar_negate(ir, r);
crypto_scalarmult_ristretto255(vir, ir, v);

// Compute f(x) = b * v^(-r) = (p(x) * g^r)^k * (g^k)^(-r)
//              = (p(x) * g)^k * g^(-k) = p(x)^k
unsigned char fx[crypto_core_ristretto255_BYTES];
crypto_core_ristretto255_add(fx, b, vir);
```

## Encoded element validation

```c
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

```c
void crypto_core_ristretto255_random(unsigned char *p);
```

Fills `p` with the representation of a random group element.

## Hash-to-group

```c
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

```c
int crypto_scalarmult_ristretto255(unsigned char *q, const unsigned char *n,
                                   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.

```c
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

```c
int crypto_core_ristretto255_add(unsigned char *r,
                                 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.

```c
int crypto_core_ristretto255_sub(unsigned char *r,
                                 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:

```c
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:

```c
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`.

```c
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`.

```c
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)`.

```c
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)`.

```c
void crypto_core_ristretto255_scalar_add(unsigned char *z,
                                         const unsigned char *x, const unsigned char *y);
```

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

```c
void crypto_core_ristretto255_scalar_sub(unsigned char *z,
                                         const unsigned char *x, const unsigned char *y);
```

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

```c
void crypto_core_ristretto255_scalar_mul(unsigned char *z,
                                         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:

```c
s[31] &= 0x7f;
```

Rejecting a key that has the top bit set:

```c
if ((s[31] & 0x80) != 0) {
    return;
}
```

## Algorithms

* `ristretto255`

## References

* [Ristretto](https://ristretto.group)
* [Decaf: Eliminating cofactors through point compression](https://eprint.iacr.org/2015/673.pdf)