# Multiset hashing based on elliptic curves

References:
- [SP1 V4 turbo note](https://github.com/succinctlabs/sp1/blob/dev/book/static/SP1_Turbo_Memory_Argument.pdf)
- [SP1 github code](https://github.com/succinctlabs/sp1/blob/c3dc4d89de4100ada22c2a4a2545bc7ffbad4b93/crates/stark/src/septic_curve.rs#L108)
- [ZK12: Memory checking in IVC-based zkVMs - Jens Groth](https://www.youtube.com/watch?v=kzSYNFh4uQ0)

> (screenshot from SP1 V4 turbo note)

## Discussion
An extension degree $k=7$ gets a security level of:
- 137 bits against [Gaudry attack](https://eprint.iacr.org/2004/073),
- 148 bits against [Joux and Vitse attack](https://eprint.iacr.org/2010/157) and
- 108.5 bits against Pollard's Rho attack.

This is fine for their targetted security level of 100 bits.

However arithmetic over $\mathbb{F}_{p^7}$ is cumbersome to implement out-circuit. So choosing $k=6$ or $8$ is preferable to use Karatsuba and Toom-Cook routines. A $k=6$ extension gets:
- 111 bits against [Gaudry attack](https://eprint.iacr.org/2004/073),
- 123 bits against [Joux and Vitse attack](https://eprint.iacr.org/2010/157) and
- **93 bits against Pollard's Rho attack, which falls behind the 100 bits target**.

A $k=8$ extension gets:
- 166 bits against [Gaudry attack](https://eprint.iacr.org/2004/073),
- 178 bits against [Joux and Vitse attack](https://eprint.iacr.org/2010/157) and
- 124 bits against Pollard's Rho attack.

$\mathbb{F}_{p^8}$ can be simply represented as $\mathbb{F}_{p}[z]/z^8-11$ and the prime-order following curve can be instantiated:
$$(E/\mathbb{F}_{p^8}): Y^2 = X^3 - 3X + 32z^5$$
This curve has the prime order:
$$r = \mathtt{0x98c29b8b2f1b6f4c0a66714470a403628e1deb2a36f88d57337f85c4e42c99}.$$

Note that since the coefficient $A$ cannot be $0$, we choose $A=-3$ to benefit from an optimization when using Jacobian coordinates [EFD](https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html).
Out-circuit the octic extension can be implemented as follows $\mathbb{F}_{p^2}=\mathbb{F}_p[x]/x^2-11$, $\mathbb{F}_{p^4}=\mathbb{F}_{p^2}[y]/y^2-x$ and $\mathbb{F}_{p^8}=\mathbb{F}_{p^4}[z]/z^2-y$ using Karatsuba-over-Karatsuba-over-Karatsuba for the arithmetic.

## Koala-bear case
A similar effort can be conducted with Koala-Bear prime for Linea use-case. Given $p=2^{31} - 2^{24} + 1$ of 31 bits, we find the elliptic curve:

$$(E/\mathbb{F}_{p^8}): Y^2 = X^3 - 3X + 17z^5$$
with prime order:
$$r = \mathtt{0xf06e44682c2aa440f5f26a5ae1748fec171df66abbdb81ad07f36ed81b9049}$$

and $\mathbb{F}_{p}[z]/z^8-3$, or equivalently $\mathbb{F}_{p^2}=\mathbb{F}_{p}[x]/x^2-3$, $\mathbb{F}_{p^4}=\mathbb{F}_{p^2}[y]/y^2-x$ and $\mathbb{F}_{p^8}=\mathbb{F}_{p^4}[z]/z^2-y$.

The security analysis is similar:
- 166 bits against [Gaudry attack](https://eprint.iacr.org/2004/073),
- 178 bits against [Joux and Vitse attack](https://eprint.iacr.org/2010/157) and
- 124 bits against Pollard's Rho attack.

If we end up not caring about the performance out-circuit and we only focus on the in-circuit cost, we can choose a $7$-th extension and implement the arithmetic in circuit over $\mathbb{F}_{p^7}$ using the randomized Schwartz-Zippel trick ([Feltroid post](https://hackmd.io/@feltroidprime/B1eyHHXNT)). We find the following parameters:
- $\mathbb{F}_{p^7} = \mathbb{F}_{p}[z]/z^7+z+4$,
- $(E/\mathbb{F}_{p^7}): Y^2 = X^3 + 9X + 15z^5$ and
- prime order $r=\mathtt{0x1e4a5d47579fd9acc910bb689b459f0a9ba4adbefb76f53ab9c25b3}.$

The security analysis is similar:
- 137 bits against [Gaudry attack](https://eprint.iacr.org/2004/073),
- 148 bits against [Joux and Vitse attack](https://eprint.iacr.org/2010/157) and
- 108.5 bits against Pollard's Rho attack.