|
14 | 14 | * 1. A base sampler via a cumulative distribution table (CDT) that |
15 | 15 | * samples from a half-Gaussian D_{Z+,sigma_0} with sigma_0 = |
16 | 16 | * sigma_min (the smallest per-level sigma in the Falcon tree). |
17 | | - * 2. Bernoulli trials for acceptance/rejection, using the |
18 | | - * decomposition of exp(-x) into a product of table-driven |
19 | | - * factors. |
| 17 | + * 2. Bernoulli trials for acceptance/rejection, using BerExp to |
| 18 | + * compute exp(-x) via a degree-12 minimax polynomial with |
| 19 | + * precision better than 2^-50 over [0, ln2), satisfying the |
| 20 | + * Renyi divergence bound required by the FN-DSA security proof. |
20 | 21 | * 3. Combination of base samples with rejection to produce a |
21 | 22 | * sample from D_{Z,mu,sigma} for arbitrary (mu, sigma). |
| 23 | + * |
| 24 | + * Polynomial coefficients for the BerExp approximation are from the |
| 25 | + * FACCT paper (Zhao et al., 2018) via the Falcon reference |
| 26 | + * implementation. |
22 | 27 | */ |
23 | 28 |
|
24 | 29 | #include <math.h> |
@@ -139,64 +144,79 @@ base_sampler(pqc_shake256_ctx *sctx) |
139 | 144 | * BerExp: accept with probability ~ exp(-x), where x is a non-negative |
140 | 145 | * double. This uses the standard Falcon approach: |
141 | 146 | * - Decompose x = s * ln(2) + r, 0 <= r < ln(2). |
142 | | - * - Flip s coins each with probability 1/2; if any fail, reject. |
143 | | - * - Accept with probability exp(-r) using a polynomial approx. |
| 147 | + * - Evaluate exp(-r) using a degree-12 minimax polynomial with |
| 148 | + * precision better than 2^-50 over [0, ln2). |
| 149 | + * - Shift right by s bits for the 2^(-s) factor. |
| 150 | + * - Constant-time Bernoulli comparison against uniform random. |
144 | 151 | * |
145 | | - * Returns 1 (accept) or 0 (reject). Constant-time. |
| 152 | + * Returns 1 (accept) or 0 (reject). |
146 | 153 | */ |
147 | 154 | static int |
148 | 155 | ber_exp(pqc_shake256_ctx *sctx, double x) |
149 | 156 | { |
150 | 157 | int s; |
151 | | - double r; |
| 158 | + double r, y; |
152 | 159 | uint64_t w, z; |
153 | | - int32_t sw; |
| 160 | + uint32_t sw; |
154 | 161 |
|
155 | 162 | static const double LN2 = 0.6931471805599453; |
156 | 163 | static const double INV_LN2 = 1.4426950408889634; |
157 | 164 |
|
158 | 165 | s = (int)floor(x * INV_LN2); |
159 | 166 | r = x - (double)s * LN2; |
160 | 167 |
|
161 | | - /* s should be small (< 64 normally). Clamp for safety. */ |
162 | | - sw = (int32_t)s; |
163 | | - sw |= (int32_t)(63 - sw) >> 31; /* if s > 63, set sw = 63 */ |
164 | | - sw &= 63; |
165 | | - |
166 | 168 | /* |
167 | | - * Compute w = floor(exp(-r) * 2^63) using a degree-11 polynomial. |
168 | | - * Coefficients are chosen for the range [0, ln(2)]. |
| 169 | + * When x < 0 (possible with the current simplified ffSampling |
| 170 | + * that uses a global sigma), s is negative. Clamp to s=0, r=0 |
| 171 | + * so the polynomial yields exp(0) = 1 and the test accepts |
| 172 | + * with probability ~1. |
169 | 173 | */ |
170 | | - { |
171 | | - double p; |
172 | | - double rr = -r; |
173 | | - double term; |
174 | | - int k; |
175 | | - |
176 | | - /* exp(-r) = sum_{k=0}^{11} (-r)^k / k! */ |
177 | | - p = 0.0; |
178 | | - term = 1.0; |
179 | | - for (k = 0; k <= 11; k++) { |
180 | | - p += term; |
181 | | - term *= rr / (double)(k + 1); |
182 | | - } |
183 | | - /* p is now approximately exp(-r), in [exp(-ln2), 1] ~ [0.5, 1]. */ |
184 | | - /* Scale to 63-bit integer. */ |
185 | | - w = (uint64_t)(p * 9223372036854775808.0); /* p * 2^63 */ |
| 174 | + if (s < 0) { |
| 175 | + s = 0; |
| 176 | + r = 0.0; |
186 | 177 | } |
187 | 178 |
|
| 179 | + /* Clamp s to [0, 63] (constant-time). */ |
| 180 | + sw = (uint32_t)s; |
| 181 | + sw ^= (sw ^ 63u) & -(uint32_t)((63u - sw) >> 31); |
| 182 | + |
188 | 183 | /* |
189 | | - * Rejection for the integer part s: flip s independent fair coins. |
190 | | - * We shift w right by s bits (constant-time). |
| 184 | + * Evaluate exp(-r) using a degree-12 minimax polynomial via |
| 185 | + * Horner's method. Coefficients from Zhao et al., FACCT (2018), |
| 186 | + * via the Falcon reference implementation (fpr_expm_p63). |
| 187 | + * |
| 188 | + * Maximum relative error over [0, ln2) is below 2^-50, well |
| 189 | + * within the ~2^-40 Renyi divergence floor required by the |
| 190 | + * FN-DSA security proof. |
| 191 | + */ |
| 192 | + y = 0.000000002073772366009083061987; |
| 193 | + y = 0.000000025299506379442070029551 - y * r; |
| 194 | + y = 0.000000275607356160477811864927 - y * r; |
| 195 | + y = 0.000002755586350219122514855659 - y * r; |
| 196 | + y = 0.000024801566833585381209939524 - y * r; |
| 197 | + y = 0.000198412739277311890541063977 - y * r; |
| 198 | + y = 0.001388888894063186997887560103 - y * r; |
| 199 | + y = 0.008333333327800835146903501993 - y * r; |
| 200 | + y = 0.041666666666110491190622155955 - y * r; |
| 201 | + y = 0.166666666666984014666397229121 - y * r; |
| 202 | + y = 0.500000000000019206858326015208 - y * r; |
| 203 | + y = 0.999999999999994892974086724280 - y * r; |
| 204 | + y = 1.000000000000000000000000000000 - y * r; |
| 205 | + |
| 206 | + /* Scale to 63-bit fixed-point. */ |
| 207 | + w = (uint64_t)(y * 9223372036854775808.0); /* y * 2^63 */ |
| 208 | + |
| 209 | + /* |
| 210 | + * Multiply by 2^(-s): shift right by sw bits. |
191 | 211 | */ |
192 | 212 | w >>= sw; |
193 | 213 |
|
194 | 214 | /* |
195 | | - * Final Bernoulli test: accept if a uniform random < w. |
| 215 | + * Constant-time Bernoulli test: accept if uniform random < w. |
196 | 216 | */ |
197 | 217 | z = prng_u64(sctx); |
198 | | - z &= 0x7FFFFFFFFFFFFFFFULL; /* mask to 63 bits for comparison with w */ |
199 | | - return (z < w) ? 1 : 0; |
| 218 | + z &= 0x7FFFFFFFFFFFFFFFULL; |
| 219 | + return (int)ct_lt_u64(z, w); |
200 | 220 | } |
201 | 221 |
|
202 | 222 | /* ------------------------------------------------------------------ */ |
@@ -228,6 +248,14 @@ fndsa_sampler_init(fndsa_sampler_ctx_t *ctx, |
228 | 248 | * 4. Accept with probability proportional to |
229 | 249 | * exp(-( (z0 - r)^2 / (2*sigma^2) - z0^2/(2*sigma0^2) )) |
230 | 250 | * where r = mu - round(mu). |
| 251 | + * |
| 252 | + * NOTE: The full Falcon SamplerZ multiplies the acceptance probability |
| 253 | + * by ccs = sigma_min / sigma. This factor is currently omitted because |
| 254 | + * the ffSampling in sign.c uses a single global sigma rather than the |
| 255 | + * per-coefficient sigmas from the LDL* Gram-Schmidt tree. With the |
| 256 | + * global sigma, ccs would be ~0.008, making acceptance vanishingly rare. |
| 257 | + * The ccs factor should be added when ffSampling is corrected to use |
| 258 | + * per-coefficient sigmas (where ccs is typically 0.3--1.0). |
231 | 259 | */ |
232 | 260 | int32_t |
233 | 261 | fndsa_sampler_sample(fndsa_sampler_ctx_t *ctx, double mu, double sigma) |
|
0 commit comments