1
$\begingroup$

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\}$$

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

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)$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Taxicab Jul 8 '18 at 9:46
  • $\begingroup$ 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)! $\endgroup$ – Taxicab Jul 8 '18 at 9:59
  • $\begingroup$ @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. $\endgroup$ – SEJPM Jul 8 '18 at 10:34
  • $\begingroup$ @t.gos you require the function to be sensitive to all of its inputs. I updated the response to address this requirement. $\endgroup$ – Mikero Jul 8 '18 at 20:50
  • $\begingroup$ @Mikero You mean $\sum_{i=0}^n (-1)^i\binom{n}{i} M(n-i)$ ? $\endgroup$ – Taxicab Jul 9 '18 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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