simple_saber/scheme.rs
1use crate::Saber;
2use simple_ring::{
3 Polynomial, RingParams, generate_cbd_sample,
4 generate_small_sample, generate_then_shake,
5};
6use crate::types::{SaberKeypair, SaberPublicKey};
7use serde::{Serialize, Deserialize};
8
9/*
10This file provides the core for the simple implementation of SABER scheme in Rust, using primitives given
11in simple-ring. SABER is based on LWR (Learning With Roundness) problem. For more informations / explanations,
12please read '/docs/pdf/simple-saber.pdf. (upcoming)
13*/
14
15
16#[derive(Debug, Clone, Serialize, Deserialize)]
17pub struct SaberCiphertext {
18 pub v: Polynomial, //The ciphertext V
19 pub u: Polynomial, //The other public key, noted as U or B'
20}
21
22pub type Key = [u8; 32]; //An alias
23
24impl Saber {
25
26 /// Intern but exposed functions for encryption/decryption (so that anyone can, from an external crate, use these methods)
27
28 pub fn round(&self, params: &RingParams, a: Polynomial) -> Polynomial { //The Round function
29 /*
30 Let a be a coefficient as a ∈ Z_q.
31 The round is â = round[ (a * p/q) ] mod p, so that â ∈ Z_p and not Z_q. Here, we don't manipulate floating numbers, so we compute the round as :
32
33 - First the scaling with p :
34
35 â = a * p
36
37 - Then, we add q/2 to simulate a mathematical rounding, and not doing a floor (because by default the compilator does a floor when rounding) :
38
39 â = ap + q/2
40
41 - We divide by q :
42
43 â = ( ap + q/2 ) / q
44
45 - We finally reduce by p :
46
47 â = [ ( ap + q/2 ) / q ] mod p
48
49 For example, with a = 1 , p = 5 and q = 100 :
50
51 â = [ (12 * 5 + 50 ) / 100 ] mod 5
52 â = [ 110 / 100 ] mod 5
53 â = 1.10
54 â = 1 (floor)
55
56 If we had not done the + q /2 :
57
58 â = [ 60/100 ] mod 5
59 â = 0.60
60 â = 0 (floor)
61 */
62 let n = params.n;
63 let q = params.q;
64 let p = self.p;
65
66 let mut result = vec![0u64; n];
67 for i in 0..n {
68 result[i] = (((a.coeffs[i] * p) + q / 2) / q) % p;
69 }
70 Polynomial::new(result)
71 }
72
73 pub fn encode(&self, params: &RingParams, m: &Polynomial) -> Polynomial { //The encoding function
74 /*
75 The encoding, in Saber, is just the preojection of the message m, as m ∈ {0, 1} (because it's compound of binary coefficients), in Z_p
76 To do that, we consider two cases :
77
78 - The coefficient is equal to 0 => the coefficient in Z_p is also 0
79
80 - The coefficient is equal to 1 => the coefficient in Z_p becames equal to p/2 (centered in Z_p)
81
82 To do that, we use the scaling, a polynomial operation, and we compute it with a factor p/2.
83 (cause it's the same as matching coefficients, but mathematically : 0 * p/2 = 0 and 1 * p/2 = p/2)
84 */
85
86 let p = self.p;
87 let factor = p / 2;
88 let m = m.scale(params, factor);
89 m.reduce(p as u128)
90 }
91
92 pub fn decode(&self, params: &RingParams, encoded: &Polynomial) -> Polynomial {
93 /*
94 For decoding, we consider now that we have coefficients in Z_p, so c ∈ {0, 1, 2, 3, ..., p - 1}.
95 We can't do a simple matching as in the encoding function.
96 We consider now four bounds :
97 {0, p/4, 3p/4, p} (which is the same as "cutting" Z_p into 4 equivalent pieces)
98
99 Now, considering the coefficients were centered before, in the encoding, we two cases :
100
101 - If the coefficients is in [p/4; 3p/4[ => it becames a 1
102
103 - Else, it becames a 0
104 */
105 let p = self.p;
106 let quarter_p = p / 4;
107 let three_quarter_p = 3 * p / 4;
108 let mut coeffs = vec![0u64; params.n];
109 for i in 0..params.n {
110 let raw = encoded.coeffs[i] % p; //The encoded is in Z_q, we first pass it in Z_p
111 coeffs[i] = if raw >= quarter_p && raw < three_quarter_p { 1 } else { 0 };
112 }
113 Polynomial::new(coeffs)
114 }
115
116 pub fn compress(&self, poly: &Polynomial) -> Polynomial {
117 let mut result = vec![0u64; poly.coeffs.len()];
118 for (i, &c) in poly.coeffs.iter().enumerate() {
119 let val = c as i64;
120 let reduced = val % self.p as i64;
121 result[i] = if reduced < 0 { (reduced + self.p as i64) as u64 } else { reduced as u64 };
122 }
123 Polynomial::new(result)
124 }
125
126 pub fn lift(&self, poly: &Polynomial) -> Polynomial {
127 let result: Vec<u64> = poly.coeffs.iter().map(|&c| (c * self.params.q as u64) / self.p).collect(); //It goes back in Z_q
128 Polynomial::new(result)
129 }
130
131 pub fn keygen(&self) -> SaberKeypair {
132 let params = &self.params;
133 let q = params.q;
134 let ntt_tables = &self.ntt_precalculated;
135
136 let (a, seed) = generate_then_shake(params, simple_ring::SeedType::NotGiven);
137 let a = a.to_poly(q);
138
139 let s = generate_small_sample(params).to_poly(q);
140
141 let b_raw = a.mul_ntt(params, ntt_tables, &s);
142 let b = self.round(params, b_raw);
143
144 SaberKeypair::new(b, seed, s)
145 }
146
147 pub fn encrypt(&self, public_key: &SaberPublicKey, message: &Polynomial) -> SaberCiphertext {
148 let seed = public_key.a_seed;
149 let b = &public_key.b; // In Z_p
150
151 let params = &self.params;
152 let q = params.q;
153 let n = params.n;
154 let ntt_tables = &self.ntt_precalculated;
155
156 let a = generate_then_shake(params, simple_ring::SeedType::Given(seed)).0.to_poly(q); //In Z_q
157
158 let r = generate_cbd_sample(n, self.eta).to_poly(q); //In Z_q
159
160 let u_raw = a.mul_ntt(params, ntt_tables, &r); //In Z_q
161 let u = self.round(params, u_raw); //Then returned in Z_p
162
163 let b_in_q = self.lift(b);
164
165 let v_raw = b_in_q.mul_ntt(params, ntt_tables, &r); //In Z_q
166 let v = self.round(params, v_raw); //Then returned in Z_p
167
168 let encoded_message = self.encode(params, message);
169 let v_message = v.sum(params, &encoded_message);
170 let v_message = v_message.reduce(self.p as u128);
171
172 SaberCiphertext { v: v_message, u }
173 }
174
175 pub fn decrypt(&self, keypair: &SaberKeypair, encapsulated: &SaberCiphertext) -> Polynomial {
176 let params = &self.params;
177 let ntt_tables = &self.ntt_precalculated;
178 let s = &keypair.secret_key; //In Z_q
179 let u = &encapsulated.u; //In Z_p
180 let v = &encapsulated.v; //In Z_p
181 let p = self.p;
182
183 let u_in_q = self.lift(u); //It goes back in Z_q so that we can do the NTT multiplication, which is in Z_q
184
185 let su_raw = s.mul_ntt(params, ntt_tables, &u_in_q); //In Z_q
186 let su = self.round(params, su_raw); //Then returned in Z_p
187
188 let mut m_poly_coeffs = vec![0u64; params.n]; // v - su, in Z_p
189 for i in 0..params.n {
190 m_poly_coeffs[i] = if v.coeffs[i] >= su.coeffs[i] {
191 v.coeffs[i] - su.coeffs[i]
192 } else {
193 p - (su.coeffs[i] - v.coeffs[i])
194 };
195 }
196 let m_poly = Polynomial::new(m_poly_coeffs);
197 self.decode(params, &m_poly) //Final decoding, in Z_p
198 }
199
200
201}