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.

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

I'm reading this article, CP-ABE with constant-size keys for lightweight devices and in the Table 1, are there these access structure: Threshold, Tree, ($n$,$n$)-Threshold, LSSS, AND gates. I have 2 questions.

1) What are the differences between these access structures ?

2) How can i measure the performance of a scheme in a network ? (i.e scalability, number of users (producers and consumers) supported, number of contents supported) [If this question is off topic, i will remove it].

share|improve this question
    
Your second question doesn't seem to be much related to the first one, because the access structure doesn't have much to do with scalibility, number of users or number of ciphertext. So it would be advisable to ask it separately. If you do, use at most three specific schemes as examples. By the way, the ciphertext or secret key size depends on the access structure. – Artjom B. Feb 2 at 22:26
up vote 0 down vote accepted

Let's assume that we're talking about monotonic access structures (without negated attributes in the policy).

A Threshold policy was introduced in Sahai, Amit, and Brent Waters. "Fuzzy identity-based encryption." Advances in Cryptology–EUROCRYPT 2005. Springer Berlin Heidelberg, 2005. 457-473. (link)

It means that a user secret key and the ciphertext are both associated with (possibly) different attribute sets. Decryption would only work if the overlap between the two sets is at least as large as the globally defined threshold (during setup). Here we don't distinguish between Key-policy ABE and Ciphertext-policy ABE.

An $(n,n)$-Threshold access structure is the same as AND gates. The later approaches usually use Shamir's Secret Sharing (SSS) with a variable threshold value $t$ as a $(t,n)$-scheme. If we require all shares to be present, then this essentially means that a single AND gates with $n$ attributes was used. Now, the authors chose to call it $(n,n)$-Threshold, because the attributes can be multi-valued (wildcards). This goes into the realm of Hidden Vector Encryption and non-monotonic access structures, even there it's still usually called AND gate.

The Tree approach was first described in Goyal, Vipul, et al. "Attribute-based encryption for fine-grained access control of encrypted data." Proceedings of the 13th ACM conference on Computer and communications security. Acm, 2006. (link)

It is a way of sharing a secret element across the attributes of a policy (KP-ABE or CP-ABE), which can then be reconstructed with Lagrange interpolation. See my answer here for more information. The construction of Goyal et al. permits not only AND and OR gates, but arbitrary threshold gates with SSS for every node of the tree. It is also fairly easy to build up the access tree from a textual representation such as a boolean formula.

Of course, there are other constructions that don't support arbitrary trees. For example Müller, Sascha, Stefan Katzenbeisser, and Claudia Eckert. "Distributed attribute-based encryption." Information Security and Cryptology–ICISC 2008. Springer Berlin Heidelberg, 2008. 20-36. (link) supports policies only written in a Disjunctive Normal Form (DNF).

A Linear Secret Sharing Scheme (LSSS) works on a matrix, where the rows are labelled with attributes of the policy, to produce shares from a secret element. This should be familiar as the outcome is the same as for the Tree access structure. In fact, when you implement a scheme, most of the time you can exchange an LSSS approach for a Tree approach, but that doesn't mean that it's secure anymore, because the security games and used assumptions may depend on a specific approach and may not work for the other.

If you're looking to convert a boolean formula to an LSSS matrix, then this is getting a little tricky, because it is not immediately apparent how this can be done. You can check with Lewko, Allison, and Brent Waters. "Decentralizing attribute-based encryption." Advances in Cryptology–EUROCRYPT 2011. Springer Berlin Heidelberg, 2011. 568-588. (link) to create an LSSS matrix from a boolean formulas, which use only AND and OR gates. Then Liu, Jian, Sihem Mesnager, and Lusheng Chen. "Secret Sharing Schemes with General Access Structures (Full version)." (link) present a way to use general boolean formulas (with threshold gates).


This was only a small number of access structures. Other notable mentions are Monotone Span Programs (highly related to LSSS), Branching Programs and Circuits (used in Lattice-based ABE constructions).

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.