Paper 2025/1870

Lookup-Table Evaluation over Key-Homomorphic Encodings and KP-ABE for Nonlinear Operations

Abstract

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<B<\sqrt{q}$, with noise growth independent of the magnitudes of the encoded integers. Consequently, this replaces the $\log_2 q$ factor in the circuit-size blow-up with $\log_{B} q$, yielding a reduction in evaluation time by a factor polynomial in $\log_2 B$. We obtain: (i) small-integer arithmetic with base-$B$ outputs in constant size; (ii) modulo-$q$ multiplication with circuit size quadratic in $\log_{B} q$; and (iii) homomorphic ciphertext multiplication in the Gentry--Sahai--Waters FHE scheme~(Crypto'13) with circuit size approximately cubic in $\log_{B} q$. As an application, we build a KP-ABE scheme that is selectively secure under the Ring-LWE assumption and compatible with our LUT evaluation method. This reduces decryption cost by a factor polynomial in $\log_2 B$ at the expense of a polynomial-in-$B$ increase in decryption-key generation cost and decryption-key size, which is an attractive trade-off because decryption is invoked far more frequently than key generation in ABE applications.