p3_poseidon1/
external.rs

1//! Full (external) round layers for the Poseidon1 permutation.
2//!
3//! # Overview
4//!
5//! Full rounds apply the S-box to **every** state element, providing strong resistance
6//! against statistical attacks (differential, linear, truncated differential, rebound).
7//! The Poseidon1 paper requires at least RF = 6 full rounds for 128-bit security against
8//! these attacks (see Section 5 and Appendix C of the paper).
9//!
10//! # Round Structure
11//!
12//! Each full round applies three operations in sequence:
13//!
14//! ```text
15//!   state → AddRoundConstants → S-box(all elements) → MDS multiply → state'
16//! ```
17//!
18//! The MDS multiply is dispatched via the [`Permutation`] trait, allowing concrete fields
19//! to use fast convolution (e.g., Karatsuba) while generic `Algebra<F>` types fall back
20//! to O(t^2) dense multiplication.
21//!
22//! # Cost
23//!
24//! Each full round costs t S-box evaluations + O(t^2) for the dense MDS multiply,
25//! giving a total full-round cost of O(RF * t^2). Since RF is small (typically 8),
26//! this is acceptable even for large t.
27
28use alloc::vec::Vec;
29
30use p3_field::{Algebra, Field, InjectiveMonomial, PrimeCharacteristicRing};
31pub use p3_mds::util::mds_multiply;
32use p3_symmetric::Permutation;
33
34/// Pre-computed constants for the full (external) rounds.
35///
36/// The full rounds are split equally: half before the partial rounds (initial),
37/// and half after (terminal).
38///
39/// The MDS matrix is **not** stored here. It is dispatched through a permutation
40/// trait at the call site. This allows concrete fields to use optimized
41/// implementations (e.g., Karatsuba convolution) while generic algebra types
42/// fall back to dense O(t^2) multiplication.
43#[derive(Debug, Clone)]
44pub struct FullRoundConstants<F, const WIDTH: usize> {
45    /// Round constants for the initial full rounds.
46    pub initial: Vec<[F; WIDTH]>,
47
48    /// Round constants for the terminal full rounds.
49    pub terminal: Vec<[F; WIDTH]>,
50
51    /// Dense N x N MDS matrix expanded from the circulant first column.
52    ///
53    /// The scalar MDS path uses a Karatsuba convolution with `i64` intermediates.
54    /// That approach relies on bit-shifts for halving.
55    ///
56    /// Packed SIMD types cannot perform bit-shifts. They only support field
57    /// arithmetic.
58    ///
59    /// Storing the fully expanded matrix lets SIMD implementations either:
60    ///
61    /// - Fall back to dense O(t^2) multiplication over `Algebra<F>`.
62    /// - Extract the first column for a field-level Karatsuba that uses
63    ///   `halve()` instead of bit-shifts.
64    pub dense_mds: [[F; WIDTH]; WIDTH],
65}
66
67/// Construct a full round layer from pre-computed constants.
68pub trait FullRoundLayerConstructor<F: Field, const WIDTH: usize> {
69    /// Build the layer from the full-round constants.
70    fn new_from_constants(constants: FullRoundConstants<F, WIDTH>) -> Self;
71}
72
73/// The full (external) round layer of the Poseidon1 permutation.
74///
75/// Implementors apply the RF/2 initial or terminal full rounds to the state.
76/// Field-specific implementations (e.g., NEON, AVX2) can override the generic
77/// behavior for better performance.
78pub trait FullRoundLayer<R, const WIDTH: usize, const D: u64>: Sync + Clone
79where
80    R: PrimeCharacteristicRing,
81{
82    /// Apply the RF/2 initial full rounds.
83    fn permute_state_initial(&self, state: &mut [R; WIDTH]);
84
85    /// Apply the RF/2 terminal full rounds.
86    fn permute_state_terminal(&self, state: &mut [R; WIDTH]);
87}
88
89/// Apply the initial full rounds (generic implementation).
90///
91/// Each round: add round constants, S-box on all elements, MDS multiply.
92/// The MDS multiply is dispatched via the permutation trait parameter.
93#[inline]
94pub fn full_round_initial_permute_state<
95    F: Field,
96    A: Algebra<F> + InjectiveMonomial<D>,
97    Mds: Permutation<[A; WIDTH]>,
98    const WIDTH: usize,
99    const D: u64,
100>(
101    state: &mut [A; WIDTH],
102    constants: &FullRoundConstants<F, WIDTH>,
103    mds: &Mds,
104) {
105    for round_constants in &constants.initial {
106        // AddRoundConstants: state[i] += rc[i].
107        for (s, &rc) in state.iter_mut().zip(round_constants.iter()) {
108            *s += rc;
109        }
110        // S-box: state[i] = state[i]^D for all i.
111        for s in state.iter_mut() {
112            *s = s.injective_exp_n();
113        }
114        // MixLayer: dispatched via Permutation trait.
115        mds.permute_mut(state);
116    }
117}
118
119/// Apply the terminal full rounds (generic implementation).
120///
121/// Same structure as the initial full rounds, but uses the terminal constants.
122#[inline]
123pub fn full_round_terminal_permute_state<
124    F: Field,
125    A: Algebra<F> + InjectiveMonomial<D>,
126    Mds: Permutation<[A; WIDTH]>,
127    const WIDTH: usize,
128    const D: u64,
129>(
130    state: &mut [A; WIDTH],
131    constants: &FullRoundConstants<F, WIDTH>,
132    mds: &Mds,
133) {
134    for round_constants in &constants.terminal {
135        // AddRoundConstants: state[i] += rc[i].
136        for (s, &rc) in state.iter_mut().zip(round_constants.iter()) {
137            *s += rc;
138        }
139        // S-box: state[i] = state[i]^D for all i.
140        for s in state.iter_mut() {
141            *s = s.injective_exp_n();
142        }
143        // MixLayer: dispatched via Permutation trait.
144        mds.permute_mut(state);
145    }
146}
p3_poseidon1/external.rs

p3_poseidon1/
external.rs
