HackMD
Multiset hashing based on elliptic curves
References:
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
(screenshot from SP1 V4 turbo note)
Discussion
An extension degree
- 137 bits against Gaudry attack,
- 148 bits against Joux and Vitse attack and
- 108.5 bits against Pollard's Rho attack.
This is fine for their targetted security level of 100 bits.
However arithmetic over
- 111 bits against Gaudry attack,
- 123 bits against Joux and Vitse attack and
- 93 bits against Pollard's Rho attack, which falls behind the 100 bits target.
A
- 166 bits against Gaudry attack,
- 178 bits against Joux and Vitse attack and
- 124 bits against Pollard's Rho attack.
This curve has the prime order:
Note that since the coefficient
Out-circuit the octic extension can be implemented as follows
Koala-bear case
A similar effort can be conducted with Koala-Bear prime for Linea use-case. Given
with prime order:
and
The security analysis is similar:
- 166 bits against Gaudry attack,
- 178 bits against Joux and Vitse attack 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
- prime order
The security analysis is similar:
- 137 bits against Gaudry attack,
- 148 bits against Joux and Vitse attack and
- 108.5 bits against Pollard's Rho attack.
