Coverage Report

Created: 2021-02-21 07:20

/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
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
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
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
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
58
   // x <- binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p)))
59
0
   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
0
   res += x + k * ((n - k) / 2.0);
65
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
79
0
   double min = cout_total(n, k, w, p, 0);
80
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
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
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
106
0
      min = std::min(min, lwf);
107
0
      }
108
109
0
   return static_cast<size_t>(min);
110
0
   }
111
112
}