p3_poseidon2/
internal.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//! Inside the Poseidon2 paper, they describe that the internal layers of the hash
//! function do not require the full properties of MDS matrices.
//!
//! > For the partial rounds, the MDS property is not required anymore, and
//! > we can set up the matrix MI focusing only on providing full diffusion, breaking
//! > arbitrarily long subspace trails, and ensuring that the polynomial representation
//! > of the scheme is dense. (Section 5.2)
//!
//! This file implements a trait for linear layers that satisfy these three properties.

// The requirements translate to the following 3 properties:
// 1: All entries are non 0.
// 2: No Subspace Trails.
// 3: For a matrix of the form 1 + D, the diagonal D should also be non 0.
//
// Properties 1 and 3 are essentially immediate to check and a sufficient condition for property 2
// is that the minimal polynomial of the matrix M and all its powers M^2, ..., M^{2WIDTH} are maximal and irreducible.
// This is equivalent to all the characteristic polynomials being irreducible.
//
// These can be verified by the following sage code (Changing field/vector/length as desired):
//
// field = GF(2^31 - 1);
// length = 16;
// vector = [-2,  1,   2,   4,   8,  16,  32,  64, 128, 256, 1024, 4096, 8192, 16384, 32768, 65536];
// const_mat = matrix.ones(field, length);
// diag_mat  = diagonal_matrix(field, vector);
// for i in range(1, 2 * length + 1)
//      assert ((const_mat + diag_mat)^i).characteristic_polynomial().is_irreducible()

use alloc::vec::Vec;

use p3_field::{AbstractField, Field};

use crate::add_rc_and_sbox_generic;

/// Initialize an internal layer from a set of constants.
pub trait InternalLayerConstructor<AF>
where
    AF: AbstractField,
{
    /// A constructor which internally will convert the supplied
    /// constants into the appropriate form for the implementation.
    fn new_from_constants(internal_constants: Vec<AF::F>) -> Self;
}

/// Given a vector v compute the matrix vector product (1 + diag(v))state with 1 denoting the constant matrix of ones.
pub fn matmul_internal<F: Field, AF: AbstractField<F = F>, const WIDTH: usize>(
    state: &mut [AF; WIDTH],
    mat_internal_diag_m_1: [F; WIDTH],
) {
    let sum: AF = state.iter().cloned().sum();
    for i in 0..WIDTH {
        state[i] *= AF::from_f(mat_internal_diag_m_1[i]);
        state[i] += sum.clone();
    }
}

/// A trait containing all data needed to implement the internal layers of Poseidon2.
pub trait InternalLayer<AF, const WIDTH: usize, const D: u64>: Sync + Clone
where
    AF: AbstractField,
{
    /// Perform the internal layers of the Poseidon2 permutation on the given state.
    fn permute_state(&self, state: &mut [AF; WIDTH]);
}

/// A helper method which allows any field to easily implement Internal Layer.
/// This should only be used in places where performance is not critical.
#[inline]
pub fn internal_permute_state<AF: AbstractField, const WIDTH: usize, const D: u64>(
    state: &mut [AF; WIDTH],
    diffusion_mat: fn(&mut [AF; WIDTH]),
    internal_constants: &[AF::F],
) {
    for elem in internal_constants.iter() {
        add_rc_and_sbox_generic::<AF, D>(&mut state[0], *elem);
        diffusion_mat(state);
    }
}

/// The compiler doesn't realize that add is associative
/// so we help it out and minimize the dependency chains by hand.
#[inline(always)]
fn sum_7<AF: AbstractField + Copy>(state: &[AF]) -> AF {
    assert_eq!(state.len(), 7);

    let s01 = state[0] + state[1];
    let s23 = state[2] + state[3];
    let s45 = state[4] + state[5];

    let s0123 = s01 + s23;
    let s456 = s45 + state[6];
    s0123 + s456
}

/// The compiler doesn't realize that add is associative
/// so we help it out and minimize the dependency chains by hand.
#[inline(always)]
fn sum_8<AF: AbstractField + Copy>(state: &[AF]) -> AF {
    assert_eq!(state.len(), 8);

    let s01 = state[0] + state[1];
    let s23 = state[2] + state[3];
    let s45 = state[4] + state[5];
    let s67 = state[6] + state[7];

    let s0123 = s01 + s23;
    let s4567 = s45 + s67;
    s0123 + s4567
}

/// The compiler doesn't realize that add is associative
/// so we help it out and minimize the dependency chains by hand.
#[inline(always)]
pub fn sum_15<AF: AbstractField + Copy>(state: &[AF]) -> AF {
    assert_eq!(state.len(), 15);

    let bot_sum = sum_8(&state[..8]);
    let top_sum = sum_7(&state[8..]);

    bot_sum + top_sum
}

/// The compiler doesn't realize that add is associative
/// so we help it out and minimize the dependency chains by hand.
#[inline(always)]
pub fn sum_23<AF: AbstractField + Copy>(state: &[AF]) -> AF {
    assert_eq!(state.len(), 23);

    let bot_sum = sum_8(&state[..8]);
    let mid_sum = sum_8(&state[8..16]);
    let top_sum = sum_7(&state[16..]);

    bot_sum + mid_sum + top_sum
}