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

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

Rosemary Koikara (Kyungpook National University, South Korea), Eun-Joon Yoon (Kyungil Univeristy, South Korea) and Anand Paul (Kyungpook National University, South Korea)
DOI: 10.4018/978-1-5225-9611-0.ch013


In secret sharing, a secret is distributed between various participants in a manner that an authorized group of participants in the appropriate access structures can recover this secret. However, a dealer might get corrupted by adversaries and may influence this secret sharing or the reconstruction process. Verifiable secret sharing (VSS) overcomes this issue by adding a verifiability protocol to the original secret sharing scheme. This chapter discusses a computationally secure publicly verifiable secret sharing scheme constructed using the three-dimensional cellular automata (3D CA). The initial configuration of the 3D CA is the secret. The following configurations are devised to be the shares distributed among the participants. Update mechanisms and various rules make it hard for an adversary to corrupt or duplicate a share. To make it even more efficient, the authors added a verifiability layer such that a dealer posts a public share and a private share to each shareholder. The NIST test suite has been used to calculate the randomness of the shares.
Chapter Preview


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 978-1-5225-9611-0.ch013.m01-threshold SS schemes in which a secret 978-1-5225-9611-0.ch013.m02 is divided among 978-1-5225-9611-0.ch013.m03 shareholders such that at least 978-1-5225-9611-0.ch013.m04 or more shareholders are required to reconstruct the secret correctly. It is not feasible to reconstruct the secret if 978-1-5225-9611-0.ch013.m05 or fewer shares are present. Polynomial arithmetic operations and interpolation form the basis of Shamir's Scheme. The goal was to take 978-1-5225-9611-0.ch013.m06 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, 978-1-5225-9611-0.ch013.m07 is the access structure, then 978-1-5225-9611-0.ch013.m08 determines the mechanism to share and reconstruct the secret. “Any subset in 978-1-5225-9611-0.ch013.m09 can reconstruct the secret from its shares, and any subset not in 978-1-5225-9611-0.ch013.m10 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.

Key Terms in this Chapter

Access Structure: The structure that consists of authorized subsets of participants that can take part in the SS.

Secret Message: The information that has to be safeguarded. This information should not come into the hands of adversaries.

Cryptography: The study of securing information such that they are safe from the hands of third parties.

Multiparty Communication: A communication environment that involves two or more parties communicating over a network.

Key-Management: The management of cryptographic keys that are used in a cryptosystem.

Shareholders: The parties taking part in the SS scheme.

Pseudo-Random: A number that satisfies the tests of a random number but that has been generated using mathematical operations.

Share: The secret message that has been processed and distributed among participants.

Complete Chapter List

Search this Book: