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 1
Previous Page Next Page