Guide to HElib (#3)

June 19, 2013 45 comments

To demonstrate HElib and to be able to better play with some of the settings, I’ve written a simple application which implements a RPN calculator. You can grab a copy of it on the thep downloads page. You’ll have to modify Makefile to point the HElib variable to the proper directory. Compile by typing make and run it by typing ./HEcalc. You’ll then be able to do things like:

3

4

*

q

at which point it should return 12.

This is a very preliminary version of HEcalc. I haven’t done anything with ciphertext packing, etc. The purpose of this code is to demonstrate how to add, subtract, and multiply encrypted numbers (along with how to encrypt, decrypt, etc). Play with it some. You’ll notice that by changing the value of L you’ll be able to do more multiplications without the error becoming too great to properly decrypt. You can do as many additions as you want (basically) as the error grows very slowly with additions. Another thing you’ll see when playing with this is that when you decrypt a value, you actually get a number of copies of that value. This is due to ciphertext packing (i.e., storing many values in the same ciphertext). This allows you to do SIMD operations. I hope to detail ciphertext packing and SIMD in the next post. Until then, feel free to use the comments to ask questions about HEcalc and I’ll answer as best as I can.

Guide to HElib (#2)

May 29, 2013 10 comments

Setting up the Context

HElib requires that you setup a context using the FHEcontext class to get things going. This stores all the parameters, etc needed for other tasks you will want to perform (key generation, encryption, decryption, homomorphic operations). I’ve been doing this in my code as follows:

#include 
long p=101;
long r=1;
long L=4;
long c=2;
long k=80;
long s=0;
long d=0;
long w=64;
long m = FindM(k, L, c, p, d, s, 0);

FHEcontext context(m,p,r);

I explained the parameters in my last post so I won’t go into much detail. The FindM function is something new. I’m not going to go into the details of it (as I’m still trying to understand it all), but basically it will find a valid value for m given the specified values. In addition to setting up the context, we also need to build the modulus chain (this is what recent versions of BGV use to avoid bootstrapping). We also need a value G which is the monic polynomial used in constructing the ring BGV works in:

buildModChain(context, L, c);
G = context.alMod.getFactorsOverZZ()[0];

Key Generation

Once you have all this setup, generating public and private keys in HElib is pretty easy:

FHESecKey secretKey(context);
const FHEPubKey& publicKey = secretKey;
secretKey.GenSecKey(w);

The value w is the hamming weight to use in key generation (see appendix B of GHS12 for an explanation).

Encryption and Decryption

Now that we have the key pair established, we can encrypt and decrypt. HElib uses the EncryptedArray class for data movement, so make sure you #include <EncryptedArray.h>.  Then create an encrypted array as:

EncryptedArray ea(context, G);

We then use a PlaintextArray to represent a plaintext. The documentation shows all the various ways this can be done. I’m going to show a simple (yet inefficient) way to encrypt a single value:

Ctxt c(publicKey);
PlaintextArray p(ea);
p.encode(5);
ea.encrypt(c, publicKey, p);

This will encrypt the number 5 and store it in c. Decryption is very simple too:

PlaintextArray p_decrypted(ea);
ea.decrypt(c, secretKey, p_decrypted);

SIMD

The reason for using a PlaintextArray is that BGV supports what is being called SIMD (single-instruction, multiple-data) operations. To understand this, consider a simple example. Say we have 20 pairs of numbers (a1,b1) to (a20, b20) and we want to multiply each pair together to get c1…c20. Clearly this can be done by computing (a1*b1), (a2*b2), and so on. BGV, however, will allow us to store all a1…a20 in a single ciphertext (say a) and all b1…b20 in a single ciphertext (say b). Then we only need to compute c=a*b. When we decrypt c we can access c1…c20. Thus a single multiplication can actually multiply many values at once.

Homomorphic Operations

The ciphertext values are stored in instances of Ctxt. Take a look at that class’s documentation to see the supported operations. The most basic are overloads of operator+=operator-=, and operator*=. Using those you can operate on the ciphertexts to compute functions. You should be able to do as many additions and subtractions as you want. If, however, you do too many multiplications on the same ciphertext value, the ciphertext becomes too noisy to decrypt. More on that in the next post.

Analysis of XKCD’s Hash Competition

May 10, 2013 Leave a comment

There was a question over on Crypto.SE on “almost” collisions as related to XKCD’s hash breaking competition. I had a few minutes to write-up some analysis. Pretty cool question that I too had wondered about but never worked out the math.

Categories: Cryptography

Guide to HElib (#1)

May 3, 2013 28 comments

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.

CipherCloud DMCA

April 20, 2013 1 comment

Something interesting is happening over at Crypto.SE. Someone a while back posted a question about CipherCloud (cached here). Turns out that CipherCloud wasn’t too happy about the analysis and sent a DMCA to StackExchange. The question has been deleted.

This raises a bunch of questions about CipherCloud. The analysis on Crypto.SE looked pretty scary. Especially given that the company has raised $30 Million. I looked over their leadership team, their board of directors, job postings, etc and don’t see a single cryptographer listed. That raises another set of warning flags.

The Analysis
I don’t want to repost the analysis here, but the basic idea was that it seemed to be using a constant mapping from plaintext to ciphertext. Thus the word ‘the’ always mapped to ‘qmf’. Thus, patterns in the ciphertext are recognizable and the security of the system is minimal. This analysis was all done on screenshots/videos of the product. It could be that it was just marketing material and does not reflect the actual security of the product. It is hard to tell though as they do not publish the details of their work. They offer a white paper if you give them your personal information (which I may do and post my own analysis here).

Why the big deal?
Why is this such a big deal? Well, cryptography research (and thus practical cryptography) is very hard to do. I’d venture to say that the practical stuff is even harder than the theoretical stuff. If you don’t publish loads of information on your cryptographic protocols, etc, how can anyone know it is secure? There isn’t really a certification group for cryptographic protocols. If you are afraid of losing your IP, you could hire reputable cryptographers to review your product. It doesn’t appear CipherCloud has done any of this. This is why it is a big deal. The security of the system could be imaginary at best. Bruce Schneier once said something to the effect of “anyone can design a cipher that they themselves cannot break”. Same goes with protocols, security systems, etc.

Recommendations
To potential users of CipherCloud, I’d recommend you contact them and tell them you want open evaluations of their products or you won’t be using it. Also tell them sending DMCA notices to StackExchange is very counter-productive. Instead a well reasoned response on Crypto.SE would have been better. Defend your product, don’t try to censor those who are curious about the security.

Secure Use of Biometrics

February 14, 2012 1 comment

I just spend a good deal of time answering a question over on Security.StackExchange and wanted to repost it here.

Fingerprints can be viewed as a fuzzy source of data. Given the same finger, a reader might never read exactly the same print. That is why most readers require the user to scan a finger multiple times during the registration phase.

During the authentication phase, the system tries to determine if the scan it just acquired is “close enough” to the trained data to allow access. This leads to two problems.

  1. Remote authentication
  2. Keeping biometric private

Remote Authentication

Assume I keep my biometric private (we’ll deal with that problem later). Can I give another party enough information to correctly authenticate me without requiring them to store enough information to impersonate me (i.e., if someone steals the database, I don’t want them to be able to impersonate me)?

It turns out you can. The functions needed are called secure sketches and fuzzy extractors. A secure sketch (SS) is given some data (w) and returns string (s) in other words SS(w)=s. A secure sketch also has a recovery function (Rec). Rec takes as input w’ (a noisy copy of w) and s. If w’ is sufficiently close to w (where closeness is measured by some distance metric such as hamming distance), then Rec(w’,s)=w. Now the server and I share a secret value (namely w) which we can each prove knowledge of to authenticate each other (mutual authentication).

The cool thing about this is that even if someone steals s, they won’t be able to impersonate me. There are a few problems with this, however. What if the attacker modifies the copy of s that the server is storing. Could they do that in such a way that w is leaked? In the original work, there were no guarantees that this couldn’t happen. Later research, however, removed this restriction by developing what is called a robust secure sketch, which is secure even in the presence of an active adversary (i.e., an adversarial controlled channel).

Keeping biometric private

The above ideas all assumed that w (and w’) were kept private. This is probably not a good assumption as seen on MythBusters. So, researchers went back to the drawing board and said “Hey what if my fingerprint was my public key” and thus Fuzzy Identity-Based Encryption (FIBE) was born.

Closely related to this is Identity Based Encryption, where my identity (e.g., email address) is my public key. Someone uses my email address to encrypt a message. I then prove to a third party that I own the email address, whereupon I am able to retrieve the corresponding private key and decrypt the encrypted message. It is important to note that the sender only needs some public information from the third party to enable her to encrypt messages to any identity. The receiver must at some point (either before or after the encrypted message is actually sent) retrieve his private key.

FIBE builds upon this idea for fuzzy identities. You read my fingerprint (w), I use w’ to get my private key and as long as w and w’ are close enough, I am able to retrieve the message you send to me (I still have to contact the third party at some time though). An authentication protocol could be built on this so that I need not keep my biometric private.

The major problem with this system (and IBE in general) is the requirement of a third party and the fact that that third party can impersonate me once they have seen a copy of my biometric. The latter problem can be removed by having multiple third parties who all contribute to the process. Thus, no single one can impersonate me. But, then I have to contact multiple people in order to encrypt or decrypt messages.

Application

I’m not sure if any commercial products implement these ideas. So, I cannot speak to commercially available products, but if you are not limited to commercially available products, you could implement these systems yourself and they would probably be pretty secure.

Categories: Cryptography

Cost of Brute-force

November 9, 2011 Leave a comment

Over at crypto.se someone asked a question about the cost in dollars of brute-forcing a 256 bit key. In my answer, I estimated it to be about 8 octodecillion dollar ($8 * 10^57). And that is for the electricity only! Some of the answers were pretty interesting and I learned a few things. For example, I never knew exactly how a quantum computer would affect symmetric-key cryptography. It turns out that it would halve the key space, which is optimal (i.e., you cannot do better). If one could do better with a quantum computer, then that would prove that the key could be brute forced in less than 2^n time. I won’t pretend to understand exactly why that is, but it is a pretty interesting result that I had wondered about for some time.

Categories: Cryptography Tags: , ,
Follow

Get every new post delivered to your Inbox.