International Association
for Cryptologic Research

Lattice-based key-homomorphic encodings introduced by Boneh et al.~(Eurocrypt'14)---known as BGG+ encodings---underpin many primitives, including key-policy attribute-based encryption (KP-ABE). Many applications beyond KP-ABE require simulating the homomorphic evaluation of FHE ciphertexts over BGG+ encodings, which involves nonlinear operations on integers of magnitude up to the ciphertext modulus $q$. However, due to noise growth incurred by multiplication, the encodable integers must be kept small, typically bits, thereby forcing nonlinear operations to be simulated by Boolean circuits and incurring a circuit-size blow-up polynomial in $\log_2 q$. Apart from resorting to costly bootstrapping for BGG+ encodings, no method is known to beat this baseline. We propose a method to evaluate lookup tables~(LUTs) over BGG+ encodings that operates directly on base-$B$ digit representations for $2