Subgroup decision ⇒ SHE (degree 2)
Statement
If the subgroup decision assumption holds for a composite-order bilinear group generator , the Boneh–Goh–Nissim scheme is IND-CPA-secure and evaluates additions and one multiplication, and so every 2-DNF formula, on ciphertexts of fixed length, for messages in a range with polynomial in , provided the evaluated result also lies in a range of size polynomial in — BGN05. Run on bits, with keeping in , it is a somewhat homomorphic encryption scheme over the ring of degree : a sum of at most products of at most two bits has integer value at most , which recovers by a discrete logarithm in time and reduces modulo — standard.
- : , , , , uniform in the order- subgroup of ; and .
- for and .
- : for the integer value of the evaluated sum, on a fresh encryption of ; is found by a discrete logarithm to the base , in time , and the output is .
- Addition multiplies ciphertexts and rerandomizes by a power of ; multiplication samples a fresh and maps into , where decryption and further additions work the same way with and in place of and .
Sketch
Under subgroup decision, is indistinguishable from a uniform element of , which generates except with negligible probability; then is uniform in and independent of . Raising to removes the -component because , and every cross term of other than is a power of , which has order .
Notes
- Decryption takes time growing with the square root of the plaintext range, so the message space and every evaluated result must be polynomially bounded — BGN05.
- The subgroup decision assumption was introduced for this scheme — BGN05.