1
$\begingroup$

The set of authorized subsets of participants is called an access structure.

In a multipartite access structure, the set of participants is divided into several parts and all participants in the same part play an equivalent role.

In the 12th line of abstract of this paper, it is given that every access structure is multipartite, I am getting confusion regarding this statement. How to understand that every access structure is a multipartite access structure?

$\endgroup$

1 Answer 1

2
$\begingroup$

From p5 of the paper:

An $r$-partition $\Omega = \{P_1,\ldots,P_r\}$ of a set $P$ is a disjoint family of non-empty subsets of $P$ with $P=P_1 \cup \ldots \cup P_r$. ... A family of subsets $\Lambda \subseteq \mathcal{P}(P)$ is said to be $\Omega$-partite if $\sigma(\Lambda)=\Lambda$ for every permutation $\sigma$ such that $\sigma(P_i) = P_i$ for every $P_i \in \Omega$.

Thus any access structure $\Lambda$ on $n$ parties is trivially an $n$-partite access structure: take the $n$-partition $\Omega = \{\{1\},\ldots,\{n\}\}$; then for any $\sigma$ fixing all sets in the partition (which is only the identity permutation), it holds that $\sigma(\Lambda) = \Lambda$. Since $\Omega$ contains $n$ partitioning sets, $\Lambda$ is an $n$-partite access structure.

The abstract also says that Shamir's scheme is unipartite. This is by taking the partition $\Omega = \{\{1,\ldots,n\}\}$, which is a $1$-partition, since for every permutation fixing all sets in the partition (which is every permutation) it holds that $\sigma(\Lambda) = \Lambda$. This is because of the symmetry in Shamir's scheme: every party can be swapped with any other party and you still have "all subsets of $\{1,\ldots,n\}$ of size at most $t$".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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