Ciphertext-Policy 𝖠𝖑𝖀 \mathsf{ABE} for 𝖭𝖒 1 \mathsf{NC}^{1} Circuits with Constant-Size Ciphertexts from Succinct 𝖫𝖢𝖀 \mathsf{LWE}

Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu Β· 2026

Read Ciphertext-Policy 𝖠𝖑𝖀 \mathsf{ABE} for 𝖭𝖒 1 \mathsf{NC}^{1} Circuits with Constant-Size Ciphertexts from Succinct 𝖫𝖢𝖀 \mathsf{LWE} by Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16117.txt.

Introduction

Liu, Zhang, and Fu build lattice encryption with tiny ciphertexts for NC1 policies. Ciphertext-policy attribute schemes gate decryption by circuit tests. Their NC1 circuit scheme keeps ciphertext size constant in depth. Public keys share that constant size as well. Secret keys grow only with input bit length. A broadcast scheme for N users falls out as a bonus. Its ciphertext stays free of any log N growth. Security rests on the succinct LWE assumption of Wee. Selective security holds in the standard model.

Catalog record

CREATORJiaqi Liu, Yuanyi Zhang, Fang-Wei Fu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE173608
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16117

Browse the full library Β· About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ciphertext-Policy 𝖠𝖑𝖀 \mathsf{ABE} for 𝖭𝖒 1 \mathsf{NC}^{1} Circuits with Constant-Size Ciphertexts from Succinct 𝖫𝖢𝖀 \mathsf{LWE} Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu Abstract We construct a lattice-based ciphertext-policy attribute-based encryption ( 𝖒𝖯 ​ - ​ 𝖠𝖑𝖀 \mathsf{CP}\text{-}\mathsf{ABE} ) scheme for 𝖭𝖒 1 \mathsf{NC}^{1} access policies with constant-size ciphertexts. Let Ξ» \lambda be the security parameter. For an 𝖭𝖒 1 \mathsf{NC}^{1} circuit of depth d d and size s s on β„“ \ell -bit inputs, our scheme has the public-key and ciphertext sizes O ⁑ ( 1 ) O(1) (independent of d d ), and secret-key size O ⁑ ( β„“ ) O(\ell) , where the O ⁑ ( β‹… ) O(\cdot) hides poly ⁑ ( Ξ» ) \poly(\lambda) factors. As an application, we obtain a broadcast encryption scheme for N N users with ciphertext size poly ⁑ ( Ξ» ) \poly(\lambda) independent of log ⁑ N \log N and key sizes poly ⁑ ( Ξ» , log ⁑ N ) \poly(\lambda,\log N) . Our construction is selectively secure in the standard model under the poly ⁑ ( Ξ» ) \poly(\lambda) -succinct 𝖫𝖢𝖀 \mathsf{LWE} assumption introduced by Wee (CRYPTO 2024). I Introduction In a traditional public-key encryption scheme, only a user who possesses the secret key corresponding to the public key used for encryption can decrypt the ciphertext. As a generalization of public-key encryption, attribute-based encryption ( \mathsf{ABE} ) realizes fine-grained access control over encrypted data. There are two types of \mathsf{ABE} schemes: ciphertext-policy \mathsf{ABE} ( \mathsf{CP}\text{-}\mathsf{ABE} ) and key-policy \mathsf{ABE} ( \mathsf{KP}\text{-}\mathsf{ABE} ). In a \mathsf{CP}\text{-}\mathsf{ABE} scheme, each secret key \mathsf{sk}_{\mathbf{x}} is associated with an attribute \mathbf{x}\in\{0,1\}^{\ell} , and each ciphertext \mathsf{ct}_{f} is associated with an access policy f that specifies which attribute vectors are authorized to decrypt it. In contrast, in a \mathsf{KP}\text{-}\mathsf{ABE} scheme, each secret key \mathsf{sk}_{f} is associated with an access policy f , and each ciphertext \mathsf{ct}_{\mathbf{x}} is associated with an attribute \mathbf{x} . In both cases, decryption succeeds only if the attribute satisfies the access policy, i.e., f(\mathbf{x})=0 ; otherwise, the decryptor learns no information about the underlying plaintext. The concept of \mathsf{ABE} was first proposed independently by Sahai and Waters [ 24 ] and by Goyal et al. [ 20 ] . Since then, \mathsf{ABE} has become a fundamental cryptographic primitive, and many concrete schemes have been proposed. A large fraction of existing \mathsf{ABE} constructions rely on assumptions over bilinear groups. However, due to known quantum attacks on bilinear-group-based assumptions, there has been substantial interest in constructing schemes from alternative assumptions. In particular, many subsequent \mathsf{ABE} schemes base their security on the \mathsf{LWE} assumption or its variants, which are believed to be resistant to quantum attacks. In [ 2 , 11 , 17 , 9 , 19 , 13 , 25 , 4 , 15 ] , a series of \mathsf{KP}\text{-}\mathsf{ABE} schemes were proposed, all based on the \mathsf{LWE} assumption. A generic transformation can convert a \mathsf{KP}\text{-}\mathsf{ABE} scheme into a \mathsf{CP}\text{-}\mathsf{ABE} one via a universal circuit. However, this transformation typically leads to significantly worse parameters. To optimize the parameters of \mathsf{CP}\text{-}\mathsf{ABE} scheme, Agrawal and Yamada [ 5 ] proposed a \mathsf{CP}\text{-}\mathsf{ABE} scheme for all \mathsf{NC}^{1} circuits with ciphertext size independent of the circuit size s , relying on the \mathsf{LWE} and generic bilinear groups. Datta et al. [ 16 ] proposed a \mathsf{CP}\text{-}\mathsf{ABE} scheme for all \mathsf{NC}^{1} circuits via linear secret sharing schemes, relying on the hardness of the \mathsf{LWE} assumption. Subsequently, there are many \mathsf{CP}\text{-}\mathsf{ABE} schemes relying on the nonstandard \mathsf{LWE} -related assumptions. Wee [ 27 ] proposed a \mathsf{CP}\text{-}\mathsf{ABE} scheme based on the evasive \mathsf{LWE} assumption and tensor \mathsf{LWE} assumption. Hsieh et al. [ 21 ] presented a \mathsf{CP}\text{-}\mathsf{ABE} scheme based on the (structured) evasive \mathsf{LWE} assumption. Agrawal et al. [ 3 ] proposed a \mathsf{CP}\text{-}\mathsf{ABE} scheme for all Turing machines based on the circular evasive \mathsf{LWE} and tensor \mathsf{LWE} . Wee [ 28 , 29 ] presents \mathsf{CP}\text{-}\mathsf{ABE} scheme for all circuits based on the weaker \poly(\lambda,d) -succinct \mathsf{LWE} assumption with ciphertext size independent of the attribute length \ell . I-A Our results We list our results as below: 1. In this work, we present a \mathsf{CP}\text{-}\mathsf{ABE} scheme for access policies represented by \mathsf{NC}^{1} circuits. For circuits on \ell -bit inputs with depth d and size s (hence s=\poly(\ell) and d=\log(\ell) ) where s,d,\ell are fixed at setup. We construct a \mathsf{CP}\text{-}\mathsf{ABE} scheme with parameters: |\mathsf{pk}|=O(s),\quad|\mathsf{sk}|=O(\ell),\quad|\mathsf{ct}|=O(1), where the notation O(\cdot) hides \poly(\lambda) factors. It proves to be selectively secure against unbounded collusions. The security relies on the \poly(\lambda) -succinct \mathsf{LWE} assumptions with sub-exponential modulus-to-noise ratio. β€’ The scheme we construct is a succinct \mathsf{CP}\text{-}\mathsf{ABE} . Namely, the ciphertext size in our scheme relies only on the security parameter \lambda and independent of the size s , the input length \ell , and the depth d , which is asymptotically optimal up to \poly(\lambda) factors. β€’ The size of the public parameters scales with the circuit size s . Though it is seen as not competitive compared with previous schemes (many schemes have public key size O(\ell) , such as [ 14 , 27 , 21 ] ), we observe that in the public parameters, all elements are sampled uniformly except for the public parameters used in the succinct \mathsf{LWE} instance (i.e., \mathsf{pp}=(\mathbf{B},\mathbf{W},\mathbf{T}) ), which is of size \poly(\lambda) . Therefore, we can generate the purely uniform part with a pseudorandom generator instead. We can then compress the size of the public parameters into O(1) size. β€’ The bound on the size of \mathsf{sk} is not tight. It depends on the number of attributes associated with the secret key rather than strictly on \ell . In scenarios where the users possesses only O(1) attributes, the secret-key size can be reduced to O(1) . 2. \mathsf{CP}\text{-}\mathsf{ABE} for \mathsf{NC}^{1} circuits gives a broadcast encryption for N=\ell users as a special case. In the broadcast encryption, we can use a circuit of size O(N\log N) and depth O(\log N) to check the membership of the users. We obtain a broadcast encryption scheme for N users with parameters |\mathsf{pk}|=N\cdot\poly(\lambda,\log N),\quad|\mathsf{sk}|=\poly(\lambda,\log N),\quad|\mathsf{ct}|=\poly(\lambda). By using a pseudorandom generator to compress the public parameter, we can reduce |\mathsf{pk}| to \poly(\lambda) . Since |\mathsf{pk}|+|\mathsf{ct}|+|\mathsf{sk}|=\poly(\lambda,\log N) , we obtain an optimal broadcast encryption (under \poly(\lambda) -succinct \mathsf{LWE} assumption). 3. In the proof of the selective security of our construction, we use the technique of using the trapdoor \mathbf{T} for [\mathbf{I}_{\ell}\otimes\mathbf{B}\mid\mathbf{W}] in the \ell -succinct \mathsf{LWE} assumption to generate other trapdoors for the matrix of the form [\mathbf{I}_{\ell^{\prime}}\otimes\mathbf{B}\mid\mathbf{W}^{\prime}] , where \mathbf{W}^{\prime} is statistically close to uniform. I-B Related Works Comparison with [ 29 ] . We use the \{0,1\} - \mathsf{LSSS} technique from [ 16 ] and the matrix commitment scheme from [ 29 ] to construct our \mathsf{CP}\text{-}\mathsf{ABE} scheme for \mathsf{NC}^{1} scheme and obtain an optimal broadcast encryption scheme. Compared with [ 29 ] , our scheme supports a narrower class of access policies and incurs a larger secret-key size. Nevertheless, we improve the parameters in the following respects: (1) |\mathsf{pk}| , |\mathsf{sk}| , and |\mathsf{ct}| are independent of the circuit depth d ; (2) the resulting broadcast encryption has ciphertext size |\mathsf{ct}| independent of \log N , where N is the number of users in the system; (3) during encryption, we

Read the complete text