/src/botan/src/lib/pubkey/mce/mce_workfactor.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * (C) Copyright Projet SECRET, INRIA, Rocquencourt |
3 | | * (C) Bhaskar Biswas and Nicolas Sendrier |
4 | | * (C) 2014 Jack Lloyd |
5 | | * |
6 | | * Botan is released under the Simplified BSD License (see license.txt) |
7 | | * |
8 | | */ |
9 | | |
10 | | #include <botan/mceliece.h> |
11 | | #include <botan/internal/bit_ops.h> |
12 | | #include <cmath> |
13 | | |
14 | | namespace Botan { |
15 | | |
16 | | namespace { |
17 | | |
18 | | double binomial(size_t n, size_t k) |
19 | 0 | { |
20 | 0 | double x = 1; |
21 | 0 |
|
22 | 0 | for(size_t i = 0; i != k; ++i) |
23 | 0 | { |
24 | 0 | x *= n - i; |
25 | 0 | x /= k -i; |
26 | 0 | } |
27 | 0 |
|
28 | 0 | return x; |
29 | 0 | } |
30 | | |
31 | | double log_binomial(size_t n, size_t k) |
32 | 0 | { |
33 | 0 | double x = 0; |
34 | 0 |
|
35 | 0 | for(size_t i = 0; i != k; ++i) |
36 | 0 | { |
37 | 0 | x += std::log(n - i); |
38 | 0 | x -= std::log(k - i); |
39 | 0 | } |
40 | 0 |
|
41 | 0 | return x / std::log(2); |
42 | 0 | } |
43 | | |
44 | | double nb_iter(size_t n, size_t k, size_t w, size_t p, size_t l) |
45 | 0 | { |
46 | 0 | double x = 2 * log_binomial(k / 2, p); |
47 | 0 | x += log_binomial(n - k - l, w - 2 * p); |
48 | 0 | x = log_binomial(n, w) - x; |
49 | 0 | return x; |
50 | 0 | } |
51 | | |
52 | | double cout_iter(size_t n, size_t k, size_t p, size_t l) |
53 | 0 | { |
54 | 0 | double x = binomial(k / 2, p); |
55 | 0 | const size_t i = static_cast<size_t>(std::log(x) / std::log(2)); |
56 | 0 | double res = 2 * p * (n - k - l) * std::ldexp(x * x, -static_cast<int>(l)); |
57 | 0 |
|
58 | 0 | // x <- binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) |
59 | 0 | x *= 2 * (2 * l + i); |
60 | 0 |
|
61 | 0 | // res <- k*(n-k)/2 + |
62 | 0 | // binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) + |
63 | 0 | // 2*p*(n-k-l)*binomial(k/2,p)^2/2^l |
64 | 0 | res += x + k * ((n - k) / 2.0); |
65 | 0 |
|
66 | 0 | return std::log(res) / std::log(2); // convert to bits |
67 | 0 | } |
68 | | |
69 | | double cout_total(size_t n, size_t k, size_t w, size_t p, size_t l) |
70 | 0 | { |
71 | 0 | return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l); |
72 | 0 | } |
73 | | |
74 | | double best_wf(size_t n, size_t k, size_t w, size_t p) |
75 | 0 | { |
76 | 0 | if(p >= k / 2) |
77 | 0 | return -1; |
78 | 0 | |
79 | 0 | double min = cout_total(n, k, w, p, 0); |
80 | 0 |
|
81 | 0 | for(size_t l = 1; l < n - k; ++l) |
82 | 0 | { |
83 | 0 | const double lwf = cout_total(n, k, w, p, l); |
84 | 0 | if(lwf < min) |
85 | 0 | min = lwf; |
86 | 0 | else |
87 | 0 | break; |
88 | 0 | } |
89 | 0 |
|
90 | 0 | return min; |
91 | 0 | } |
92 | | |
93 | | } |
94 | | |
95 | | size_t mceliece_work_factor(size_t n, size_t t) |
96 | 0 | { |
97 | 0 | const size_t k = n - ceil_log2(n) * t; |
98 | 0 |
|
99 | 0 | double min = cout_total(n, k, t, 0, 0); // correspond a p=1 |
100 | 0 | for(size_t p = 0; p != t / 2; ++p) |
101 | 0 | { |
102 | 0 | double lwf = best_wf(n, k + 1, t, p); |
103 | 0 | if(lwf < 0) |
104 | 0 | break; |
105 | 0 | |
106 | 0 | min = std::min(min, lwf); |
107 | 0 | } |
108 | 0 |
|
109 | 0 | return static_cast<size_t>(min); |
110 | 0 | } |
111 | | |
112 | | } |