HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
KeySwitch Class Reference

Key-switching matrices. More...

#include <FHE.h>

Public Member Functions

 KeySwitch (long sPow=0, long xPow=0, long fromID=0, long toID=0, long p=0)
 
 KeySwitch (const SKHandle &_fromKey, long fromID=0, long toID=0, long p=0)
 
bool operator== (const KeySwitch &other) const
 
bool operator!= (const KeySwitch &other) const
 
unsigned NumCols () const
 
void verify (FHESecKey &sk)
 A debugging method.
 
void readMatrix (istream &str, const FHEcontext &context)
 Read a key-switching matrix from input.
 

Static Public Member Functions

static const KeySwitchdummy ()
 returns a dummy static matrix with toKeyId == -1
 

Public Attributes

SKHandle fromKey
 
long toKeyID
 
long ptxtSpace
 
vector< DoubleCRTb
 
ZZ prgSeed
 

Detailed Description

Key-switching matrices.

There are basically two approaches for how to do key-switching: either decompose the mod-q ciphertext into bits (or digits) to make it low-norm, or perform the key-switching operation mod Q>>q. The tradeoff is that when decomposing the (coefficients of the) ciphertext into t digits, we need to increase the size of the key-switching matrix by a factor of t (and the running time similarly grows). On the other hand if we do not decompose at all then we need to work modulo Q>q^2, which means that the bitsize of our largest modulus q0 more than doubles (and hence also the parameter m more than doubles). In general if we decompose into digits of size B then we need to work with Q>q*B.)

The part of the spectrum where we expect to find the sweet spot is when we decompose the ciphertext into digits of size B=q0^{1/t} for some small constant t (maybe t=2,3 or so). This means that our largest modulus has to be Q>q0^{1+1/t}, which increases also the parameter m by a factor (1+1/t). It also means that for key-switching in the top levels we would break the ciphertext to t digits, hence the key-switching matrix will have t columns.

A key-switch matrix W[s'->s] converts a ciphertext-part with respect to secret-key polynomial s' into a canonical cipehrtext (i.e. a two-part ciphertext with respect to (1,s)). The matrix W is a 2-by-t matrix of DoubleCRT objects. The bottom row are just (psudo)random elements. Then for column i, if the bottom element is ai then the top element is set as bi = P*Bi*s' + p*ei - s ai mod P*q0, where p is the plaintext space (i.e. 2 or 2^r) and Bi is the product of the digits-sizes corresponding to columns 0...i-1. (For example if we have digit sizes 3,5,7 then B0=1, B1=3, B2=15 and B3=105.) Also, q0 is the product of all the "ciphertext primes" and P is roughly the product of all the special primes. (Actually, if Q is the product of all the special primes then P=Q*(Q^{-1} mod p).)

In this implementation we save some space, by keeping only a PRG seed for generating the pseudo-random elements, rather than the elements themselves.

To convert a cipehrtext part R, we break R into digits R= Bi Ri, then set (q0,q1)^T = Ri * column-i. Note that we have (1,s) (q0,q1) = Ri*(s ai-s ai+p*ei+P*Bi*s') = P * Bi*Ri s' + p Ri ei = P * R s' + p*a-small-element (mod P*q0) where the last element is small since the ei's are small and |Ri|<B. Note that if the ciphertext is encrypted relative to plaintext space p' and then key-switched with matrices W relative to plaintext space p, then we get a mew ciphertxt with noise p'*small+p*small, so it is valid relative to plaintext space GCD(p',p).

The matrix W is defined modulo Q>t*B*sigma*q0 (with sigma a bound on the size of the ei's), and Q is the product of all the small primes in our moduli chain. However, if p is much smaller than B then is is enough to use W mod Qi with Qi a smaller modulus, Q>p*sigma*q0. Also note that if p<Br then we will be using only first r columns of the matrix W.


The documentation for this class was generated from the following files: