enter image description here

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

  • $\begingroup$ What do you mean by "selection"? Polynomials are randomly generated. $\endgroup$ – Artjom B. Jan 20 '16 at 22:34
  • $\begingroup$ 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 $\endgroup$ – chisky Jan 20 '16 at 22:39

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:

enter image description here

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.

| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – chisky Jan 20 '16 at 23:18
  • $\begingroup$ for the coding. I plan to use a python library called Charm as my knowledge of C isnt that good $\endgroup$ – chisky Jan 20 '16 at 23:19
  • $\begingroup$ "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)$. $\endgroup$ – Artjom B. Jan 20 '16 at 23:21
  • $\begingroup$ 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. $\endgroup$ – Artjom B. Jan 20 '16 at 23:23
  • $\begingroup$ Thats good to know. Got it installed yesterday. Will look at the documentation. Thanks for your help $\endgroup$ – chisky Jan 21 '16 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.