Implement a strength estimator for McEliece keys based on HyMES version

6 files changed, 125 insertions, 15 deletions

diff --git a/src/cmd/speed_pk.cpp b/src/cmd/speed_pk.cpp
index 141248d7d..6d20065cc 100644
--- a/src/cmd/speed_pk.cpp
+++ b/src/cmd/speed_pk.cpp
@@ -682,8 +682,6 @@ void benchmark_mce(RandomNumberGenerator& rng,
                    Benchmark_Report& report)
    {
    const std::vector<std::pair<size_t, size_t>> params = {
-      { 256, 15 },
-      { 512, 33 },
       { 1024, 35 },
       { 2048, 50 },
       { 2960, 56 },
@@ -727,7 +725,8 @@ void benchmark_mce(RandomNumberGenerator& rng,
 
       std::ostringstream keysize_report;
       keysize_report << "(size " << pub_key.x509_subject_public_key().size() << " pub "
-                     << priv_key.pkcs8_private_key().size() << " priv)";
+                     << priv_key.pkcs8_private_key().size() << " priv "
+                     << pub_key.estimated_strength() << " work factor)";
 
       report.report(nm + " " + keysize_report.str(), keygen_timer);
       report.report(nm, enc_timer);
diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h
index ee5f8ab8f..6e6dffe02 100644
--- a/src/lib/pubkey/mce/mceliece.h
+++ b/src/lib/pubkey/mce/mceliece.h
@@ -143,6 +143,12 @@ class BOTAN_DLL McEliece_Public_Operation : public PK_Ops::Encryption
   u32bit m_code_length;
 };
 
+/**
+* Estimate work factor for McEliece
+* @return estimated security level for these key parameters
+*/
+BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t k, size_t t);
+
 }
 
 
diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp
index 7da5aefed..2b4a277ad 100644
--- a/src/lib/pubkey/mce/mceliece_key.cpp
+++ b/src/lib/pubkey/mce/mceliece_key.cpp
@@ -76,7 +76,9 @@ McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) :
 
 size_t McEliece_PublicKey::estimated_strength() const
    {
-   return mceliece_work_factor(m_t, m_code_length);
+   const u32bit ext_deg = ceil_log2(m_code_length);
+   const size_t k = m_code_length - ext_deg * m_t;
+   return mceliece_work_factor(m_code_length, k, m_t);
    }
 
 McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits)
diff --git a/src/lib/pubkey/mce/workfactor.cpp b/src/lib/pubkey/mce/workfactor.cpp
new file mode 100644
index 000000000..18eaf65e5
--- /dev/null
+++ b/src/lib/pubkey/mce/workfactor.cpp
@@ -0,0 +1,114 @@
+/**
+ * (C) Copyright Projet SECRET, INRIA, Rocquencourt
+ * (C) Bhaskar Biswas and Nicolas Sendrier
+ *
+ * Distributed under the terms of the Botan license
+ *
+ */
+
+#include <botan/mceliece.h>
+#include <cmath>
+
+namespace Botan {
+
+namespace {
+
+double binomial(size_t n, size_t k)
+   {
+   double x = 1;
+
+   for(size_t i = 0; i != k; ++i)
+      {
+      x *= n - i;
+      x /= k -i;
+      }
+
+   return x;
+   }
+
+double log_binomial(size_t n, size_t k)
+   {
+   double x = 0;
+
+   for(size_t i = 0; i != k; ++i)
+      {
+      x += std::log(n - i);
+      x -= std::log(k - i);
+      }
+
+   return x / std::log(2);
+   }
+
+double nb_iter(size_t n, size_t k, size_t w, size_t p, size_t l)
+   {
+   double x = 2 * log_binomial(k / 2, p);
+   x += log_binomial(n - k - l, w - 2 * p);
+   x = log_binomial(n, w) - x;
+   return x;
+   }
+
+double cout_iter(size_t n, size_t k, size_t p, size_t l)
+   {
+   // x <- binomial(k/2,p)
+   double x = binomial(k / 2, p);
+   // i <- log[2](binomial(k/2,p))
+   size_t i = (size_t) (std::log(x) / std::log(2)); // normalement i < 2^31
+   // res <- 2*p*(n-k-l)*binomial(k/2,p)^2/2^l
+   double res = 2 * p * (n - k - l) * ldexp(x * x, -l);
+   // x <- binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p)))
+   x *= 2 * (2 * l + i);
+   // res <- k*(n-k)/2 +
+   // binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) +
+   // 2*p*(n-k-l)*binomial(k/2,p)^2/2^l
+   res += x + k * ((n - k) / 2.0);
+
+   return std::log(res) / std::log(2);
+   }
+
+double cout_total(size_t n, size_t k, size_t w, size_t p, size_t l)
+   {
+   return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l);
+   }
+
+double best_wf(size_t n, size_t k, size_t w, size_t p)
+   {
+   if(p >= k / 2)
+      return -1;
+
+   // On part de l = u, en faisant croitre l.
+   // On s'arrète dés que le work factor croit.
+   // Puis on explore les valeurs <u, mais en tenant de la convexite'
+
+   double min = cout_total(n, k, w, p, 0);
+   for(size_t l = 1; l < n - k; ++l)
+      {
+      double lwf = cout_total(n, k, w, p, l);
+      if(lwf < min)
+         {
+         min = lwf;
+         }
+      else
+         break;
+      }
+
+   return min;
+   }
+
+}
+
+size_t mceliece_work_factor(size_t n, size_t k, size_t t)
+   {
+   double min = cout_total(n, k, t, 0, 0); // correspond a p=1
+   for(size_t p = 0; p != t / 2; ++p)
+      {
+      double lwf = best_wf(n, k + 1, t, p);
+      if(lwf < 0)
+         break;
+
+      min = std::min(min, lwf);
+      }
+
+   return min;
+   }
+
+}
diff --git a/src/lib/pubkey/workfactor.cpp b/src/lib/pubkey/workfactor.cpp
index 972d03af9..5665c5269 100644
--- a/src/lib/pubkey/workfactor.cpp
+++ b/src/lib/pubkey/workfactor.cpp
@@ -11,11 +11,6 @@
 
 namespace Botan {
 
-size_t mceliece_work_factor(size_t code_size, size_t t)
-   {
-   return 0;
-   }
-
 size_t ecp_work_factor(size_t bits)
    {
    return bits / 2;
diff --git a/src/lib/pubkey/workfactor.h b/src/lib/pubkey/workfactor.h
index 37f487234..ba81d61b4 100644
--- a/src/lib/pubkey/workfactor.h
+++ b/src/lib/pubkey/workfactor.h
@@ -26,12 +26,6 @@ size_t dl_work_factor(size_t prime_group_size);
 */
 size_t ecp_work_factor(size_t prime_group_size);
 
-/**
-* Estimate work factor for McEliece
-* @return estimated security level for this group
-*/
-size_t mceliece_work_factor(size_t code_size, size_t t);
-
 }
 
 #endif