Succinct LWE ⇒ ABE

Succinct LWE implies ABE.

Statement

Migrated verbatim from learning-with-errors § Succinct LWE:

Succinct LWE is a falsifiable, single-game strengthening of LWE introduced by Wee — Wee25 — for constructing KP- and CP-ABE for circuits with $O(1)$-size ciphertexts and keys. Unlike Evasive LWE (an implication between two conditions), it is a standard indistinguishability game: an LWE sample $(\mathbf{B},\mathbf{sB}+\mathbf{e})$ is indistinguishable from uniform even when the adversary is given a short matrix $T$ satisfying $[I_{\ell }\otimes \mathbf{B}\mid \mathbf{W}]\cdot T=I_{\ell }\otimes \mathbf{G}$, where $\ell =\mathrm{poly}(\lambda )$ and $\mathbf{G}$ is the MP12 gadget matrix.

Migrated verbatim from learning-with-errors § Succinct LWE:

The primary application is attribute-based encryption with $O(1)$-size ciphertexts and secret keys for arbitrary circuits — Wee25.

Notes

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

This relation is stated on 2 pages; the statements above are all of them.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Duplicated at line 277 of the same page with the same citation.
• O(1)-size ciphertexts and keys is a concrete efficiency claim bundled into the reduction.
• Duplicate of the claim at line 243 of the same page.