Download here thecodethat was used to generate these challenges. This is C++ code, which was written on top ofShoups NTL library(which was slightly modified to support hexadecimal integer I/O).
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
that are included with the code above. This code is written using Shoups NTL library, which was slightly modified to support hexadecimal integer I/O. Specifically the two files
were modified, and they are included with the code above.
Craig Gentry and Shai Halevi.Implementing Gentrys Fully-Homomorphic Encryption Scheme. Manuscript, 2010.
Using the notations from [GH10], these SSSP challenges include the key elements
, LNCS volume 6056, pages 420-443. Springer, 2010.
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.)
, and the SSSP challenges were produced by calling
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 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.
The SSSP challenges were solved by Moon Sung Lee from the National Institute for Mathematical Sciences in Korea. The solutions are:1925 1299 1920 394 1845 1755 1274 730 295 1359 843 1984 1252 426 114409 450 530 472 76 492 251 360 492 409 462 171 142 304 394393 376 208 119 210 383 244 404 66 432 459 483 338 99 119Public Challenges for Fully-Homomorphic EncryptionIn STOC 2009 Gentry described a construction of afully-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:
Click here for thesmall SSSP challenge(2 MB).
Click here for themain toy challenge(19 MB).
The main medium and large challenge are available on a DVD via snail-mail. Pleasecontact usfor details.
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
Click here for thelarge SSSP challenge(31 MB).
Craig Gentry.Fully homomorphic encryption using ideal lattices. In
. (The toy challenge with the solution was produced by calling
Click here for themain small challenge(76 MB)
Click here for themedium SSSP challenge(8 MB).
for the underlying somehwat homomorphic scheme, and also all the
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.
The main challenges that include complete public keys were produced by calling
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
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.
Nigel Smart and Frederik Vercauteren.Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. In