Skip to main content

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}