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;
29use thiserror::Error;
30
31/// Reasons the precomputed 128-bit Poseidon2 round table cannot serve a parameter set.
32#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
33pub enum Poseidon2RoundNumbersError {
34    /// The S-box exponent does not define a permutation of the field.
35    #[error(
36        "Poseidon2 S-box exponent {exponent} is not coprime to the field order minus one ({field_order_minus_one})"
37    )]
38    InvalidSboxExponent {
39        /// Requested S-box exponent.
40        exponent: u64,
41        /// Multiplicative-group order the exponent must be coprime to.
42        field_order_minus_one: u64,
43    },
44    /// No precomputed round count exists for this width and exponent.
45    #[error(
46        "no precomputed Poseidon2 round count for a {field_bits}-bit field with width {width} and S-box exponent {exponent}"
47    )]
48    UnsupportedWidthAndExponent {
49        /// Bit length of the field order.
50        field_bits: u32,
51        /// Requested permutation width.
52        width: usize,
53        /// Requested S-box exponent.
54        exponent: u64,
55    },
56    /// The table has not been computed for this field size.
57    #[error("no precomputed Poseidon2 round counts for a {field_bits}-bit field")]
58    UnsupportedFieldSize {
59        /// Bit length of the field order.
60        field_bits: u32,
61    },
62}
63
64/// Total number of full rounds for 128-bit security.
65///
66/// The Poseidon paper's statistical attack analysis (Section 5.4) requires `RF ≥ 6`.
67/// Adding the standard +2 security margin gives `RF = 8`.
68/// This value is the same for all field sizes and widths at the 128-bit security level.
69const FULL_ROUNDS_128: usize = 8;
70
71/// Return the full and partial round counts needed for 128-bit security.
72///
73/// # Errors
74///
75/// Returns an error when `d` does not define a permutation over `F`.
76///
77/// Returns an error when the precomputed table has no matching parameter set.
78pub const fn poseidon2_round_numbers_128<F: PrimeField64>(
79    width: usize,
80    d: u64,
81) -> Result<(usize, usize), Poseidon2RoundNumbersError> {
82    // Start by checking that d is a valid permutation.
83    let field_order_minus_one = F::ORDER_U64 - 1;
84    if !relatively_prime_u64(d, field_order_minus_one) {
85        return Err(Poseidon2RoundNumbersError::InvalidSboxExponent {
86            exponent: d,
87            field_order_minus_one,
88        });
89    }
90
91    // Next compute the number of bits in p.
92    let prime_bit_number = F::ORDER_U64.ilog2() + 1;
93
94    match prime_bit_number {
95        31 => match (width, d) {
96            (16, 3) => Ok((FULL_ROUNDS_128, 20)),
97            (16, 5) => Ok((FULL_ROUNDS_128, 14)),
98            (16, 7) => Ok((FULL_ROUNDS_128, 13)),
99            (16, 9) => Ok((FULL_ROUNDS_128, 13)),
100            (16, 11) => Ok((FULL_ROUNDS_128, 13)),
101            (24, 3) => Ok((FULL_ROUNDS_128, 23)),
102            (24, 5) => Ok((FULL_ROUNDS_128, 22)),
103            (24, 7) => Ok((FULL_ROUNDS_128, 21)),
104            (24, 9) => Ok((FULL_ROUNDS_128, 21)),
105            (24, 11) => Ok((FULL_ROUNDS_128, 21)),
106            (32, 3) => Ok((FULL_ROUNDS_128, 31)),
107            (32, 5) => Ok((FULL_ROUNDS_128, 30)),
108            (32, 7) => Ok((FULL_ROUNDS_128, 30)),
109            (32, 9) => Ok((FULL_ROUNDS_128, 30)),
110            (32, 11) => Ok((FULL_ROUNDS_128, 30)),
111            _ => Err(Poseidon2RoundNumbersError::UnsupportedWidthAndExponent {
112                field_bits: prime_bit_number,
113                width,
114                exponent: d,
115            }),
116        },
117        64 => match (width, d) {
118            (8, 3) => Ok((FULL_ROUNDS_128, 41)),
119            (8, 5) => Ok((FULL_ROUNDS_128, 27)),
120            (8, 7) => Ok((FULL_ROUNDS_128, 22)),
121            (8, 9) => Ok((FULL_ROUNDS_128, 19)),
122            (8, 11) => Ok((FULL_ROUNDS_128, 17)),
123            (12, 3) => Ok((FULL_ROUNDS_128, 42)),
124            (12, 5) => Ok((FULL_ROUNDS_128, 27)),
125            (12, 7) => Ok((FULL_ROUNDS_128, 22)),
126            (12, 9) => Ok((FULL_ROUNDS_128, 20)),
127            (12, 11) => Ok((FULL_ROUNDS_128, 18)),
128            (16, 3) => Ok((FULL_ROUNDS_128, 42)),
129            (16, 5) => Ok((FULL_ROUNDS_128, 27)),
130            (16, 7) => Ok((FULL_ROUNDS_128, 22)),
131            (16, 9) => Ok((FULL_ROUNDS_128, 20)),
132            (16, 11) => Ok((FULL_ROUNDS_128, 18)),
133            _ => Err(Poseidon2RoundNumbersError::UnsupportedWidthAndExponent {
134                field_bits: prime_bit_number,
135                width,
136                exponent: d,
137            }),
138        },
139        _ => Err(Poseidon2RoundNumbersError::UnsupportedFieldSize {
140            field_bits: prime_bit_number,
141        }),
142    }
143}
144
145#[cfg(test)]
146mod tests {
147    use alloc::format;
148    use alloc::string::ToString;
149
150    use p3_baby_bear::BabyBear;
151    use p3_field::PrimeField64;
152
153    use super::{Poseidon2RoundNumbersError, poseidon2_round_numbers_128};
154
155    #[test]
156    fn invalid_sbox_exponent_reports_the_exponent_and_group_order() {
157        let error = poseidon2_round_numbers_128::<BabyBear>(16, 2).unwrap_err();
158        assert_eq!(
159            error,
160            Poseidon2RoundNumbersError::InvalidSboxExponent {
161                exponent: 2,
162                field_order_minus_one: BabyBear::ORDER_U64 - 1,
163            }
164        );
165        assert_eq!(
166            error.to_string(),
167            format!(
168                "Poseidon2 S-box exponent 2 is not coprime to the field order minus one ({})",
169                BabyBear::ORDER_U64 - 1
170            )
171        );
172    }
173
174    #[test]
175    fn unsupported_parameters_report_every_table_key() {
176        let error = poseidon2_round_numbers_128::<BabyBear>(15, 7).unwrap_err();
177        assert_eq!(
178            error,
179            Poseidon2RoundNumbersError::UnsupportedWidthAndExponent {
180                field_bits: 31,
181                width: 15,
182                exponent: 7,
183            }
184        );
185        assert_eq!(
186            error.to_string(),
187            "no precomputed Poseidon2 round count for a 31-bit field with width 15 and S-box exponent 7"
188        );
189    }
190
191    #[test]
192    fn unsupported_field_size_message_reports_the_table_key() {
193        let error = Poseidon2RoundNumbersError::UnsupportedFieldSize { field_bits: 48 };
194        assert_eq!(
195            error.to_string(),
196            "no precomputed Poseidon2 round counts for a 48-bit field"
197        );
198    }
199}
p3_poseidon2/round_numbers.rs

p3_poseidon2/
round_numbers.rs
