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/// Total number of full rounds for 128-bit security.
31///
32/// The Poseidon paper's statistical attack analysis (Section 5.4) requires `RF ≥ 6`.
33/// Adding the standard +2 security margin gives `RF = 8`.
34/// This value is the same for all field sizes and widths at the 128-bit security level.
35const FULL_ROUNDS_128: usize = 8;
36
37/// Given a field, a width and an D return the number of full and partial rounds needed to achieve 128 bit security.
38///
39/// If d is not a valid permutation of the given field or the optimal parameters for that size of prime
40/// have not been computed, an error is returned.
41pub const fn poseidon2_round_numbers_128<F: PrimeField64>(
42    width: usize,
43    d: u64,
44) -> Result<(usize, usize), &'static str> {
45    // Start by checking that d is a valid permutation.
46    if !relatively_prime_u64(d, F::ORDER_U64 - 1) {
47        return Err("Invalid permutation: gcd(d, F::ORDER_U64 - 1) must be 1");
48    }
49
50    // Next compute the number of bits in p.
51    let prime_bit_number = F::ORDER_U64.ilog2() + 1;
52
53    match prime_bit_number {
54        31 => match (width, d) {
55            (16, 3) => Ok((FULL_ROUNDS_128, 20)),
56            (16, 5) => Ok((FULL_ROUNDS_128, 14)),
57            (16, 7) => Ok((FULL_ROUNDS_128, 13)),
58            (16, 9) => Ok((FULL_ROUNDS_128, 13)),
59            (16, 11) => Ok((FULL_ROUNDS_128, 13)),
60            (24, 3) => Ok((FULL_ROUNDS_128, 23)),
61            (24, 5) => Ok((FULL_ROUNDS_128, 22)),
62            (24, 7) => Ok((FULL_ROUNDS_128, 21)),
63            (24, 9) => Ok((FULL_ROUNDS_128, 21)),
64            (24, 11) => Ok((FULL_ROUNDS_128, 21)),
65            (32, 3) => Ok((FULL_ROUNDS_128, 31)),
66            (32, 5) => Ok((FULL_ROUNDS_128, 30)),
67            (32, 7) => Ok((FULL_ROUNDS_128, 30)),
68            (32, 9) => Ok((FULL_ROUNDS_128, 30)),
69            (32, 11) => Ok((FULL_ROUNDS_128, 30)),
70            _ => Err("The given pair of width and D has not been checked for these fields"),
71        },
72        64 => match (width, d) {
73            (8, 3) => Ok((FULL_ROUNDS_128, 41)),
74            (8, 5) => Ok((FULL_ROUNDS_128, 27)),
75            (8, 7) => Ok((FULL_ROUNDS_128, 22)),
76            (8, 9) => Ok((FULL_ROUNDS_128, 19)),
77            (8, 11) => Ok((FULL_ROUNDS_128, 17)),
78            (12, 3) => Ok((FULL_ROUNDS_128, 42)),
79            (12, 5) => Ok((FULL_ROUNDS_128, 27)),
80            (12, 7) => Ok((FULL_ROUNDS_128, 22)),
81            (12, 9) => Ok((FULL_ROUNDS_128, 20)),
82            (12, 11) => Ok((FULL_ROUNDS_128, 18)),
83            (16, 3) => Ok((FULL_ROUNDS_128, 42)),
84            (16, 5) => Ok((FULL_ROUNDS_128, 27)),
85            (16, 7) => Ok((FULL_ROUNDS_128, 22)),
86            (16, 9) => Ok((FULL_ROUNDS_128, 20)),
87            (16, 11) => Ok((FULL_ROUNDS_128, 18)),
88            _ => Err("The given pair of width and D has not been checked for these fields"),
89        },
90        _ => Err("The optimal parameters for that size of prime have not been computed."),
91    }
92}
p3_poseidon2/round_numbers.rs

p3_poseidon2/
round_numbers.rs
