Shamir Secret Sharing

As one alternative to additive secret sharing, Cicada provides Shamir sharing, which supports the same set of mathematical and logical operations. Unlike additive sharing, Shamir’s is a threshold scheme such that for any set of \(n\) players, a threshold \(k\) can be specified where any subset of \(n >= k\) can reveal a secret. To accomplish this, Shamir’s scheme is based on creating and evaluating polynomials over an integral field. To share a secret \(s\) among \(n\) parties with threshold \(k\), a random polynomial with the following form is generated over the field \(\mathbb{Z}_p\), where the \(c\) coefficients are all random field elements:

\[f(x)=(c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_{2}x^{2}+c_{1}x+s)\mod p\]

After construction of the polynomial, the \(c\) coefficients become the shares that are distributed among players. Reconstruction of the secret is accomplished with straightforward Lagrange interpolation. In the following, \(x\) and \(y\) with subscripts have their usual meaning in the context of successive points at which a polynomial is evaluated and the result of that evaluation respectively, and the subscripts denote the position of each within a list of such pairs:

\[s= f(0)=\sum_{j=1}^{n}y_j \prod_{k=1:k\neq j}^{n} \frac{-x_k}{x_j-x_k}\]

Cicada defines two protocol suites that implement Shamir’s scheme: ShamirBasicProtocolSuite supports a subset of operations that work with any \(k \leq n\), while ShamirProtocolSuite provides the full set of operations supported by AdditiveProtocolSuite, albeit with the constraint that

\[k \leq \frac{n+1}{2}\]

Let’s consider an example using ShamirBasicProtocolSuite that doubles a secret value using addition:

[1]:

import logging
logging.basicConfig(level=logging.INFO)

import numpy

from cicada.shamir import ShamirBasicProtocolSuite, ShamirProtocolSuite
from cicada.communicator import SocketCommunicator
from cicada.logging import Logger

def main(communicator):
    log = Logger(logging.getLogger(), communicator)
    protocol = ShamirBasicProtocolSuite(communicator, threshold=3)

    value = numpy.array(2.5) if communicator.rank == 0 else None
    log.info(f"Player {communicator.rank} value: {value}")

    value_share = protocol.share(secret=value, src=0, shape=())
    double_share = protocol.add(value_share, value_share)
    double = protocol.reveal(double_share)

    log.info(f"Player {communicator.rank} doubled value: {double}")

SocketCommunicator.run(world_size=3, fn=main);

INFO:root:Player 0 value: 2.5
INFO:root:Player 1 value: None
INFO:root:Player 2 value: None
INFO:root:Player 0 doubled value: 5.0
INFO:root:Player 1 doubled value: 5.0
INFO:root:Player 2 doubled value: 5.0

Aside from using ShamirBasicProtocolSuite, this is identical to the code you would write to perform the same operation using AdditiveProtocolSuite.

To use multiplication or any operation dependent on multiplication, you must use ShamirProtocolSuite instead. But, as we discussed above, it places stronger constraints on \(k\) … let’s see what happens if we simply substitue ShamirProtocolSuite and try to square our secret value using multiplication:

[2]:

def main(communicator):
    log = Logger(logging.getLogger(), communicator)
    protocol = ShamirProtocolSuite(communicator, threshold=3)

    value = numpy.array(2.5) if communicator.rank == 0 else None
    log.info(f"Player {communicator.rank} value: {value}")

    value_share = protocol.share(secret=value, src=0, shape=())
    square_share = protocol.multiply(value_share, value_share)
    square = protocol.reveal(square_share)

    log.info(f"Player {communicator.rank} squared value: {square}")

SocketCommunicator.run(world_size=3, fn=main);

ERROR:cicada.communicator.socket:Comm world player 0 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')
ERROR:cicada.communicator.socket:Comm world player 1 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')
ERROR:cicada.communicator.socket:Comm world player 2 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')

… the program raises an exception when constructing the ShamirProtocolSuite object, because \(k\) is too large for the given \(n\). We can solve the problem by making \(k\) smaller or \(n\) larger. Let’s try the latter, and re-run the program with five players:

[3]:

def main(communicator):
    log = Logger(logging.getLogger(), communicator)
    protocol = ShamirProtocolSuite(communicator, threshold=3)

    value = numpy.array(2.5) if communicator.rank == 0 else None
    log.info(f"Player {communicator.rank} value: {value}")

    value_share = protocol.share(secret=value, src=0, shape=())
    square_share = protocol.multiply(value_share, value_share)
    square = protocol.reveal(square_share)

    log.info(f"Player {communicator.rank} squared value: {square}")

SocketCommunicator.run(world_size=5, fn=main);

INFO:root:Player 0 value: 2.5
INFO:root:Player 1 value: None
INFO:root:Player 2 value: None
INFO:root:Player 3 value: None
INFO:root:Player 4 value: None
INFO:root:Player 0 squared value: 6.25
INFO:root:Player 1 squared value: 6.25
INFO:root:Player 2 squared value: 6.25
INFO:root:Player 3 squared value: 6.25
INFO:root:Player 4 squared value: 6.25

Thus, Shamir offers straightforward resilience against data loss by allowing a subset of players to reveal data even after some players fail; however, this comes at a cost: it is less resistant to coalitions, since a sufficiently large coalition could reveal a secret that would otherwise remain private using additive sharing. Further, greater care is required to ensure that the number of players and threshold are chosen correctly, depending on the set of operations to be performed.