Matrix Embeddings

A method to embed circuits into LWE matrices

For the set of public matrix  we encode a vector of field elements  as an LWE sample as

for  where  and  's are sampled according to the standard LWE distribution.

Then, given two encodings, , we can add and multiply them as follows:

Correspondingly, we can define operations on the matrices

Using these operations, one can compute an arithmetic circuit  on the encodings gate-by-gate. In particular, restricting  to be a binary string, we can compute the NAND operation as

where  is a fixed encoding of 

We note that in the description above, to compute a single multiplication on the encodings  one must know one of  or  but it is not required to know both. This means that computing operations such as inner products on two vector attributes can be done without the knowledge of one of the vectors. In particular, given the encodings of  and a pair  where  and  one can derive an encoding of 

Theorem ([BGG+14, GVW15b]). Fix a security parameter  and lattice parameters  where  is a -bounded error distribution. Let  be a depth- Boolean circuit on  input bits. Let   and  such that

for some  There exists the following pair of algorithms

•  On input a circuit  for  and  matrices  outputs a matrix 

•  On input a circuit  for  , vectors  and length  string  outputs a vector 

Such that for  and 

We have that

Moreover,  is a "low-norm" linear function of  That is, there are matrices  such that  and