Paper 2019/576

Group-homomorphic Secret Sharing Schemes Are Group-characterizable with Normal Subgroups

Reza Kaboli and Shahram Khazaei and Maghsoud Parviz

Abstract

Since the seminal work of Frankel, Desmedt and Burmester [Eurocrypt'92 & Crypto'92] there has been almost no result on the algebraic structure of homomorphic secret sharing schemes. In this paper, we revisit group-homomorphic schemes--- those whose secret and share spaces are groups---via their connection to \emph{group-characterizable random variables} [Chan and Yeung 2002]. A group-characterizable random variable is induced by a joint distribution on the (left) cosets of some subgroups of a main group. It is easy to see that a group-characterizable secret sharing with \emph{normal} subgroups in the main group is group-homomorphic. In this paper, we show that the converse holds true as well. A non-trivial consequence of this result is that total and statistical secret sharing coincide for group-homomorphic schemes. To achieve the above claim, we present a necessary and sufficient condition for a joint distribution to be inherently group-characterizable (i.e., up to a relabeling of the elements of the support). Then, we show that group-homomorphic secret sharing schemes satisfy the sufficient condition and, consequently, they are inherently group-characterizable. We strengthen our result by showing that they indeed have a group characterization with normal subgroups in the main group. Group-characterizable random variables are known to be quasi-uniform (namely, all marginal distributions are uniform). As an additional contribution, we present an example of a quasi-uniform random variable which is not inherently group-characterizable.

Note: Minor editorial changes compared with the previous version.