Guide to HElib (#1)

Shai Halevi has released an implementation of the BGV cryptosystem over on github. I know a lot of people (myself include) have been wanting to play with FHE to get a better understanding of it. A while back I started a sage implementation of BGV (which I have never released). That helped a lot in understanding BGV. If anyone is interested in the very beta version of my sage code, let me know.

Given that HElib has now been released, I wanted to start playing with it and release my notes. So, here goes. In post #1 I will go over installation and playing with some of the test programs that come with HElib.

Install (Compilation)

Installation/compilation of HElib is quite easy if you get things right. First of all you will need NTL (number theory library). I tried using the default version of NTL for my version of Ubuntu, but HElib wouldn’t compile. So, get the newest version 6.0.0. Compile and install (./configure; make; make check; make install).

Then head over to github and clone the git repository (git clone https://github.com/shaih/HElib.git). Compilation of HElib is pretty easy (cd HElib/src; make). This will build a library against which you can statically compile your own code which can use HElib. There are, however, also some test programs you might be interested in (named Test_*). To compile these do (make test).

Test_General

Within Test_General.cpp we can learn a lot about HElib and how to use it in code. First off is the main function. There are a lot of parameters. Running (./Test_General_x –help) explains what these parameters are (to some degree). I’ll go in more detail on some of them here. The parameters are:

R is the number of rounds
p is the plaintext base [default=2]
r is the lifting [default=1]
d is the degree of the field extension [default==1]
(d == 0 => factors[0] defined the extension)
c is number of columns in the key-switching matrices [default=2]
k is the security parameter [default=80]
L is the # of primes in the modulus chain [default=4*R]
s is the minimum number of slots [default=4]
m is a specific modulus

R is the number of rounds of testing (basically a parameter to a for loop around the testing). p is the plaintext base. Basically this is the plaintext space. Setting p=2 basically says that plaintexts are in {0,1}. p should be a prime number. d as it says is the degree of the field extension. GHS12 explains (section 2.3) what this is:

We note that the values in the plaintext slots are not just bits, rather they are polynomials modulo the irreducible F_j’s, so they can be used to represents elements in extension fields GF(2^d).

k as said, is the security parameter. A default of 80 is 80 bits of security. The length of the modulus chain, L, allowes for “leveled” FHE. L reduces or eliminates the amount of bootstrapping (see BGV11). Finally, s tells how many (at a minimum) number of plaintext slots you’d like. Set this too high and it will complain.

The basic parameters given in the file are pretty good for testing. Take a look at the GHS12 paper for more on parameter tuning. In that paper they look specifically at tuning BGV for AES.