Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

2 Answers 2

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 iacr.org/phds/index.php?p=detail&entry=548 –  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

 
discard

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.