Shamir's Secret Sharing Scheme (SSS) - Java Implementation

Multi-Party Computation (MPC)

Overview

Shamir's Secret Sharing Scheme (SSS) is a cryptographic algorithm that allows a secret to be split into multiple shares. The secret can only be reconstructed when a threshold number of shares are combined together. This Java implementation provides a simple framework for generating shares, distributing them, and reconstructing the original secret.

Key Features

• Splitting a secret into multiple shares
• Reconstructing the secret when enough shares are available
• Modular arithmetic with a large prime modulus
• Secure random number generation for polynomial coefficients

Prerequisites

To use this Shamir's Secret Sharing Scheme implementation, you need the following:

• Java 8 or higher: Make sure you have a JDK installed on your machine. You can download it from the official Oracle website or install it through your package manager.

How It Works

• Secret Sharing: The secret (a BigInteger) is split into n shares, where at least k shares are required to reconstruct the secret. The shares are generated by evaluating a polynomial at different points, with the secret being the constant term of the polynomial.
• Reconstruction: To reconstruct the secret, a minimum of k shares are needed. Lagrange interpolation is used to find the secret from the shares.

Installation

• Clone the repository.

• Compile the project using the javac command.

  javac SSS.java Test.java

• Run the project with the java command:

  java Test

Code Explanation

• Class SSS: This is the main class that implements the Shamir's Secret Sharing Scheme. The class contains several methods to handle different parts of the process, such as generating primes, splitting the secret into shares, and reconstructing the secret.
• Constructor: Initializes the number of shares (n), threshold (k), and generates a large prime number for the modulus. It also initializes an empty list of polynomial coefficients.
• Method genPrime(): Generates a prime number of the specified bit length using a secure random number generator.
• Method setSecret(): Sets the secret as the constant term of the polynomial and generates random coefficients for the other terms in the polynomial.
• Method computeShare(): Calculates the share corresponding to a given x using the polynomial defined by the coefficients.
• Method computeAllShare(): Computes and returns all the shares as a map of share IDs to share values.
• Method reconstructSecret(): Reconstructs the secret using Lagrange interpolation, given at least k shares.