Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, FOCS ’10; Brakerski-Vaikuntanathan, STOC ’11], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov-Vaikuntanathan-Wee, STOC ’13; Boneh et al., Eurocrypt ’14], only accommodate circuits up to all predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. Intriguingly, for over a decade, it has remained unclear whether the circular security assumptions empowering FHE can similarly benefit ABE. In this work, we introduce new lattice-based techniques to overcome the depth-dependency limitations: •Relying on a circular security assumption, we construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size.•Based on the evasive circular LWE assumption, a stronger variant of the recently proposed evasive LWE assumption [Wee, Eurocrypt ’22; Tsabary, Crypto ’22], we construct a full-fledged ABE scheme for circuits of unbounded depth and size. Our constructions eliminate the multiplicative overheads polynomial in depth from previous constructions. Our LFE, 1key FE, and reusable garbling schemes achieve almost optimal succinctness. Their ciphertexts and input encodings are proportional in length to the input, while function digest, secret keys, and garbled circuits maintain a constant size independent of circuit parameters. Our ABE schemes offer short components, with master public key and ciphertext sizes linear in the attribute length and secret key being constant-size.