Paper 2026/1439

ABE for Unbounded Depth Circuits from the Doubly Circular Assumption

Abstract

The recent work of Hsieh, Lin and Luo [HLL23] (HLL23) provided the first construction of ABE for unbounded depth circuits from the circular evasive LWE assumption, which they introduced. Unfortunately, this assumption has been recently broken [AMYY25]. Finding a new construction for unbounded depth ABE from a safe assumption, without relying on compact functional encryption or obfuscation, is therefore an important open problem. In this work, we provide a new candidate for ABE for circuits of unbounded depth as well as unbounded width from a novel, falsifiable ``doubly circular'' assumption which combines circular LWE with key dependent message security of a variant of ElGamal encryption in an inseparable manner. We show that the assumption holds in Shoup's bilinear generic group model, which rules out all non-generic attacks. In particular, this implies that our construction is secure assuming circular LWE in the bilinear generic group model, which has a long history of study. We also show that in a restricted setting, it is implied by the standard SXDH assumption and circular LWE.