Flaws found and fixed in decentralized multi-authority encryption schemes
Cryptanalysis and Repair of "Decentralized Multi-authority ABE for NC$^1$ from BDH"
Cryptography and Security
Summary
Some widely studied encryption methods that use multiple authorities and attributes to control who sees information have a security weakness. The authors showed that a corrupt authority can break the system’s protections to recover messages they shouldn’t access. They identified the technical mistake causing this and proposed fixes that keep the original system’s efficiency while restoring security. Their work also corrects similar problems in related encryption designs and provides formal proofs showing the repaired versions are secure under standard assumptions.
What this means in practice
- •For cloud security teams: Ensure multi-authority attribute-based encryption setups are patched to prevent malicious authorities from decrypting unauthorized data.
- •For cryptographic software developers: Use the repaired schemes to build decentralized attribute-based encryption tools with provable security and unchanged key and ciphertext sizes.
Authors
Xingwang Wang
Abstract
We present a plaintext-recovery attack on the decentralized multi-authority attribute-based encryption construction of Datta, Komargodski, and Waters (Journal of Cryptology, 2023). The attack succeeds in the claimed static model with one corrupt authority and two users whose individual attribute sets remain unauthorized even when combined with the corrupt authority's attribute. The flaw is an incorrect extension of LSSS matrix-normalization invariance from complete secret shares to coordinate-wise ciphertext masks. A corrupt authority can expose these masks and remove identity binding from other users' decryption shares. We replace the coordinate-wise masks with independent full linear sharings of zero and prove static security under decisional bilinear Diffie-Hellman (DBDH) in the random oracle model. The repair retains the original matrix-width and row-labeling restrictions and leaves authority keys, user keys, decryption, and ciphertext size unchanged, while increasing encryption randomness and field arithmetic. We also give analogous attacks on both multi-authority attribute-based inner-product functional encryption constructions of Datta and Pal (PKC, 2023). The same modification restores correctness and matrix-substitution invariance for both variants. We prove static security of the repaired small-universe variant under asymmetric DBDH. For the large-universe variant, we identify a separate missing source-group encoding in the original reduction, formulate an augmented $L$-DBDH assumption, prove its hardness in the asymmetric generic bilinear group model, and give a static security reduction for the repaired scheme.