Outsourcing computation, privately

image-20220919154446784

Homomorphic evaluation function:

Eval: f, Enc(x) -> Enc(f(x))

Fully homomorphic encryption

image-20220919154723892

Fully homomorphic = correctness for any efficient f = correctness for universal set

Approximate eigenvector method

image-20220919160158938

基于GSW13的特征向量的构造，我们可以在ciphertext上计算加法和乘法，然后可以通过secret key恢复出message的计算结果。但是这个方法不安全，因为特征向量很容易被找到。

idea：使用approximate eigenvectors，在secret key右乘cipher text

image-20220919160511119

image-20220919162526756

image-20220919162834463

Learning with errors (LWE) R05

image-20220919190114289

Rearranging notation

image-20220919190916495

basic idea: ** we have a matrix A, we can generate a matrix s, such that sA=$\eta$**

image-20220919191541347

Encryption scheme from LWE

Encryption

image-20220919191851050

Decryption

image-20220919192128171

it can be generalized to matrices.

On matrices

image-20220919192253181

Ref

https://www.youtube.com/watch?v=O8IvJAIvGJo