💻 computer science

Ciphertext-Policy ABE for $\mathsf{NC}^1$ Circuits with Constant-Size Ciphertexts from Succinct LWE

This paper presents a selectively secure, lattice-based ciphertext-policy attribute-based encryption scheme for $\mathsf{NC}^1$ circuits that achieves constant-size ciphertexts and public keys independent of circuit depth under the succinct LWE assumption.

Original authors: Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiaqi Liu, Yuanyi Zhang, Fang-Wei Fu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a high-security vault. You have a master key, but you don't want to give the whole vault to just one person. Instead, you want to give people "keys" that only open specific parts of the vault, but only if they meet certain conditions.

This is the world of Ciphertext-Policy Attribute-Based Encryption (CP-ABE).

Here is a simple breakdown of what this paper achieves, using everyday analogies.

1. The Problem: The "Too Big" Lock

In traditional encryption, if you want to send a secret message to a group, you usually have to encrypt it separately for every single person, or use a system where the "lock" (the ciphertext) gets huge as the number of people or the complexity of the rules increases.

Imagine trying to send a secret letter to a club of 1,000 members.

Old Way: The envelope (ciphertext) gets so big it fills a truck because it has a separate lock for every member.
The Goal: We want an envelope that stays the same size (like a standard postcard), no matter if the club has 10 members or 10 million, and no matter how complex the rules are for who can open it.

2. The Solution: A "Magic Postcard"

The authors of this paper have built a new type of digital lock system.

The Envelope (Ciphertext): It is now constant size. Whether you are sending a secret to 10 people or 10,000, the encrypted message is always the same tiny size. It's like sending a postcard that magically expands to fit the right person's key, but the card itself never gets bigger.
The Rules (Access Policy): You can set complex rules. For example: "Only open if the user is a 'Manager' AND ('Senior' OR 'Security')." The system handles these complex logic puzzles (called NC1 circuits) efficiently.
The Keys: The user's key is small, but it grows slightly based on how many "badges" (attributes) they have. If you only have one badge, your key is tiny.

3. How They Did It: The "Universal Master Key" Trick

To achieve this magic, the authors used a concept from quantum-resistant mathematics called Lattice-based cryptography (specifically something called "Succinct LWE").

Think of it like this:

The Old Way: To verify a user's identity, the system had to check a giant list of names.
The New Way: The authors used a Matrix Commitment. Imagine a giant, magical filing cabinet. Instead of listing every single file inside the cabinet to prove it's there, you just show a single, tiny "receipt" (the commitment) that proves the cabinet contains the right files.
The "Succinct" Part: They used a mathematical assumption that allows them to create a "short" proof. It's like proving you have a billion dollars in the bank without showing a billion bank statements; you just show one cryptic, unforgeable receipt that the bank trusts.

4. The "Broadcast" Bonus

One of the coolest side effects of this technology is Broadcast Encryption.

Scenario: Imagine a TV station wants to send a pay-per-view movie to 1 million subscribers.
Old Problem: The signal usually gets bloated with data for every single subscriber.
New Solution: With this new system, the TV station sends one single, tiny signal.
- If you are a subscriber, your "key" (which is small) fits the lock.
- If you aren't, the lock stays shut.
- The size of the signal doesn't care if there are 100 users or 100 million. It stays small.

5. Why This Matters (The "Quantum" Angle)

Most current encryption relies on math problems that a future Quantum Computer could solve easily (like cracking a safe with a master key).

This new system is built on Lattice problems, which are believed to be resistant to quantum computers.
It's like upgrading from a wooden lock (easy to break with a new tool) to a titanium lock that even a super-tool can't break.

Summary Analogy

Imagine a Giant Library (the encrypted data).

Old System: To let people in, you had to print a unique, massive map for every single person showing them exactly where to walk. The more people, the more paper you needed.
This Paper's System: You give everyone a small, standard ID card. The library door has a smart scanner. The scanner reads the ID card and checks a tiny, magical "rulebook" (the constant-size ciphertext).
- If your ID matches the rules (e.g., "Must be a Librarian AND have a Red Badge"), the door opens.
- The door's scanner and the rulebook stay the same size, even if the library adds a million new books or a million new visitors.

In short: The authors created a way to send secret messages to complex groups where the message size never bloats, the keys stay small, and the whole system is safe from future quantum computers.

1. Problem Statement

The paper addresses the challenge of constructing efficient Ciphertext-Policy Attribute-Based Encryption (CP-ABE) schemes for complex access policies (specifically NC1 circuits) while minimizing ciphertext size.

Context: In CP-ABE, a ciphertext is encrypted under an access policy $f$ , and a user can decrypt only if their attributes $x$ satisfy $f(x) = 0$ (or 1, depending on convention).
The Bottleneck: Existing lattice-based CP-ABE schemes often suffer from ciphertext sizes that scale linearly with the complexity of the access policy (e.g., the depth $d$ or size $s$ of the circuit). This makes them impractical for large-scale applications like broadcast encryption where the number of users $N$ is large.
Goal: Construct a CP-ABE scheme where the ciphertext size is constant (independent of the circuit depth $d$ and size $s$ ), while maintaining security based on standard lattice assumptions resistant to quantum attacks.

2. Methodology

The authors propose a novel construction that combines Linear Secret Sharing Schemes (LSSS), Matrix Commitments, and the Succinct LWE assumption.

A. Core Assumption: Succinct LWE

