A 3D-Cellular Automata-Based Publicly-Verifiable Threshold Secret Sharing

Introduction

Securing information that is flowing on the Internet has become crucial in the past few years. There has been an escalation in the amount of cyber-crime when it comes to an organization's privacy or an individual’s privacy. Cryptographic algorithms like DES (Diffie, & Hellman, 1977) and RSA (Rivest, Shamir, & Adleman, 1978) have been used for encrypting data using keys. However, here the security of information lies in the safety of the keys. Key-management techniques were developed to solve this issue. Secret sharing was one of the techniques that emerged mainly for key management though it has many other applications.

Secret sharing (SS) is composed of two algorithms – the secret sharing algorithm and the reconstruction algorithm. In SS, a dealer generates shares and then distributes them to various participants who then become shareholders. The shares generated are then used to reconstruct the secret. The concept of secret sharing was first formulated independent of each other by Shamir (1979) and Blakley (1979) in 1979. The SS scheme developed were -threshold SS schemes in which a secret is divided among shareholders such that at least or more shareholders are required to reconstruct the secret correctly. It is not feasible to reconstruct the secret if or fewer shares are present. Polynomial arithmetic operations and interpolation form the basis of Shamir's Scheme. The goal was to take points and guarantee that a unique polynomial with those points exists. The interpolation of the missing points corresponding to the polynomial is made possible. Blakley’s scheme, on the other hand, was based on hyperplane intersections instead of polynomial interpolation.

The shareholders in SS belong to various subsets of participants called the access structure. Suppose, is the access structure, then determines the mechanism to share and reconstruct the secret. “Any subset in can reconstruct the secret from its shares, and any subset not in cannot reveal any information about the secret” (Beimel, 2011). Depending upon the access structure, there can be many SS schemes. A hierarchical threshold SS scheme that had a hierarchical access structure was proposed by Tassa (2007). This scheme was based on Birkhoff interpolation and could share one secret.

Shamir’s SS scheme among other commonly used SS mechanisms can be used to distribute only one secret. However, the secret messages are not always small, and they may be huge on certain occasions (Capocelli, Santis, Gargano, & Vaccaro, 1991). There has to be a technique to share more than one secret message among shareholders. In ref. (He, & Dawson, 1994; Blundo, De Santis, Di Crescenzo, Gaggia, &Vaccaro, 1994), multi-secret sharing schemes were proposed. These schemes as mentioned earlier use were based on Shamir's schemes.