Beneh-Goh-Nissim (BGN)

One of the most significant steps toward an FHE scheme was introduced by Boneh-Goh-Nissim (BGN) in [Boneh et al. 2005]. BGN evaluates 2-DNF5 formulas on ciphertext and it supports an arbitrary number of additions and one multiplication by keeping the ciphertext size constant. The hardness of the scheme is based on the subgroup decision problem. Subgroup decision problem simply decides whether an element is a member of a subgroup Gp of group G of Composite order n = pq, where p and q are distinct primes.