CKKS Mitigation 2

Mitigation for the CKKS vulnerability recently [observed](https://eprint.iacr.org/2020/1533.pdf) by Li and Micciancio Co-authored-by: Shai Halevi <shaih@alum.mit.edu> Co-authored-by: Flavio Bergamaschi <anadyomeni@gmx.com>
homenc · Dec 9, 2020 · fb6a647 · fb6a647
1 parent 8a10d52
commit fb6a647
Show file tree

Hide file tree

Showing 9 changed files with 91 additions and 23 deletions.
diff --git a/CHANGES.md b/CHANGES.md
@@ -1,3 +1,13 @@
+HElib 1.3.0, December 2020
+=========================
+(tagged as v1.3.0)
+
+November-December 2020
+---------------------
+* Mitigation for the CKKS vulnerability recently [observed](https://eprint.iacr.org/2020/1533.pdf) by Li and Micciancio
+* Context Builder unsing builder pattern
+* HElib now requires C++17
+
 HElib 1.2.0, November 2020
 =========================
 (tagged as v1.2.0)

diff --git a/CKKS-security.md b/CKKS-security.md
@@ -0,0 +1,57 @@
+# Security of Approximate-Numbers Homomorphic Encryption
+
+Security of standard (not homomorphic) encryption scheme is fairly well understood nowadays, and it usually comes in two flavors: An encryption scheme may only resists passive attackers (that can view encrypted data but not manipulate it), or it can also resist active attackers that can manipulate the encrypted data and then observe how it is decrypted.
+The crypto lingo for the weaker (passive) notion is [CPA-security](https://en.wikipedia.org/wiki/Chosen-plaintext_attack), while the stronger is called [CCA-security](https://en.wikipedia.org/wiki/Chosen-ciphertext_attack). (These acronyms stand for chosen-plaintext-attacks and chosen-ciphertext-attacks, respectively.)
+It is well understood that to protect data at rest or in transit, one must use CCA-secure encryption. CPA-security may suffice when the encryption is used as one component in a larger system, and protection against active attackers is provided by other components in that system.
+
+For homomorphic encryption (HE) schemes, it is well known that they inherently cannot be CCA secure. One consequence of their non-CCA-security is that the system must ensure that decryption is never applied to invalid ciphertexts. Indeed, with contemporary HE schemes, allowing the attacker to submit invalid ciphertexts to be decrypted would typically result in exposure of the secret key. In HElib, a ciphertext is *valid* if it was produced using the library's encryption and evaluation routines and does not contain too much noise. (In particular, decryption should not print a warning about "decrypting with too much noise".) It is thus a commonly accepted practice for HE schemes to make do with CPA security, and rely on the system around the HE to provide the extra protection that may be needed.
+
+Recently, Li and Micciancio [observed](https://eprint.iacr.org/2020/1533.pdf) that for *approximate-number* HE schemes, the common notion of CPA security is not enough even against passive attackers. The crucial difference is that since the scheme itself adds some error, the attacker may learn something from the decryption result *even if it knows what the decrypted result was supposed to be*. Specifically, it learns the error, which may leak information about the secret key. Li and Micciancio described simple attacks on the CKKS approximate-numbers scheme that expose the secret key after seeing a small number of decryption results (sometimes as few as a single decryption).
+
+## Mitigating the Li-Micciancio attacks
+
+In response to this observation, HElib now includes some countermeasures to mitigate this risk to some extent. In particular, the HElib decryption routine for CKKS was modified to add some key-independent noise, masking the key-dependent noise and making the Li-Micciancio attacks harder to mount. This extra noise, however, reduce the accuracy of the decrypted result. Applications that use CKKS need to walk a fine line, balancing security, accuracy, and performance. Below we describe a framework for developing CCKS-based applications while talking these aspect into account.
+
+1. Start by identifying the (class of) processes that the application needs to apply to the data;
+2. Identify the *required precision* from the processed results;
+3. Run these processes in HElib on some test data to determine the parameters to be used, roughly as follows:
+   1. Find some parameter setting where `context.securityLevel()` returns high enough security and the library does not report decryption errors;
+   2. Experimentally find some fairly tight bound on the noise magnitude of the decrypted results, when called with the accuracy parameter from Step 2. This can be done by running HElib processing many times and comparing the decrypted results to what you get when applying the same processing to plaintext data;
+   3. Compare the noise bounds that you get from Step 3.2 above with the estimated error that HElib computes just prior to decryption, which can be accessed via `ctxt.errorBound()`. If the experimental noise is significantly smaller than what `ctxt.errorBound()` returns then use `ctxt.bumpNoiseBound()` prior to decryption to force HElib to use the tighter error estimate.
+   4. Repeat Steps 3.1-3.3, increasing the parameters until decryption no longer emits a warning about the added noise being too small.
+
+   We now elaborate more on each of these steps.
+
+### Steps 1-2, Processes and Required Precision
+
+As with any application of HE, the starting point is ensuring adequate functionality. The developers must therefore determine the operations to be computed and the *output precision* which is required. Some applications only need to compute a single function while others need to handle a wider class of functions, but at the very least the developers should determine the maximum depth of supported circuits and the maximum precision required.
+
+In HElib, the user gets to specify the *input precision* for encrypting plaintext data, and each level in the circuit reduces the precision by one (or upto 1.5) bits, namely the error roughly doubles for each level. For example using the helper class `PtxtArray` one could call `ptxt.encrypt(ctxt, ptxtMagnitude, precision)`,<sup>[1](#optPrecision)</sup> which would result in encryption of the given input plaintext with error bounded by 2<sup>-precision</sup>.
+After evaluating a depth-three circuit (say), the error will grow to a little more than 2<sup>3-precision</sup>. An application requiring *p* bits of output precision after the evaluation of a depth-*d* circuit should then encrypt with input precision somewhere between *p+d* and *p+3d/2*.
+
+### Step 3, Finding Matching Parameters
+
+After determining the required depth *d* and output precision *p*, the application developers need to find some parameters that yield this output precision while ensuring security. This typically involves an iterative trial-and-error procedure, as follows:
+
+1. Begin with some rough estimate of the parameters: The total bitlength of the modulus needed for a depth-*d* circuit is typically something like *22(d+1)*, and the ring dimension needed to get 128-bit security with this modulus is around *750(d+1)* (rounded up to a power of two, since the current CKKS support in HElib was only tested with power-of-two rings).
+
+   Denote by *m* the next power of two larger than *750(d+1)*, then these initial parameters can be set in HElib by using the `ContextBuilder` class, setting
+   ```
+     Context context =
+         ContextBuilder<CKKS>().m(m).bits(16*(d+1)).precision(p+d).c(3).build();
+   ```
+   Note that the number of bits specified above is only *16(d+1)* rather than *22(d+1)*, and there is a mysterious additional parameter *c=3* satisfying *(c+1)/c ~ 22/16*. The quantity *bits=16(d+1)* is an estimate for what's needed for a depth-*d* circuit, and the total modulus bitsize in HElib is obtained roughly as *bits&middot;(c+1)/c*. (See discussion of *ciphertext vs. special primes* in the [HElib document](https://eprint.iacr.org/2020/1481), section 5.1. One can get slightly smaller total bitsize for the same functionality by increasing the *c* parameter from its default value of *c=3*, but the keysize and running time grow almost linearly with *c*.
+
+   After setting these parameters, run HElib processing and check if the library complains about possible decryption errors, and use these experiments to increase or decrease the *bits* and *m* parameters. You should also use the interface `context.securityLevel()` to check that this combination of parameters *m,bits,precision* and *c* yields an acceptable level of security.
+
+2. Check that these parameters indeed yield the required output precision. Namely run several experiments of HElib processing, decrypting the result with the optional precision argument (e.g., using the interface `ptxt.decrypt(ctxt, secretKey, p)` of the `ptxtArray` class), and comparing the outcome with the result of plaintext processing. (At this point you should ignore any warning from HEib about the added noise being too small.) Revisit the parameters from Step 1 above until both security and output precision are acceptable.
+
+3. Next, check the error bound that HElib reports via `ctxt.errorBound()` just prior to decryption, to the actual error that was observed in the previous step (which presumably is no more than *2<sup>-p</sup>*). If the HElib estimate is significantly larger than the actual noise, then use `ctxt.bumpNoiseBound()` prior to decryption to force HElib to use the "right estimate".
+
+4. At this point, you need to check that HElib no longer prints a warning message on decryption about the added noise being too small. If you still see that warning, then you need to revisit the parameter setting, increasing the *bits* parameter (and other parameters as needed to maintain security and precision), until this warning is no longer displayed.
+
+As a final comment, we remark that this procedure is only adequate for cases where the threat model include the adversary only getting access to a handful of decryption results. If the total amount of information available to the adversary about decryption queries is much larger, then the application needs to increase the *bits* parameter from above. In particular, to withstand an attack that has access to the results from decryption of *D* ciphertexts, the *bits* parameter should be increased roughly by a factor of *<math><msqrt><mi>D</mi></msqrt></math>*, and the input-precision parameter should similarly be increased to *<math><msqrt><mi>D</mi></msqrt>(p+d)</math>*.
+
+---------------------------------------
+<a name="optPrecision"><sup>1</sup></a>
+The `ptxtMagnitude`, and `precision` arguments are optional, with defaults that depend on the context and the actual plaintext to be encrypted. Importantly, the precision (if specified) indicates an absolute number, it is *not* a fraction of the plaintext magnitude. For example calling with `ptxtMagnitude=16`, and `precision=3` would still result in an error of magnitude 1/8. Finally note that the `precision` arguments can also be negative, indicating error magnitude larger than one.
diff --git a/README.md b/README.md
@@ -12,6 +12,9 @@ the [Smart-Vercauteren][2] ciphertext packing techniques and
 the [Gentry-Halevi-Smart][3] optimizations. See [this report][7] for a
 description of a few of the algorithms using in this library. 
 
+Please refer to [CKKS-security.md](CKKS-security.md) for the latest 
+discussion on the security of the the CKKS scheme implementation in HElib.
+
 Since mid-2018 HElib has been under extensive refactoring for *Reliability*, 
 *Robustness & Serviceability*, *Performance*, and most importantly *Usability* 
 for researchers and developers working on HE and its uses.

diff --git a/include/helib/Context.h b/include/helib/Context.h
@@ -36,7 +36,7 @@ constexpr int BOOT_DFLT_SK_HWT = MIN_SK_HWT;
  * @brief An estimate for the security-level. This has a lower bound of 0.
  * @param n LWE dimension.
  * @param log2AlphaInv Variable containing the value of `log(1/alpha)` where
- * `alpha` is the noise.
+ * `alpha` is the noise/modulus ratio.
  * @param hwt The Hamming weight.
  * @return The estimated security level.
  * @note This function uses experimental affine approximations to the

diff --git a/src/Ctxt.cpp b/src/Ctxt.cpp
@@ -2883,15 +2883,6 @@ void Ctxt::addNoiseForCKKSDecryption(const SecKey& sk, double eps)
   } else
     sigma = sigma_target;
 
-#ifdef HELIB_DEBUG
-
-  if (sigma / sigma_min < 1000) {
-    Warning("CKKS decryption: sigma/sigma_min = " +
-            std::to_string(convert<double>(sigma / sigma_min)));
-  }
-
-#endif
-
   // std::cerr << "***** " << (sigma/sigma_min) << "\n";
 
   NTL::xdouble addedNoiseBound = sigma * B;

diff --git a/src/EaCx.cpp b/src/EaCx.cpp
@@ -111,20 +111,20 @@ void EncryptedArrayCx::decrypt(const Ctxt& ctxt,
   // the scaled error increases by at most eps (with some
   // futher adjustments made in addNoiseForCKKSDecryption
   // to maintain a certain level of security as the cost
-  // of accuracy.
+  // of accuracy).
 
-  long r = alMod.getR(); // default r-value
-  if (prec.isDefined())
-    r = prec; // override if necessary
 
-  double eps = std::ldexp(1.0, -r);
+  double eps = ctxt.errorBound();
+  if (prec.isDefined()) {
+    double eps1 = std::ldexp(1.0, -prec); // eps = 2^{-r}
+    if (eps1 < eps) Warning("CKKS decryption: 2^{-prec} < ctxt.errorBound(): "
+                            "potential security risk");
+    eps = eps1;
+  }
 
   // now add noise to a copy of ctxt
   Ctxt ctxt1 = ctxt;
 
-  // This will help protect accuracy while allowing us to add a lot of noise
-  ctxt1.bringToSet(ctxt1.getContext().fullPrimes());
-
   ctxt1.addNoiseForCKKSDecryption(sKey, eps);
 
   // finally, perform the decryption

diff --git a/src/keys.cpp b/src/keys.cpp
@@ -1321,8 +1321,14 @@ void SecKey::Decrypt(NTL::ZZX& plaintxt,
   double bnd = getContext().zMStar.getPolyNormBnd();
 #endif
 
-  if (ciphertxt.totalNoiseBound() * bnd > 0.48 * xQ)
-    Warning("decrypting with too much noise");
+  if (ciphertxt.totalNoiseBound() * bnd > 0.48 * xQ) { 
+    std::string message = "Decrypting with too much noise";
+#ifdef HELIB_DEBUG
+    Warning(message);
+#else
+    throw LogicError(message);
+#endif
+  }
 
   const IndexSet& ptxtPrimes = ciphertxt.primeSet;
 

diff --git a/tests/GTestApproxNums.cpp b/tests/GTestApproxNums.cpp
@@ -740,12 +740,12 @@ INSTANTIATE_TEST_SUITE_P(typicalParameters,
                              // SLOW
                              Parameters(/*R=*/1,
                                         /*m=*/1024,
-                                        /*r=*/8,
+                                        /*r=*/10,
                                         /*L=*/150,
                                         /*epsilon=*/0.01,
                                         /*seed=*/0)
                              // FAST
-                             // Parameters(1, 128, 8, 150, 0.01, 0)
+                             // Parameters(1, 128,10, 150, 0.01, 0)
                              ));
 // if (R<=0) R=1;
 // if (R<=2)

diff --git a/tests/TestPermutations.cpp b/tests/TestPermutations.cpp
@@ -271,6 +271,7 @@ TEST_P(TestPermutationsCKKS, ciphertextPermutationsWithNewAPI)
   helib::PtxtArray w(context);
   w.decrypt(ctxt, secretKey);
 
+  //TODO-FB investigate the use of EXPECT_NEAR with an error threshold
   EXPECT_TRUE(w == helib::Approx(v));
 }
 
@@ -322,7 +323,7 @@ INSTANTIATE_TEST_SUITE_P(variousParameters,
 INSTANTIATE_TEST_SUITE_P(variousParameters,
                          TestPermutationsCKKS,
                          ::testing::Values(CKKSParameters(/*m=*/8192,
-                                                          /*r=*/20,
+                                                          /*r=*/50,
                                                           /*bits=*/1000,
                                                           /*depth=*/5)));