The Constant Lock

In attribute-based encryption, a ciphertext can only be decrypted by someone whose attributes satisfy a policy — “must be a doctor AND work in cardiology AND have security clearance level 3.” The policy is embedded in the ciphertext itself. More complex policies should, intuitively, require larger ciphertexts.

Liu, Zhang, and Fu (arXiv:2603.16117) show they don’t. For policies expressible as NC¹ circuits — a broad class including arbitrary boolean formulas of polynomial depth — the ciphertext size is constant. Independent of the circuit’s depth, its size, the number of attributes involved. The policy can be arbitrarily complex; the encrypted message stays the same size.

The structural trick: separate where the complexity lives. The policy complexity is absorbed entirely by the public key and the decryption key, not by the ciphertext. The ciphertext carries the encrypted message and nothing else. The question (“who can read this?”) and the answer (“this is the message”) are structurally decoupled.

This is built on succinct Learning With Errors — a lattice-based assumption where evaluation of a function on an encrypted input produces an output whose size does not grow with the function’s complexity. The function is “baked into” the key generation, not the encryption.

The deeper principle: the complexity of an access decision does not need to propagate to the object being accessed. A door with a simple lock and a door with a complex lock are both the same size. The sophistication lives in the key, not the lock. This separability — between policy complexity and artifact complexity — is not obvious. In most encryption schemes, the policy leaks into the ciphertext through structural overhead. Here, the overhead is provably zero.