Every attribute leaf holds a share of a hidden secret, produced by evaluating a random polynomial q(x) of degree k−1 whose constant term is the secret: q(0) = S. The gate is satisfied once at least k of the n attributes are present — an AND gate is just k = n, an OR gate is k = 1.
Secret sharing (Shamir): q(x) = S + a1*x + a2*x^2 + … + a(k-1)*x^(k-1)
Share for attribute i: share_i = q(i)
Reconstruction (Lagrange interpolation at x=0), using any k shares from set T:
S = Σ_{i in T} share_i · Δ_i(0), Δ_i(0) = Π_{j in T, j≠i} (0 − j) / (i − j)
- KP-ABE — the policy tree is baked into the user's key; the data is tagged with plain attributes. Decrypts if the data's attributes satisfy the key's policy.
- CP-ABE — the policy tree is baked into the ciphertext; the user's key just carries attributes. Decrypts if the key's attributes satisfy the ciphertext's policy.
- Toggling attributes below simulates which ones the user actually holds; picking a gate/threshold simulates the access policy attached at Setup / Encryption time.
This mirrors the real KP-ABE construction (Goyal–Pandey–Sahai–Waters): each internal access-tree node runs its own Shamir sharing, and decryption walks the tree bottom-up, only ever reconstructing a parent's share once its own threshold is met.