# Number of possible access structure with $n$ person

I want to count number of possible access structures in closed form(if possible) as a variable of $n$,the number of share holder. I have tried in several ways. Still no good progress. It is very hard to consider all cases and count it and I think there will be work by others on approximating the number. Is there any approximation of that count so that I can get some idea ?

All possible access contains $(k,n)$ - Secret sharing scheme( general access structures). Can anyone give any idea how to proceed?

Example: In General access structure, we will call the set of collection of all people who can get the secret by $\Gamma_{qual}$ . Consider a case of $n=5$ , we have to consider the case like $$\Gamma_{qual}= \{\{1,2\},\{2,4\},\{1,3,5\}\}$$ but we can't have an access structure where a shareholder is not present, means we always need $$\cup_{X\in \Gamma_{qual}}X = \{1,2,\cdots,n\}$$

• Your number of share holder condition is unnatural if you are doing a global count. – kodlu Jul 8 '18 at 15:37

An access structure is just a function $f:\{0,1\} ^n\to \{0,1\}$. It takes a subset of $\{1,\ldots,n\}$ as input (represented as it's characteristic vector) and returns 1 if authorized and 0 if unauthorized. Additionally, the function must be monotone, meaning that $A\subseteq B \implies f(A) \le f(B)$.

The number of monotone Boolean functions over $n$ variables is given by the Dedekind numbers (OEIS). It is a nontrivial formula!

Edit: You are interested in $f$ which are sensitive to all $n$ inputs. Let's call $f$ insensitive to input $i$ if there is a function $g$ (defined on subsets of $\{1,\ldots, i-1,i+1,\ldots,n\}$) such that $f(A) = g(A \setminus \{i\})$ for all $A$. If this is not the case then we say that $f$ is sensitive to $i$. Now say that $f$ is $k$-sensitive if it is sensitive to $k$ of its inputs. You can count the number of $n$-sensitive monotone functions using the inclusion-exclusion principle.

The idea is that $M(n)$ ($n$th Dedekind number) includes things you don't care about like $(n-1)$-sensitive functions. There are ${n \choose 1} M(n-1)$ Monotone functions of $n$ variables that are (at most) $(n-1)$-sensitive, so subtract them off. But since $M(n-1)$ also "overcounts" all the $(n-2)$-sensitive functions, you've subtracted them off too much and need to add them back. There are ${n \choose 2} M(n-2)$ of these. Etc etc etc. You finally get the thing you want as $\sum_{i=0}^n (-1)^i {n \choose i}M(n-i)$.

• But, you need all of them to be present there. For example: $\Gamma_{qual}=\{\{1,2\},\{2,3\}\}$, qualified set, is not an access structure for $4$ people, as $4$ is not present in any one of the subsets. – Taxicab Jul 8 '18 at 9:46
• I am also not getting where you have considered the fact that we also have structures like $\Gamma_{qual}=\{\{1,2\},\{2,3\},\{1,3,4\}\}$ (the minimum qualified set)! – Taxicab Jul 8 '18 at 9:59
• @t.gos there is an approach of a characteristic vector used, that is, if there are 4 people you consider bit vectors of length 4 where position $i$ denotes whether person $i$ is required and the function returns $1$ iff this set of persons eg 1100 ($=\{1,2\}$) is authorized. – SEJPM Jul 8 '18 at 10:34
• @t.gos you require the function to be sensitive to all of its inputs. I updated the response to address this requirement. – Mikero Jul 8 '18 at 20:50
• @Mikero You mean $\sum_{i=0}^n (-1)^i\binom{n}{i} M(n-i)$ ? – Taxicab Jul 9 '18 at 5:16