Botan  2.4.0
Crypto and TLS for C++11
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 
14 namespace Botan {
15 
16 namespace {
17 
18 double 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 
31 double 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 
44 double 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 
52 double 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 
69 double 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 
74 double 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 
95 size_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 }
size_t mceliece_work_factor(size_t n, size_t t)
Definition: alg_id.cpp:13
size_t ceil_log2(T x)
Definition: bit_ops.h:117