The security relies on the $\ell$ -succinct LWE assumption (introduced by Wee, CRYPTO 2024).

Unlike standard LWE, this assumption involves a "succinct" structure where a trapdoor $T$ allows sampling short preimages for a matrix of the form $[I_\ell \otimes B \mid W]$ , where $W$ is statistically close to uniform.
This allows the scheme to handle large dimensions ( $\ell$ ) without the public parameters or ciphertexts growing linearly with $\ell$ .

B. Technical Innovations

Matrix Commitment for Compression:
- The authors adapt the Matrix Commitment scheme (from Wee 2025). Instead of encrypting a message under a large matrix representing the access structure, they commit to the matrix $U$ (derived from the policy and public parameters) using a short commitment matrix $C$ .
- The ciphertext contains only the commitment $C$ and a few LWE samples, rather than the full matrix components.
Modification of the DKW21 Scheme:
- The construction builds upon the CP-ABE scheme by Datta, Kurosawa, and Wee (DKW21), which supports LSSS-based policies.
- Key Change: In DKW21, the ciphertext size scales with the number of rows in the LSSS matrix ( $\ell$ ). The authors replace the explicit matrices $\{A_u\}$ and vectors $\{v_j\}$ with a single commitment matrix $C$ and a single matrix $B$ .
- Encryption: The ciphertext consists of three components:
  - $c_1 \approx s^\top B$ (Standard LWE sample).
  - $c_2 \approx s^\top (A + C)$ (Compressed policy information).
  - $c_3 \approx s^\top y + \text{msg}$ (Message encoding).
- Here, $C$ is the commitment to the matrix $U$ constructed from the policy $M$ and attributes.
Decryption Mechanism:
- To decrypt, the user utilizes their secret key (associated with attributes) and the verification matrix $V$ of the commitment.
- They compute $c_2 V + c_1 Z$ (where $Z$ is the opening of the commitment) to recover the underlying LWE samples corresponding to the specific attributes, effectively "opening" the commitment to the relevant parts of the policy without revealing the whole policy.
- The reconstruction coefficients of the LSSS are then applied to recover the message.
Security Proof Strategy (Hybrid Games):
- The proof uses a sequence of hybrid games to transition from the real scheme to a random one.
- Key Challenge: Generating secret keys for unauthorized attribute sets without using the master trapdoor (which would break the LWE assumption).
- Solution: The authors use the trapdoor $T$ from the Succinct LWE assumption to generate new trapdoors for matrices of the form $[I \otimes B \mid W']$ on the fly. This allows the simulator to answer secret key queries for unauthorized sets without knowing the secret $s$ used in the LWE samples, ensuring the ciphertext remains indistinguishable from random.

3. Key Contributions

Constant-Size Ciphertexts: The scheme achieves ciphertext size $O(1)$ (independent of the circuit depth $d$ and size $s$ ), which is asymptotically optimal up to polynomial factors in the security parameter $\lambda$ .
NC1 Circuit Support: It supports access policies represented by NC1 circuits (circuits of logarithmic depth and polynomial size), which covers a broad class of boolean formulas and logic gates.
Public Parameter Optimization: While the public key size initially scales with the circuit size $s$ , the authors note that the non-uniform part is small ( $poly(\lambda)$ ). The rest can be generated via a Pseudorandom Generator (PRG), effectively compressing the public parameters to $O(1)$ in practice.
Optimal Broadcast Encryption: As a direct application, the scheme yields a Broadcast Encryption scheme for $N$ $N$ users with:
- Ciphertext size: $poly(\lambda)$ (independent of $\log N$ ).
- Key size: $poly(\lambda, \log N)$ .
- This is considered optimal for broadcast encryption under the Succinct LWE assumption.

4. Results and Parameters

Let $\lambda$ be the security parameter, $d$ the circuit depth, $s$ the circuit size, and $\ell$ the input bit length.

**Ciphertext Size ($|ct| $):**$ O(1)$ (hides $poly(\lambda)$ ). Independent of $d, s, \ell$ .
**Public Key Size ($|pk| $):**$ O(s)$ (can be compressed to $O(1)$ via PRG).
**Secret Key Size ($|sk| $):**$ O(\ell)$ (depends on the number of attributes; can be $O(1)$ if users have a constant number of attributes).
Security Model: Selectively secure in the Standard Model.
Assumption: Based on $poly(\lambda)$ -succinct LWE with sub-exponential modulus-to-noise ratio.

5. Significance

Quantum Resistance: By relying on Lattice-based assumptions (LWE) rather than bilinear pairings, the scheme is believed to be secure against quantum attacks.
Scalability: The constant-size ciphertext is a major breakthrough for applications like Broadcast Encryption and Secure Data Sharing in large-scale systems. Previous schemes required ciphertexts that grew with the number of users or the complexity of the policy, making them inefficient for massive user bases.
Theoretical Advancement: The work demonstrates the power of Succinct LWE and Matrix Commitments in constructing efficient cryptographic primitives. It bridges the gap between theoretical succinctness and practical CP-ABE construction, offering a new paradigm for handling complex access structures with minimal overhead.
Comparison: Compared to recent works (e.g., Wee 2025), this scheme offers independent ciphertext size from the circuit depth and input length, though it trades off a slightly larger secret key size in general cases (though still efficient for typical attribute sets).

In summary, this paper presents a significant step forward in post-quantum cryptography by enabling highly efficient, fine-grained access control where the encrypted data size does not bloat with the complexity of the access policy.