Equality-check Circuit FHE from LWE

Given an encryption of a message  a circuit  and any field element one can homomorphically compute the function

on the ciphertext. Here, we take advantage of the fact that the FHE homomorphic operations can support scalar multiplication by a field element without increasing the noise too much.

Fix a security parameter  and depth bound  Let  be LWE parameters where  is a  -bounded error distribution and  Then, there is an FHE scheme  for circuits of depth bound , with the following properties:

• HE.KeyGen outputs a secret key 
• HE.Enc takes in a message  and outputs a ciphertext  where .
• HE.Eval takes in a circuit  and a ciphertext  and outputs ciphertexts 
• For any boolean circuit  of depth  and scalar element  HE.Eval  is computed by a boolean circuit of depth 
• HE.Dec on input  and , when  we have that

When  we have

for some bound 

• Security relies on 

• Correctness. We require that for all  KeyGen  and boolean circuits  of depth at most , we have that

where the probability is taken over HE.Enc and HE.KeyGen.

• Security. For security, we require standard semantic security. For any PPT adversary  and for all  there exists a negligible function negl such that

We will encrypt the punctured point  and homomorphically compute the equality predicate  on the ciphertext such that it decrypts to a random element  only if the evaluation of the PRF a point  equals to the punctured point. This is simply evaluating the equality check circuit on the FHE ciphertext and scaling the result by .