Setting up of polynomials for CP-ABE or KP-ABE Access Trees

My question I guess is how the selection is done. A brief explanation with a simple access tree will be very helpful.

• What do you mean by "selection"? Polynomials are randomly generated. Jan 20 '16 at 22:34
• my bad, i used the wrong term there. What i mean to ask is the process. I know they are randomly generated with the degree being less than the threshold value for the node. I sort of understand the concept as it relates to a particular node or point on the access tree. What is still a bit confusing is the process for an actual access tree leading from the least leaf node to the root node to actually allow for decryption in the case of ABE and for encryption in the case of CP-ABE. Thanks Jan 20 '16 at 22:39

1 Answer

I suggest, you look into the code how that works. Basically, you start with a secret that you want to share according to some tree. You share the secret with a Threshold Secret Sharing Scheme like Shamir's Secret Sharing and put the resulting shares into the children of that node (in the beginning this is the root node). Then you can re-share each of the shares if this is necessary. Here is an example:

In the end, every non-leaf node in the tree has its own polynomial that has to be evaluated and every leaf node has a share. In the reconstruction phase, you apply Lagrange interpolation at each node from the bottom up.

Of course, it is possible to make some optimizations. For example, if the root node is an OR gate and the left subtree is large, but the right subtree is only a single leaf, then you should first check whether the right subtree is satisfied and reconstruct the root secret only from one leaf.

• The point I was missing was the fact that the shares for each node are reshared for its child nodes. That explains the transversal up till the root node which is the ultimate secret. Thanks Jan 20 '16 at 23:18
• for the coding. I plan to use a python library called Charm as my knowledge of C isnt that good Jan 20 '16 at 23:19
• "The point I was missing was the fact that the shares for each node are reshared for its child nodes." - This is basically what $q_x(0)=q_{parent(x)}(index(x))$ means. The secret is always the polynomial evaluated at 0: $P(0)$. Jan 20 '16 at 23:21
• Keep in mind that Charm has all of this already implemented and the policy parsing and share generation is given by the framework. You don't have to do that yourself. Jan 20 '16 at 23:23
• Thats good to know. Got it installed yesterday. Will look at the documentation. Thanks for your help Jan 21 '16 at 2:14