Paper 2026/1439

ABE for Unbounded Circuits from Circular LWE and Pairings

Abstract

Constructing attribute based encryption (ABE) for unbounded circuits, namely circuits with both depth and width being unbounded, and for Turing machines are perhaps the most important open questions in ABE research. Recent years saw some much-awaited progress on these long-standing problems -- (i) the work of Hsieh, Lin and Luo [HLL23] (HLL23) provided the first construction of ABE for unbounded circuits from a new circular evasive LWE assumption, (ii) the follow-up work of Agrawal, Kumari and Yamada [AKY24b] and Cini and Wee [CW25] gave the first constructions of ABE for Turing machines. Unfortunately, all these works relied on different versions of the ``private-coin'' Evasive Learning With Errors assumption which was invalidated in a sequence of attacks [BUW25, BDJ+25, DJM+25, AMYY25, HJL25, HHY26]. Finding new constructions from better-understood assumptions (without relying on compact functional encryption or obfuscation) is therefore an important open problem. In this work, we make progress towards this goal. Our contributions are: 1. *KP-ABE for Unbounded Circuits from Circular Small-Secret LWE and Bilinear GGM.* We provide a new candidate for key-policy ABE for unbounded circuits from circular small-secret Learning With Errors (csLWE) and the Bilinear Generic Group Model (BGGM). Since the BGGM has a long history of study, we believe that this provides strong evidence for the security of our scheme. In the standard model, we argue security from a novel, falsifiable ``doubly circular'' assumption which combines csLWE with key dependent message security of a variant of ElGamal encryption in an inseparable manner. We show that in a restricted setting, it is implied by the standard SXDH assumption and csLWE. 2. *SK CP-ABE for Unbounded Circuits from Circular Small-Secret LWE. * In the symmetric key setting, we provide a new candidate for ciphertext-policy ABE for unbounded circuits from only the csLWE assumption. 3. *SK KP-ABE for Turing Machines from Circular Small-Secret LWE.* In the symmetric key setting, we provide the first key-policy ABE for Turing machines from the csLWE assumption. Curiously, each of our constructions is intrinsically key-policy or ciphertext-policy and stubbornly resists adaptation to its dual variant. Thus, our work exhibits a surprising (to us) dichotomy between the key and ciphertext policy versions of ABE for unbounded circuits. Finding dual versions of the above constructions, removing pairings altogether or dispensing with the symmetric key setting are fascinating open problems.

Note: In addition to the construction of KP-ABE for unbounded circuits from the circular small-secret LWE assumption and Bilinear GGM, this revision of the paper includes two more contributions. We also provide a new candidate for secret-key CP-ABE for Unbounded Circuits and for secret-key KP-ABE for a Turing Machine, based on the circular small-secret LWE assumption.