p3_poseidon2/
round_numbers.rs

1//! As the security analysis of Poseidon2 is identical to that of Poseidon,
2//! the relevant constraints regarding the number of full/partial rounds required can be found in
3//! the original paper: `<https://eprint.iacr.org/2019/458.pdf>` and the associated codebase:
4//! `<https://extgit.iaik.tugraz.at/krypto/hadeshash>` (See generate_params_poseidon.sage)
5//!
6//! These constraints are broken down into 6 equations:
7//! statistical, interpolation, Gröbner 1, 2, 3 and
8//! an extra constraint coming from the paper `<https://eprint.iacr.org/2023/537.pdf>`.
9//!
10//! For our parameters (M = 128, p > 2^30, WIDTH = t >= 8, D = alpha < 12),
11//! the statistical constraint always simplifies to requiring RF >= 6.
12//! Additionally p does not appear in Gröbner 3 or the constraint coming from `<https://eprint.iacr.org/2023/537.pdf>`.
13//! The remaining 3 constraints all can be rearranged into the form:
14//! F(RF, RP) >= G(p) where G is a function which is non-decreasing with respect to p.
15//!
16//! Thus, if some tuple (M, p, WIDTH, D, RF, RP) satisfies all constraints, then so will
17//! the tuple (M, q, WIDTH, D, RF, RP) for any 2^30 < q < p.
18//! Moreover if RF, RP are the "optimal" round numbers (Optimal meaning minimising the number of S-box operations we need to perform)
19//! for two tuples (M, p, WIDTH, D) and (M, q, WIDTH, D), then
20//! they will also be optimal for (M, r, WIDTH, D) for any q < r < p.
21//!
22//! We compute the optimal required number of external (full) and internal (partial) rounds using:
23//! `<https://github.com/0xPolygonZero/hash-constants/blob/master/calc_round_numbers.py>`
24//! Using the above analysis we can conclude that the round numbers are equal
25//! for all 31 bit primes and 64 bit primes respectively.
26
27use p3_field::PrimeField64;
28use p3_util::relatively_prime_u64;
29
30/// Given a field, a width and an D return the number of full and partial rounds needed to achieve 128 bit security.
31///
32/// If d is not a valid permutation of the given field or the optimal parameters for that size of prime
33/// have not been computed, an error is returned.
34pub const fn poseidon2_round_numbers_128<F: PrimeField64>(
35    width: usize,
36    d: u64,
37) -> Result<(usize, usize), &'static str> {
38    // Start by checking that d is a valid permutation.
39    if !relatively_prime_u64(d, F::ORDER_U64 - 1) {
40        return Err("Invalid permutation: gcd(d, F::ORDER_U64 - 1) must be 1");
41    }
42
43    // Next compute the number of bits in p.
44    let prime_bit_number = F::ORDER_U64.ilog2() + 1;
45
46    match prime_bit_number {
47        31 => match (width, d) {
48            (16, 3) => Ok((8, 20)),
49            (16, 5) => Ok((8, 14)),
50            (16, 7) => Ok((8, 13)),
51            (16, 9) => Ok((8, 13)),
52            (16, 11) => Ok((8, 13)),
53            (24, 3) => Ok((8, 23)),
54            (24, 5) => Ok((8, 22)),
55            (24, 7) => Ok((8, 21)),
56            (24, 9) => Ok((8, 21)),
57            (24, 11) => Ok((8, 21)),
58            _ => Err("The given pair of width and D has not been checked for these fields"),
59        },
60        64 => match (width, d) {
61            (8, 3) => Ok((8, 41)),
62            (8, 5) => Ok((8, 27)),
63            (8, 7) => Ok((8, 22)),
64            (8, 9) => Ok((8, 19)),
65            (8, 11) => Ok((8, 17)),
66            (12, 3) => Ok((8, 42)),
67            (12, 5) => Ok((8, 27)),
68            (12, 7) => Ok((8, 22)),
69            (12, 9) => Ok((8, 20)),
70            (12, 11) => Ok((8, 18)),
71            (16, 3) => Ok((8, 42)),
72            (16, 5) => Ok((8, 27)),
73            (16, 7) => Ok((8, 22)),
74            (16, 9) => Ok((8, 20)),
75            (16, 11) => Ok((8, 18)),
76            _ => Err("The given pair of width and D has not been checked for these fields"),
77        },
78        _ => Err("The optimal parameters for that size of prime have not been computed."),
79    }
80}
p3_poseidon2/round_numbers.rs

p3_poseidon2/
round_numbers.rs
