REFHE: Fully Homomorphic ALU

Abstract

We present a fully homomorphic encryption scheme supporting arithmetic and logical operations on large machine words (plaintexts of form Z_2^n, such as n=64). Building on the BGV framework with modified number field selection and message encoding, the scheme supports expansive message spaces with controlled noise growth.

The approach enables native arithmetic operations modulo 2^n and features an efficient bootstrapping procedure that decomposes machine words into individual bits, allowing logical operations during bootstrapping. Operations like "greater than" comparisons require only a single subtraction and a single bootstrapping cycle.

The research introduces novel tools including generalized BGV modulus switching for ideal-based plaintexts and ciphertexts.