Botan 3.0.0
Crypto and TLS for C&
mce_workfactor.cpp
Go to the documentation of this file.
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
14namespace Botan {
15
16namespace {
17
18double binomial(size_t n, size_t k)
19 {
20 double x = 1;
21
22 for(size_t i = 0; i != k; ++i)
23 {
24 x *= n - i;
25 x /= k -i;
26 }
27
28 return x;
29 }
30
31double log_binomial(size_t n, size_t k)
32 {
33 double x = 0;
34
35 for(size_t i = 0; i != k; ++i)
36 {
37 x += std::log(n - i);
38 x -= std::log(k - i);
39 }
40
41 return x / std::log(2);
42 }
43
44double nb_iter(size_t n, size_t k, size_t w, size_t p, size_t l)
45 {
46 double x = 2 * log_binomial(k / 2, p);
47 x += log_binomial(n - k - l, w - 2 * p);
48 x = log_binomial(n, w) - x;
49 return x;
50 }
51
52double cout_iter(size_t n, size_t k, size_t p, size_t l)
53 {
54 double x = binomial(k / 2, p);
55 const size_t i = static_cast<size_t>(std::log(x) / std::log(2));
56 double res = 2 * p * (n - k - l) * std::ldexp(x * x, -static_cast<int>(l));
57
58 // x <- binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p)))
59 x *= 2 * (2 * l + i);
60
61 // res <- k*(n-k)/2 +
62 // binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) +
63 // 2*p*(n-k-l)*binomial(k/2,p)^2/2^l
64 res += x + k * ((n - k) / 2.0);
65
66 return std::log(res) / std::log(2); // convert to bits
67 }
68
69double cout_total(size_t n, size_t k, size_t w, size_t p, size_t l)
70 {
71 return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l);
72 }
73
74double best_wf(size_t n, size_t k, size_t w, size_t p)
75 {
76 if(p >= k / 2)
77 return -1;
78
79 double min = cout_total(n, k, w, p, 0);
80
81 for(size_t l = 1; l < n - k; ++l)
82 {
83 const double lwf = cout_total(n, k, w, p, l);
84 if(lwf < min)
85 min = lwf;
86 else
87 break;
88 }
89
90 return min;
91 }
92
93}
94
95size_t mceliece_work_factor(size_t n, size_t t)
96 {
97 const size_t k = n - ceil_log2(n) * t;
98
99 double min = cout_total(n, k, t, 0, 0); // correspond a p=1
100 for(size_t p = 0; p != t / 2; ++p)
101 {
102 double lwf = best_wf(n, k + 1, t, p);
103 if(lwf < 0)
104 break;
105
106 min = std::min(min, lwf);
107 }
108
109 return static_cast<size_t>(min);
110 }
111
112}
Definition: alg_id.cpp:12
size_t mceliece_work_factor(size_t n, size_t t)
constexpr uint8_t ceil_log2(T x)
Definition: bit_ops.h:125