# Access tree and Key geneation in KP-ABE

I tried for about 1 month to understand ABE and know I am confusing about access tree. In paper "Attributed-based encryption for fine-grained access control of encrypted data" the author explained the generation of keys with access tree for KP-ABE which I attached the picture of it here.

I found an example for this but some parts in paper are not clear for me.

1) what is the meaning of "threshold value"? Based on the top example, how can I determine this for different nodes?

2) What is the meaning of the index (x)?

Thanks a lot. I appreciate your helps.

1. The threshold value for any node in the tree is the minimum amount of child nodes that is needed for derivation of the secret. For an OR node the threshold value is usually 1 while for an AND node the threshold value is equal to the number of child nodes. For instance from your diagram, the threshold value for the AND node numbered 1 is 2 and the threshold value for the other node is 2. The threshold value for the root node which in your diagram is r will also be 2 because it is an AND node and it has two sub nodes attached to it.

2. index (x) is simply a way to keep track of all the individual nodes that are part of the whole tree so you can evaluate them accordingly i.e according to their position in the overall tree which means being able to identify what child nodes are attached to any certain node and what parent node a particular node is attached to.

Hope this helps.

Access tree $$\mathcal{T}$$. Let $$\mathcal{T}$$ be a tree representing an access structure. Each non-leaf node of the tree represents a threshold gate, described by its children and a threshold value. If $$num_x$$ is the number of children of a node $$x$$ and $$k_x$$ is its threshold value, then $$0 < k_x ≤ num_x$$. (That is, if any $$k_x$$ or more children of node $$x$$ are satisfied, node $$x$$ is satisfied.)

When $$k_x = 1$$, the threshold gate is an OR gate and when $$k_x = num_x$$, it is an AND gate. Each leaf node $$x$$ of the tree is described by an attribute and a threshold value $$k_x = 1$$.

To facilitate working with the access trees, we define a few functions. We denote the parent of the node $$x$$ in the tree by $$\text{parent}(x)$$. The function $$\text{att}(x)$$ is defined only if $$x$$ is a leaf node and denotes the attribute associated with the leaf node $$x$$ in the tree. The access tree $$\mathcal{T}$$ also defines an ordering between the children of every node, that is, the children of a node are numbered from $$1$$ to $$num$$. The function $$\text{index}(x)$$ returns such a number associated with the node $$x$$. Where the index values are uniquely assigned to nodes in the access structure for a given key in an arbitrary manner.

Reference: KP-ABE 2006 Goyal et al. CP-ABE 2007 Bethencourt et al.