Cryptology ePrint Archive: Report 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.

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.

Category / Keywords: foundations / homomorphic secret sharing schemes, group-characterizable distribution, quasi-uniform distribution

Date: received 27 May 2019, last revised 7 Jul 2019

Contact author: shahram khazaei at gmail com

Available format(s): PDF | BibTeX Citation

Note: In the previous version it was mentioned that "a non-trivial consequence of this result is that total and statistical secret sharing coincide for group-homomorphic schemes". This claim does not follow from the result of this paper and Theorem 8.7 in

Version: 20190707:134052 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]