While reading Attribute Based Encryption Schemes, I did not quite understand what a monotonic access structure or non monotonic access structures are.

Is there a popular explanation of those terms ? any references ?


Simply speaking, if any superset of the set satisfying the access structure satisfies the access structure, we call the structure monotonic.

Let $\{1,2,...,n\}$ be a set of indices. An access structure is a collection $\mathbb{A}$ of non-empty subsets of $\{1,2,3,...,n\}$. We say a collection (or an access structure) $\mathbb{A} \subseteq 2^{\{1,2,...,n\}}$ is monotonic if for any $B,C \in 2^{\{1,2,...,n\}}$, if $B \in \mathbb{A}$ and $B \subseteq C$ then $C \in \mathbb{A}$.

As a concrete example, let us consider $\{1,2,3,4\}$.

  • $((1,2,3),(1,2,4),(1,3,4),(2,3,4),(1,2,3,4))$ is monotonic, which corresponds to 3-out-of-4-threshold.
  • $((1,2),(3,4))$ is non-monotonic, because $(1,3,4)$ is not included.

I borrowed this definition from Beimel's thesis and Rafail Ostrovsky and Amit Sahai and Brent Waters:Attribute-Based Encryption with Non-Monotonic Access Structures.


My understanding of this is as follows:

  • Monotonic access structure: if $\mathbb{A}$ is a set of attributes satisfying an access structure $T$, then any $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ also satisfies $T$. For example, consider $T = A \cap B$, then both $\mathbb{A}=\{A,B\}$ and $\mathbb{A}'=\{A,B,C\}$ satisfy $T$.
  • Non-monotonic access structure: there exists $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ and $\mathbb{A}'$ does not satisfy $T$. For example, consider $T = A \cap \neg C$. Then in the previous example, only $\mathbb{A}$ satisfies $T$.

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.