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

crystals_dilithium/poly/
lvl5.rs
