Contemporary Mathematics
Volume 633, 2015
Secret sharing using non-commutative groups
and the shortlex order
Bren Cavallo and Delaram Kahrobaei
Abstract. In this paper we review the Habeeb-Kahrobaei-Shpilrain secret
sharing scheme and introduce a variation based on the shortlex order on a free
group. Drawing inspiration from adjustments to classical schemes, we also
present a method that allows for the protocol to remain secure after multiple
secrets are shared.
1. Introduction
Secret sharing is a cryptographic protocol by which a dealer distributes a secret
via shares to participants such that only certain subsets of participants can together
use their shares to recover the secret. A secret sharing scheme begins with a dealer,
a secret, participants, and an access structure. The access structure determines
which groups of participants have access to the secret. The goal of the scheme is to
distribute the secret to the participants in such a way that only sets of participants
within the access structure have access to the secret. In this way, it is most often
the case that no individual participant can recover the secret on their own.
Secret sharing schemes are ideal tools for when the secret is both highly impor-
tant and highly sensitive. The fact that there are multiple shares, as opposed to one
private key in private key cryptography, makes the secret less likely to be lost while
allowing high levels of confidentiality. If any one share is compromised the secret
can generally still be recovered with the non-compromised shares. Additionally,
even though the secret is spread out over multiple shares, recovering the secret is
limited by the access structure, and so the secret remains secure. Secret sharing
has applications in multi-party encryption, Byzantine agreement, and threshold en-
cryption among others. See [1] for a survey on secret sharing and its applications
in cryptography and computer science.
2. Formal Definition
A secret sharing scheme consists of a dealer, n participants,
P1,...Pn, and an
access structure A 2{P1,··· ,Pn} such that for all A A and A B, B A.
To share a secret s, the dealer runs an algorithm:
Share(s) = (s1, · · · , sn)
and then distributes each share si to Pi.
2010 Mathematics Subject Classification. Primary 20F05, 94A60, 20F10.
c 2015 American Mathematical Society
Previous Page Next Page