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].
Let's assume that we're talking about monotonic access structures (without negated attributes in the policy).
A Threshold policy was introduced by Amit Sahai and Brent Waters in "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, Katzenbeisser and 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, Cao and Wong. "Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees" (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).
