crystals_dilithium/poly/
lvl5.rs

1use super::{Poly, N};
2use crate::{fips202, params, rounding};
3
4const UNIFORM_ETA_NBLOCKS: usize = (135 + fips202::SHAKE256_RATE) / fips202::SHAKE256_RATE;
5#[allow(clippy::manual_div_ceil)]
6const UNIFORM_GAMMA1_NBLOCKS: usize =
7    (params::lvl5::POLYZ_PACKEDBYTES + fips202::SHAKE256_RATE - 1) / fips202::SHAKE256_RATE;
8
9/// For all coefficients c of the input polynomial, compute high and low bits c0, c1 such c mod Q = c1*ALPHA + c0 with -ALPHA/2 < c0 <= ALPHA/2 except c1 = (Q-1)/ALPHA where we set c1 = 0 and -ALPHA/2 <= c0 = c mod Q - Q < 0.
10/// Assumes coefficients to be standard representatives.
11///
12/// # Arguments
13///
14/// * 'a' - input polynomial
15///
16/// Returns a touple of polynomials with coefficients c0, c1
17pub fn decompose(a1: &mut Poly, a0: &mut Poly) {
18    for i in 0..N {
19        (a1.coeffs[i], a0.coeffs[i]) = rounding::lvl5::decompose(a1.coeffs[i]);
20    }
21}
22
23/// Compute hint polynomial, the coefficients of which indicate whether the low bits of the corresponding coefficient of the input polynomial overflow into the high bits.
24///
25/// # Arguments
26///
27/// * 'a0' - low part of input polynomial
28/// * 'a1' - low part of input polynomial
29///
30/// Returns the hint polynomial and the number of 1s
31pub fn make_hint(h: &mut Poly, a0: &Poly, a1: &Poly) -> i32 {
32    let mut s: i32 = 0;
33    for i in 0..N {
34        h.coeffs[i] = rounding::lvl5::make_hint(a0.coeffs[i], a1.coeffs[i]);
35        s += h.coeffs[i];
36    }
37    s
38}
39
40/// Use hint polynomial to correct the high bits of a polynomial.
41///
42/// # Arguments
43///
44/// * 'a' - input polynomial
45/// * 'hint' - hint polynomial
46///
47/// Returns polynomial with corrected high bits
48pub fn use_hint(a: &mut Poly, hint: &Poly) {
49    for i in 0..N {
50        a.coeffs[i] = rounding::lvl5::use_hint(a.coeffs[i], hint.coeffs[i]);
51    }
52}
53
54/// Use hint polynomial to correct the high bits of a polynomial in place.
55///
56/// # Arguments
57///
58/// * 'a' - input polynomial to have high bits corrected
59/// * 'hint' - hint polynomial
60pub fn use_hint_ip(a: &mut Poly, hint: &Poly) {
61    for i in 0..N {
62        a.coeffs[i] = rounding::lvl5::use_hint(a.coeffs[i], hint.coeffs[i]);
63    }
64}
65
66/// Sample uniformly random coefficients in [-ETA, ETA] by performing rejection sampling using array of random bytes.
67///
68/// Returns number of sampled coefficients. Can be smaller than len if not enough random bytes were given
69pub fn rej_eta(a: &mut [i32], alen: usize, buf: &[u8], buflen: usize) -> usize {
70    let mut ctr = 0usize;
71    let mut pos = 0usize;
72    while ctr < alen && pos < buflen {
73        let mut t0 = (buf[pos] & 0x0F) as u32;
74        let mut t1 = (buf[pos] >> 4) as u32;
75        pos += 1;
76
77        if t0 < 15 {
78            t0 = t0 - (((205 * t0) >> 10) * 5);
79            a[ctr] = 2 - t0 as i32;
80            ctr += 1;
81        }
82        if t1 < 15 && ctr < alen {
83            t1 = t1 - (((205 * t1) >> 10) * 5);
84            a[ctr] = 2 - t1 as i32;
85            ctr += 1;
86        }
87    }
88    ctr
89}
90
91/// Sample polynomial with uniformly random coefficients in [-ETA,ETA] by performing rejection sampling using the output stream from SHAKE256(seed|nonce).
92pub fn uniform_eta(a: &mut Poly, seed: &[u8], nonce: u16) {
93    let mut state = fips202::KeccakState::default();
94    fips202::shake256_stream_init(&mut state, seed, nonce);
95
96    let mut buf = [0u8; UNIFORM_ETA_NBLOCKS * fips202::SHAKE256_RATE];
97    fips202::shake256_squeezeblocks(&mut buf, UNIFORM_ETA_NBLOCKS, &mut state);
98
99    let buflen = UNIFORM_ETA_NBLOCKS * fips202::SHAKE256_RATE;
100    let mut ctr = rej_eta(&mut a.coeffs, N, &buf, buflen);
101    while ctr < N {
102        fips202::shake256_squeezeblocks(&mut buf, 1, &mut state);
103        ctr += rej_eta(&mut a.coeffs[ctr..], N - ctr, &buf, fips202::SHAKE256_RATE);
104    }
105}
106
107/// Sample polynomial with uniformly random coefficients in [-(GAMMA1 - 1), GAMMA1 - 1] by performing rejection sampling on output stream of SHAKE256(seed|nonce).
108pub fn uniform_gamma1(a: &mut Poly, seed: &[u8], nonce: u16) {
109    let mut state = fips202::KeccakState::default();
110    fips202::shake256_stream_init(&mut state, seed, nonce);
111
112    let mut buf = [0u8; UNIFORM_GAMMA1_NBLOCKS * fips202::SHAKE256_RATE];
113    fips202::shake256_squeezeblocks(&mut buf, UNIFORM_GAMMA1_NBLOCKS, &mut state);
114    z_unpack(a, &buf);
115}
116
117/// Implementation of H. Samples polynomial with TAU nonzero coefficients in {-1,1} using the output stream of SHAKE256(seed).
118#[allow(clippy::needless_range_loop)]
119pub fn challenge(c: &mut Poly, seed: &[u8]) {
120    let mut state = fips202::KeccakState::default();
121    fips202::shake256_absorb(&mut state, seed, params::SEEDBYTES);
122    fips202::shake256_finalize(&mut state);
123
124    let mut buf = [0u8; fips202::SHAKE256_RATE];
125    fips202::shake256_squeezeblocks(&mut buf, 1, &mut state);
126
127    let mut signs: u64 = 0;
128    for i in 0..8 {
129        signs |= (buf[i] as u64) << (8 * i);
130    }
131
132    let mut pos: usize = 8;
133    c.coeffs.fill(0);
134    for i in (N - params::lvl5::TAU)..N {
135        let mut b: usize;
136        loop {
137            if pos >= fips202::SHAKE256_RATE {
138                fips202::shake256_squeezeblocks(&mut buf, 1, &mut state);
139                pos = 0;
140            }
141            b = buf[pos] as usize;
142            pos += 1;
143            if b <= i {
144                break;
145            }
146        }
147        c.coeffs[i] = c.coeffs[b];
148        c.coeffs[b] = 1 - 2 * ((signs & 1) as i32);
149        signs >>= 1;
150    }
151}
152
153/// Bit-pack polynomial with coefficients in [-ETA,ETA]. Input coefficients are assumed to lie in [Q-ETA,Q+ETA].
154#[allow(clippy::identity_op)]
155pub fn eta_pack(r: &mut [u8], a: &Poly) {
156    let mut t = [0u8; 8];
157    for i in 0..N / 8 {
158        t[0] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 0]) as u8;
159        t[1] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 1]) as u8;
160        t[2] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 2]) as u8;
161        t[3] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 3]) as u8;
162        t[4] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 4]) as u8;
163        t[5] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 5]) as u8;
164        t[6] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 6]) as u8;
165        t[7] = (params::lvl5::ETA as i32 - a.coeffs[8 * i + 7]) as u8;
166
167        r[3 * i + 0] = (t[0] >> 0) | (t[1] << 3) | (t[2] << 6);
168        r[3 * i + 1] = (t[2] >> 2) | (t[3] << 1) | (t[4] << 4) | (t[5] << 7);
169        r[3 * i + 2] = (t[5] >> 1) | (t[6] << 2) | (t[7] << 5);
170    }
171}
172
173/// Unpack polynomial with coefficients in [-ETA,ETA].
174#[allow(clippy::identity_op)]
175pub fn eta_unpack(r: &mut Poly, a: &[u8]) {
176    for i in 0..N / 8 {
177        r.coeffs[8 * i + 0] = (a[3 * i + 0] & 0x07) as i32;
178        r.coeffs[8 * i + 1] = ((a[3 * i + 0] >> 3) & 0x07) as i32;
179        r.coeffs[8 * i + 2] = (((a[3 * i + 0] >> 6) | (a[3 * i + 1] << 2)) & 0x07) as i32;
180        r.coeffs[8 * i + 3] = ((a[3 * i + 1] >> 1) & 0x07) as i32;
181        r.coeffs[8 * i + 4] = ((a[3 * i + 1] >> 4) & 0x07) as i32;
182        r.coeffs[8 * i + 5] = (((a[3 * i + 1] >> 7) | (a[3 * i + 2] << 1)) & 0x07) as i32;
183        r.coeffs[8 * i + 6] = ((a[3 * i + 2] >> 2) & 0x07) as i32;
184        r.coeffs[8 * i + 7] = ((a[3 * i + 2] >> 5) & 0x07) as i32;
185
186        r.coeffs[8 * i + 0] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 0];
187        r.coeffs[8 * i + 1] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 1];
188        r.coeffs[8 * i + 2] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 2];
189        r.coeffs[8 * i + 3] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 3];
190        r.coeffs[8 * i + 4] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 4];
191        r.coeffs[8 * i + 5] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 5];
192        r.coeffs[8 * i + 6] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 6];
193        r.coeffs[8 * i + 7] = params::lvl5::ETA as i32 - r.coeffs[8 * i + 7];
194    }
195}
196
197/// Bit-pack polynomial z with coefficients in [-(GAMMA1 - 1), GAMMA1 - 1].
198/// Input coefficients are assumed to be standard representatives.*
199#[allow(clippy::identity_op)]
200pub fn z_pack(r: &mut [u8], a: &Poly) {
201    let mut t = [0i32; 2];
202
203    for i in 0..N / 2 {
204        t[0] = params::lvl5::GAMMA1 as i32 - a.coeffs[2 * i + 0];
205        t[1] = params::lvl5::GAMMA1 as i32 - a.coeffs[2 * i + 1];
206
207        r[5 * i + 0] = (t[0]) as u8;
208        r[5 * i + 1] = (t[0] >> 8) as u8;
209        r[5 * i + 2] = (t[0] >> 16) as u8;
210        r[5 * i + 2] |= (t[1] << 4) as u8;
211        r[5 * i + 3] = (t[1] >> 4) as u8;
212        r[5 * i + 4] = (t[1] >> 12) as u8;
213    }
214}
215
216/// Unpack polynomial z with coefficients in [-(GAMMA1 - 1), GAMMA1 - 1].
217/// Output coefficients are standard representatives.
218#[allow(clippy::identity_op)]
219pub fn z_unpack(r: &mut Poly, a: &[u8]) {
220    for i in 0..N / 2 {
221        r.coeffs[2 * i + 0] = a[5 * i + 0] as i32;
222        r.coeffs[2 * i + 0] |= (a[5 * i + 1] as i32) << 8;
223        r.coeffs[2 * i + 0] |= (a[5 * i + 2] as i32) << 16;
224        r.coeffs[2 * i + 0] &= 0xFFFFF;
225
226        r.coeffs[2 * i + 1] = (a[5 * i + 2] as i32) >> 4;
227        r.coeffs[2 * i + 1] |= (a[5 * i + 3] as i32) << 4;
228        r.coeffs[2 * i + 1] |= (a[5 * i + 4] as i32) << 12;
229        r.coeffs[2 * i + 0] &= 0xFFFFF;
230
231        r.coeffs[2 * i + 0] = params::lvl5::GAMMA1 as i32 - r.coeffs[2 * i + 0];
232        r.coeffs[2 * i + 1] = params::lvl5::GAMMA1 as i32 - r.coeffs[2 * i + 1];
233    }
234}
235
236/// Bit-pack polynomial w1 with coefficients in [0, 15].
237/// Input coefficients are assumed to be standard representatives.
238#[allow(clippy::needless_range_loop, clippy::identity_op)]
239pub fn w1_pack(r: &mut [u8], a: &Poly) {
240    for i in 0..N / 2 {
241        r[i] = (a.coeffs[2 * i + 0] | (a.coeffs[2 * i + 1] << 4)) as u8;
242    }
243}
crystals_dilithium/poly/lvl5.rs

crystals_dilithium/poly/
lvl5.rs
