Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question
up vote 1 down vote accepted

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.

share|improve this answer
Thank you , can you give the link to Beimel's thesis ? – sashank Jan 2 '13 at 2:41
Beimel's thesis is available at IACR's Ph.D Database – xagawa Jan 2 '13 at 9:57

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$.
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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