What are monotonic and non monotonic access structures in ABE ?

Question

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 ?

Answer 1

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.

Answer 2

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$.