Fully Homomorphic Encryption over the Integers with Shorter Public Keys I want to implement Homomorphic scheme from the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.

I successfully implemented key generation by taking $\lambda = 2, \beta = 4, \eta = 4$.

But I am not getting the correct bit after decryption. I think there is problem in encrypting the bit and I am not able to understand how this $2$-dimensional array of $x$ produces $\beta^2$ integers in the encryption function:

$$c = m + 2r + 2 \cdot \sum_{1 \le i, j \le \beta} b_{i,j}\cdot x_{i,0}\cdot x_{j,1} \mod x_0$$

This is code for encryption in which I take an array of 2 rows and $\beta$ columns. Here r is a BigInteger representing a random noise with $4\lambda = 8$ bits, m1 is message, x0 and x[][] are public keys. The random vector b1 is $1$.

Here is the code ---

import java.math.BigInteger;  
import java.security.SecureRandom;  
public class Encrypt{  
    public BigInteger encrypt(BigInteger x0,BigInteger[][] x,int m)    
    {  
        SecureRandom rnd=new SecureRandom();  
        BigInteger r=new BigInteger(8,rnd);//noise 4*λ  
        BigInteger two=new BigInteger("2");//constant biginteger of value 2  
        BigInteger c=new BigInteger("0");//ciphertext biginteger  
        BigInteger summation=new BigInteger("0");//summing x[][] values  
        BigInteger b=null,m1=null;//b is random vector and m is message  
        int beta=4;//it is  β=√τ  
        BigInteger sign = BigInteger.valueOf(new SecureRandom().nextInt(2) * 2 - 1);//used to generate random noise between (-2^ρ1,2^ρ1).   
        r=r.multiply(sign).multiply(two); 

        for(int i=0;i&lt;beta;i++)  //2 d array with 2 row and beta columns      
        {      
            for(int j=0;j&lt;beta;j++)    
            {  
                b=new BigInteger(2,rnd);  
                BigInteger b1=BigInteger.ONE;  
                b1=b1.multiply(x[0][i]).multiply(x[1][j]);//x[0][0]*x[1][0]+x[0]  [0]*x[1][1]+x[0][0]*x[2][0]+ and so on  


                summation= summation.add(b1);

            }
        }
        summation=summation.multiply(two);
        m1=m1.valueOf(m);
        c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x

        //System.out.println("c value "+c);
        c=c.mod(x0);//c=c mod x0 
        return c;

    }
}


Any Help Thanks.
If I understood well, you have two issues:


About the $2\beta$ values of $x$ "generating" $\beta^2$ values
About your the bugs in your code.


So, answering (1):   Notice that in the summation (and in your first for loop) for each $x_{i,0}$ you have $\beta$ different values of $x_{1,j}$, which means $\beta^2$ combinations of those $2\beta$ values. You are using the $2\beta$ values you have to perform $\beta^2$ products. Nothing special here.

The point (2) is harder because there are a lot of possible causes to the malfunction of your program. My first guess would be that you are not multiplying $r$ by $2$ in the line

c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x


but it may also be some problem with the intervals each parameter has to belong (are you sure you are respecting them?) or some other restriction imposed on the values. For instance, $x_0$ must be a product of a prime number $p$ with a random odd square free number $q_0$ that does not contain prime factors smaller than $2^\lambda$...

All those restrictions are there to guarantee security or correctness.