Welcome to the resource topic for 2025/1870
Title:
Lookup-Table Evaluation over Key-Homomorphic Encodings and KP-ABE for Nonlinear Operations
Authors: Sora Suegami, Enrico Bottazzi
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.
ePrint: https://eprint.iacr.org/2025/1870
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .