Public Challenges for Fully-Homomorphic Encryption

Craig Gentry and Shai Halevi

Update, Oct-2011: The SSSP challenges were solved by Moon Sung Lee from the National Institute for Mathematical Sciences in Korea. The solutions are:
Large: 1925 1299 1920 394 1845 1755 1274 730 295 1359 843 1984 1252 426 114
Medium: 409 450 530 472 76 492 251 360 492 409 462 171 142 304 394
Small: 393 376 208 119 210 383 244 404 66 432 459 483 338 99 119

August 2010

In STOC 2009 Gentry described a construction of a fully-homomorphic encryption scheme, whose security is based on the assumed hardness of some problems related to integer lattices [G09]. The first published attempt at implementing (a variant of) this scheme was described by Smart and Vercauteren in PKC 2010 [SV10]. Smart and Vercauteren implemented the underlying "somewhat homomorphic" scheme, but were not able to implement the bootstrapping functionality that is needed to get the complete scheme to work. Later in 2010, Gentry and Halevi described an implementation of a variant similar to the one from [SV10], were they succeeded in implementing the entire scheme, including the bootstrapping functionality [GH10].

From this page you can download challenges for breaking the Gentry-Halevi implementation. The challenges are offered in three security levels, ranging from "small" challenges (corresponding to lattices in dimension 2048), through "medium" (in dimension 8192) to "large" (in dimension 32768). We also provide on this page a "toy" challenge (in dimension 512), which is provided together with its solution. The "toy" challenge is meant to help people test their attack strategies. In each of the three security levels we offer two challenges:

The main challenge consists of a complete public key of the fully-homomorphic encryption, breaking this challenge would mean that the scheme in that dimension is insecure.
The second challenge is meant to examine specifically the hardness of the sparse-subset-sum problem (SSSP), which is used for "squashing" the decryption procedure. This challenge consists of the public- and secret-keys of the underlying "somewhat homomorphic" scheme, as well as the SSSP instance which is part of the public key of the fully-homomorphic scheme.

Using the notations from [GH10], these SSSP challenges include the key elements d, r, w for the underlying "somehwat homomorphic" scheme, and also all the x_i's that implicitly define the SSSP instances. (Of course, these challenges do not include the circular encryption of the secret key bits, since it could be decrypted using the secret key of the underlying scheme.)

The solution to these challenges consist of the indexes of the elements that are part of the sparse subset-sum, i.e., the SSSP solution. In all the challenges, the sparse subset consists of exactly 15 elements, the challenge is considered "solved" as soon as ten of these indexes are published. Our current guess is that the "small" challenges should be breakable in weeks or months, but the "large" ones take perhaps as much effort to break as factoring RSA-1024.

Download here the code that was used to generate these challenges. This is C++ code, which was written on top of Shoup's NTL library version 5.5.2 (which was slightly modified to support hexadecimal integer I/O).
Click here for the toy challnge (19 MB).
Click here for the main small challnge (76 MB) and the small SSSP challenge (2 MB).
Click here for the main medium challnge (309 MB) and the medium SSSP challenge (8 MB).
Click here for the main large challnge (2.4 GB) and large SSSP challenge (31 MB).

Format

The format of these challenges is defined by the following piece of C++ code, which was used to output them to disk. See more details in the files fhe.h and fhe-utils.cc that are included with the code above. This code is written using Shoup's NTL library version 5.5.2, which was slightly modified to support hexadecimal integer I/O. Specifically the two files ZZ.h and ZZ.c were modified, and they are included with the code above.

class PKblock {
 public:
  ZZ x;         // the sequence of elements is xi = x * R^i mod det
  long idx;     // index of the xi that belongs to the sparse subset
  [...]
};

class FHEkeys {
 public:
  FHEparams prms;   // Parameters
  ZZ det, root, w;  // Public/secret key for underlying "somehwat" scheme
  std::vector<PKblock> pkBlocks;  // The squeash-enabling parts
  vec_ZZ ctxts;     // "compact" encryption of secret-key bits
  [...]
};

void FHEkeys::outputKeys(std::ostream& s, int outIdxs, int outW)
{
 // output all the parameters
  s << prms.secprm;        // unsigned long secprm;
  s << " " << prms.mu;     // double mu;
  s << " " << prms.s;      // unsigned long s;
  s << " " << prms.S;      // unsigned long S;
  s << " " << prms.p;      // unsigned long p;
  s << " " << prms.t;      // unsigned long t;
  s << " " << prms.logn;   // unsigned long logn;
  s << " " << prms.logR;   // unsigned long logR;
  s << " " << prms.noise;  // unsigned long noise;

  // The det, root, and w of the underlying scheme
  s << "\n" << det;        // ZZ det, root, w;
  s << "\n" << root;
  if (outW) s << "\n" << w;

  // The arithmetic progressions
  for (int i=0; i<pkBlocks.size(); i++) { 
    s << "\n" << pkBlocks[i].x;
    if (outIdxs) s << " " << pkBlocks[i].idx;
  }
  // finally the encrypted secret-key bits
  if (outIdxs || !outW) s << "\n" << ctxts;
}

The "main challenges" that include complete public keys were produced by calling keys.outputKeys(cout,0,0), and the SSSP challenges were produced by calling keys.outputKeys(cout,0,1). (The "toy" challenge with the solution was produced by calling keys.outputKeys(cout,1,1).)

The challenges were generated on an IBM System x3500 server, featuring a quad-core Intel Xeon E5450 running at 3GHz, with 12MB L2 cache and 24GB of RAM.

Bibliography

[G09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC 2009, pages 169-178. ACM, 2009.

[GH10] Craig Gentry and Shai Halevi. Implementing Gentry's Fully-Homomorphic Encryption Scheme. Manuscript, 2010.

[SV10] Nigel Smart and Frederik Vercauteren. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In PKC 2010, LNCS volume 6056, pages 420-443. Springer, 2010.