gentry lee fhe library

implementation of "fully homomorphic encryption for matrix arithmetic" by craig gentry and yongwoo lee.

implementation status

completed: client-side operations

the following components from the paper have been implemented:

section 2.2-2.3: basic rlwe encryption

• polynomial operations over z_q[x]/(x^n+1)
• rlwe encryption and decryption
• key generation, gadget decomposition, relinearization

section 3.1: matrix encoding

• encoding/decoding of batched matrices into polynomials
• vandermonde matrix-based transformations
• support for complex matrix encoding

section 3.2: encryption over extended ring

• gaussian integer operations z_q[i]
• 3d polynomial operations over r'_q = z_q[i][x,y,w]
• rlwe encryption/decryption for encoded matrices
• secret key generation in r_q

remaining: cloud-side operations

the following homomorphic operations need to be implemented:

section 3.4: homomorphic matrix multiplication

• trace operation for encrypted matrix multiplication
• reduction to plaintext matrix multiplications

section 3.5: relinearization for matrix multiplication

• key switching for matrix products
• relinearization keys for r'_q

section 3.6: other homomorphic operations

• matrix addition
• hadamard multiplication
• transposition (conjugate and standard)
• intra-matrix rotations (rows/columns)
• inter-matrix rotations

library structure

lib/
├── include/
│   ├── poly.h           - basic polynomial operations
│   ├── rlwe.h           - rlwe encryption (standard)
│   ├── fhe.h            - fhe operations (standard)
│   ├── encoding.h       - matrix encoding (section 3.1)
│   ├── gauss_int.h      - gaussian integers
│   ├── poly_3d.h        - 3d polynomials r'_q
│   ├── rlwe_3d.h        - rlwe over r'_q (section 3.2)
│   └── gentry_lee_fhe.h - main header
└── src/
    └── [implementations]

building

cd lib
make

produces bin/libgentry_lee_fhe.a

parameters

standard rlwe

• n = 256
• q = 12289
• gadget_base = 32
• gadget_digits = 4

matrix encoding

• n_matrix = 4 (matrix dimension)
• p_batch = 5 (batch parameter)
• phi_p_batch = 4 (number of matrices)
• delta_encoding = 64.0

3d encryption

• n_poly3d = 4
• p_poly3d = 3
• phi_p_poly3d = 2
• q_gauss = 65537

usage

#include "gentry_lee_fhe.h"

// encoding
encoding_basis basis = init_basis();
batch_matrix matrices = ...;
poly_3d encoded = encode(matrices, basis);

// encryption
poly_3d secret_key = gen_secret_key();
ciphertext_3d ct = encrypt_3d(encoded, secret_key);

// decryption
poly_3d decrypted = decrypt_3d(ct, secret_key);
batch_matrix result = decode(decrypted, basis);