# Lagrange Coefficients & Polynomial in KP-ABE

My question is how these concepts relate in ABE.

I am assuming that the attributes are used to share the master secret key and only a user with the right attributes for a particular access tree is able to reconstruct the master secret key.

Could someone help with some details on how this work.

Short refresher on KP-ABE:

The Master Secret Key (MSK) and the Public Parameters (PP) are created during Setup and both enable the attribute authority to create Secret Keys (SK) for users using the Keygen algorithm.

Some user who possesses PP can Encrypt some data with a set of attributes $\gamma$. The encryption works by generating a new random secret $s$ and using that secret on all attributes in set $\gamma$.

$${E_i=T_i^s}_\gamma$$

The Keygen algorithm takes a policy (access tree) and MSK to create SK. The $y$ element from MSK is shared by using the policy into shares that represent the leaves of the access tree $q_x(0)$. This is very similar to Shamir's Secret Sharing. Those shares are used as

$$D_x=g^{\frac{q_x(0)}{t_i}}$$

where $q_x(0)$ and $t_i$ are both not easy to calculate due to the difficulty of discrete logarithm. Since the Lagrange interpolation is done in the exponent, as the polynomial interpolation on page 9 shows, it cannot reveal $y$. In the end we get $e(g,g)^{ys}$ where $y$ is still not easily computable due to discrete logarithm.

I am assuming that the attributes are used to share the master secret key and only a user with the right attributes for a particular access tree is able to reconstruct the master secret key.

If the user would be able to reconstruct MSK from its own SK and the received CT, then it could create SKs for any attribute set and decrypt any CT with any policy. Of course, this is not the point of ABE. The MSK is the master secret key, because you can create any SK from it, so it must be kept secret at all cost by the attribute authority. This is also the main problem of ABE, because this is basically a key escrow service that, if broken into, undermines the complete security of the system.

• Thanks for the refresher...One thing that is still not entirely clear is the decryption process. When you have the ciphertext labelled with attributes and then a secret key with an access structure, how is the original message gotten without a reconstruction of the master secret key? – chisky Jan 20 '16 at 21:58
• so I guess I was looking at it all wrong. While the master secret key is used in generating the secret key. It is not reconstructed for decryption. – chisky Jan 20 '16 at 22:08
• Try to trace back where $y$ is used. You will see that it is used for creating the ciphertext ($Y$) and creating a secret key ($q_r(0)$). It is hidden in both cases, but during decryption, both cancel each other out through the division. You can think of it as a hidden blinding value. – Artjom B. Jan 20 '16 at 22:08
• ok thanks for the info. Another concept that still eludes me is the whole selection of polynomials and calculations that have to be done at seperate levels of the access tree be it a leaf or child node. Still grasping the specifics of ABE to use it for research so thanks once again – chisky Jan 20 '16 at 22:31