Introduction

This library provides an implementation of the [GGH96] algorithm for public-key encryption, due to S. Tzvetkov. For a description of the algorithm read the paper by O. Goldreich, S. Goldwasser, and S. Halevi.

Contents:

Introduction
Download
Description
Loading files in Matlab
Class reference
Notes
Download

To download the LiDIA package go to http://www.informatih.th-darmstadt.de/TI/LiDIA/. Read the instructions for installation.
To download the library choose one of the archive files:
- Key.tgz
- Key.zip
Files in the archive:
- Key.h - class definitions
- Key.cpp - class implementations
- Invert.cpp - gaussian elimination; included by Key.cpp
Description

There are two classes defined in Key.h, private_key and public_key. To generate a new pair of keys, use private_key::generate(int dim,int lll=0,int inv=0). dim is the size of the lattice basis. If lll is nonzero, the transforamation matrix is reduced using the LLL algorithm; this works for dimentions up to approximately 200. If inv is nonzero then LiDIA's built-in, although still undocumented, matrix inversion function is used (bigfloat_matrix::invert), which is slower, but supposedly more reliable than our function (a simple Gaussian elimination).
The data for the public key is contained in the private key. All you need to do to initialize a public key is to call private_key::make_public(public_key &pubkey).
Of course, the public key can be initialized without knowing the private key. The stream I/O operators << and >> are predefined for both of the classes. There are two output formats - plain and matlab. To change the output format use get_print_format and set_print_format. Only the plain format is supported for input.
There are instructions on how to load the generated data in Matlab.
Basic encryption/decryption of lattice vector is implemented in public_key::encrypt and private_key::decrypt. To encrypt a message, a bit-string b[i], there are two algorithms:
- embedding the message in the error vector
  v[i]=random(-128..127)
  e[i]=random(-3,2) if b[i]=0 and random(-2,3) if b[i]=1
- embedding the message in the lattice vector
  v[i]=random_even(-128..126) if b[i]=0 and random_odd(-127..127) if b[i]=1
  e[i]=random(-3,-2,2,3)
To set the algorithm use get_method and set_method.
Here is a sample program that uses the library:
```
#include "Key.h"


private_key privkey;
public_key pubkey;

main() {
  privkey.generate(100);         // generate private key

  ofstream fout("key.100");
  fout << privkey;               // write private key to file
  fout.close();

  privkey.make_public(pubkey);   // initialize public key

  int_vector b(100,100,FIXED);   // int_vector defined in Key.h
  for (int i=0; i<100; i++)
    b[i] = rand()&1;             // a random message

  bigint_vector c(100,100,FIXED); // also defined in Key.h
  pubkey.set_method(1);
  c = pubkey.encrypt_bitstr(b);   // encrypt message

  int_vector d(100,100,FIXED);
  privkey.set_method(pubkey.get_method());
  d = privkey.decrypt_bitstr(c);  // decrypt message

  if (!b.equal(d))                // compare with the original
    cerr << "Ooops!" << endl;
}
```
A typical makefile for building such a program is given bellow: (lib and include here are assumed to be links to the corresponding LiDIA directories)
```
myprog:	myprog.cpp Key.o
	g++ -o myprog myprog.cpp Key.o -Llib/ -Iinclude/ -lm -lLiDIA
Key.o:	Key.cpp Key.h Invert.cpp
	g++ -c -o Key.o Key.cpp -Iinclude/
```
Loading files in Matlab

Because Matlab cannot read .m files with more than 255 characters per row, we have to use .mat files. The following example shows how to read a private key in Matlab (in this case dim=100):
```
load A.mat -ascii
Rinv = A(1:100,:);
T = A(101:200,:);
B = A(201:300,:);
```
Class reference
Class private_key:
```
int get_method(void);
void set_method(int m);
```
If m=1 the message is embedded in the error vector, and if m=2 then it is in the lattice vector.
```
int get_print_format(void);
void set_print_format(int f);
```
If f=1 the format is plain, if f=2 it is matlab. (The only difference is that the plain format starts with a line containing the dimention.)
```
void generate(int dim, int lll=0, int inv=0);
```
Generate a private key.
If lll!=0 then the transformation matrix is reduced by LiDIA's LLL algorithm.
If inv!=0 then LiDIA's bigfloat_matrix::invert is used instead of our inversion.
```
void make_public(public_key &pubkey);
```
Copy the public key.
```
int get_dim(void);
```
Returns the dimention of the private key.
```
bigint_vector decrypt(bigint_vector c);
```
Decrypt c. Basically this computes T*round(Rinv*c)
```
int_vector decrypt_bitstr(bigint_vector c);
```
Decrypt a bit-string message.
```
friend istream & operator >> (istream & in, private_key & privkey);
friend ostream & operator << (ostream & out, const private_key & privkey);
```
Stream I/O.
Class public_key:
```
int get_method(void);
void set_method(int m);
```
If m=1 the message is embedded in the error vector, and if m=2 then it is in the lattice vector.
```
int get_print_format(void);
void set_print_format(int f);
```
If f=1 the format is plain, if f=2 it is matlab. (The only difference is that the plain format starts with a line containing the dimention.)
```
int get_dim(void);
```
Returns the dimention of the private key.
```
bigint_vector encrypt(bigint_vector v,bigint_vector e);
```
Compute B*v+e.
```
bigint_vector encrypt_bitstr(int_vector b);
```
Encrypt the bit-string message b using the current method.
```
friend istream & operator >> (istream & in, public_key & pubkey);
friend ostream & operator << (ostream & out, const public_key & pubkey);
```
Stream I/O.
Notes

There are several problems that appear when working with higher dimentions. For example, if you use LLL to reduce the transformation matrix, usually before dimention 200 it stops working (sleeps forever). If you don't use LLL, the entries in the transformation matrix get big--about 9-10 digits for dim=100 and 19-20 digits for dim=200. The larger digits in the private and the public key make the encryption and decryption a little bit slower (about 10-12%).
The key generation usually takes a while. On a Pentium-133 with 32MB RAM, running Linux we got the following running times (measured in seconds):
```
dim =      50    60    70    80    90   100   110   120   130   140   150   160   170   180
-------------------------------------------------------------------------------------------
w/ LLL:    66   151   360   734  1242  1999  3123  4818  6816 11693 15657 21581 28025 32156
w/out LLL: 17    29    46    68    98   136   182   235   303   376   465   556   687   835
```
As we said above, if you don't use LLL, the entries in the transformation matrix T get large. Since we store T as a bigint_matrix, we don't have a problem with storing the matrix itself. However, T is computed as an inverse of T^-1 using Gaussian elimination. The process of inversion requires higher precision and floating point matrix as a buffer. We use bigfloat numbers which have the default precision of 20 decimal digits. This is enough up to about dim=160. You'll have to increase the precision for higher dimentions. This could be done using the bigfloat::set_precision(p) function. For example:
```
...
int main(int argc, char **argv) {
  bigfloat::set_precision(50);
  private_key privkey;
  public_key pubkey;

  privkey.generate(200);
...
```
Another problem is due to the great amount of memory used. More precisely if you free the memory used for a key, you are not guaranteed that you will be able to use it for anouther one. (I.e., there is memory fragmentation.) We suspect that LiDIA has problems in dealing with very large matrices.

Introduction

Download

Description

Loading files in Matlab

Class reference

Notes