Geometrical contributions to secret sharing theory (Q1879097)

This is a nice survey on geometric secret sharing schemes. The basic idea behind a geometric scheme is to implement a secret sharing scheme in a finite projective geometry in such a way that the secret \(s\) is represented by a subspace \(s^{\sigma}\) and also each participant's share corresponds to a subspace. For any given access structure \(\Gamma\subseteq 2^{\mathcal{P}}\) on a finite set \(\mathcal{P}\) of participants, and any given prime power \(q\), it is possible, for certain \(d\), to assign subspaces \(p^{\sigma}\subseteq \mathbb{P}^d(\mathbb{F}_q)\) to all participants \(p\in\mathcal{P}\) in such a way that for all \(A\subseteq\mathcal{P}\), \[ A\in\Gamma\Longrightarrow A^{\sigma}\supseteq s^{\sigma},\quad A\not\in \Gamma\Longrightarrow A^{\sigma}\cap s^{\sigma}=\emptyset, \] where \(A^{\sigma}\) is the subspace spanned by the subspaces \(p^{\sigma}\) for \(p\in A\). This condition allows the implementation of a secret sharing scheme with access structure \(\Gamma\), via distribution rules. The survey reviews some classical secret sharing schemes that can be fit into this geometrical scheme. It discusses then some measures of efficiency of geometric schemes. If \(c_p=(\dim p^{\sigma}+1)/(\dim s^{\sigma}+1)\), the information rate \(\rho\) and the average information rate \(\tilde{\rho}\) are defined as: \[ \rho:=\text{min}_{p\in\mathcal{P}}c_p^{-1},\quad \tilde{\rho}:=n/\left(\sum_{p\in\mathcal{P}}c_p\right). \] They satisfy \(\rho\leq\tilde{\rho}\leq 1\) and a subspace configuration for which \(\rho=\tilde{\rho}=1\) is considered ideal, since the size of the shares are minimum with respect to the size of the secret. A third measure is the randomness coefficient \(\text{rc}=\left(\dim\langle s^{\sigma},\mathcal{P}^{\sigma}\rangle+1\right)/(\dim s^{\sigma}+1)-1\); it is a measure of the size of the ambient projective space with respect to the secret size and is thus a value that is desirable to minimize. Some devices for deriving subspace configurations from a given subspace configuration are then reviewed: restriction, contraction, grouping, dual, repeating, and it is studied how the above efficiency measures are affected by these constructions. The algorithmic approach is also considered and some algorithms for constructing optimal subspace configurations are presented and compared. The state of the art of some classification problems is then recalled: the classification of access structures realizable by ideal subspace configurations, which is related to the existence of certain matroids, and the classification of ideal threshold schemes, related to the existence of certain arcs in projective spaces. Finally, some extended capabilities of secret sharing schemes are studied, like multisecret sharing, homomorphic secret sharing, coping with cheaters, or changing threshold parameters, and it is seen how these capabilities can be provided by geometric constructions too.