Skip to main content
Engineering LibreTexts

3.1: Definitions

  • Page ID
    7327
  • Definition \(\PageIndex{1}\): Secret-Sharing

    A t-out-of-n threshold secret-sharing scheme (TSSS) consists of the following algorithms:

    • Share: a randomized algorithm that takes a message \(m \in ?\) as input, and outputs a sequence \(s = (s_1,. . . ,s_n)\) of shares.
    • Reconstruct: a deterministic algorithm that takes a collection of \(t\) or more shares as input, and outputs a message.

    We call \(?\) the message space of the scheme, and \(t\) its threshold. As usual, we refer to the parameters/components of a scheme \(\Sigma\) as \(\Sigma.t, \Sigma.n, \Sigma.?, \Sigma.Share, \Sigma.Reconstruct.\)

    The correctness property for such a scheme is that any subset of at least \(t\) shares is enough to reconstruct the message \(m\). That is, for all sets \(U \subseteq \{1,. . . ,n\}\) with \(|X| \ge t\) and for all \(s \leftarrow \text{Share(}m)\), we have Reconstruct (\((s_i)_{i \in U} ) = m\).

    In typical usage, then shares are distributed to \(n\) different users. In the above definition, the set \(U\) corresponds to a set of users. If \(|U| \ge t\), we say that the set is authorized; otherwise the set is unauthorized.

    Just like the encryption definition does not address the problem of key distribution, the secret-sharing definition does not address the problem of who should run the Share algorithm (if its input \(m\) is so secret that it cannot be entrusted to any single person), nor of how the shares are meant to be sent securely to the \(n\) different users. Those concerns are considered out of scope by the problem of secret-sharing (although we later discuss clever approaches to the first problem). Rather, the focus is simply on whether it is even possible to encode data in such a way that it can be recovered (only) if a threshold number of shares are present.

    Security Definition

    We’d like a security guarantee that says something like:

    if you have an unauthorized set of shares, then you learn no information about the choice of secret message.

    To translate this informal statement into a formal security definition, we follow the The Central Principle of Security Definitions\(^{\text{TM}}\) and define two libraries that allow the calling program to learn a set of shares (for an unauthorized set), and that differ only in which secret is shared. If the two libraries are interchangeable, then we conclude that seeing an unauthorized set of shares leaks no information about the choice of secret message. The definition looks like this:

    Definition \(\PageIndex{2}\): TSSS Security

    Let \(\Sigma\) be a threshold secret-sharing scheme. We say that \(\Sigma\) is secure if \(\mathscr{L}^{\Sigma}_{tsss-L} \equiv \mathscr{L}^{\Sigma}_{tsss-R}\), where:

    Screen Shot 2019-02-16 at 1.23.22 PM.png

    In an attempt to keep the notation uncluttered, we have not written the type of the argument \(U\), which is \(U \subseteq \{1,. . . ,\Sigma.n\}\).

    Discussion

    • Similar to the definition of one-time secrecy of encryption, we let the calling program choose the two secret messages that will be shared. As before, this models the fact that an adversary may have partial knowledge or influence over what inputs might be used in the secret-sharing scheme.
    • The calling program also chooses the set \(U\) of users’ shares to obtain. The libraries make it impossible for the calling program to obtain the shares of an authorized set (returning err in that case).
    • Consider a 6-out-of-10 threshold secret-sharing scheme. With the libraries above, the calling program can receive the shares of users {1,. . . ,5} (an unauthorized set) in one call to QUERY, and then receive the shares of users {6,. . . ,10} in another call. It might seem like the calling program can then combine these shares to reconstruct the secret (if the same message was shared in both calls). However, this is not the case because these two sets of shares came from two independent executions of the Share algorithm. Shares generated by one call to Share should not be expected to function with shares generated by another call, even if both calls to Share used the same secret message.
    • The calling program sees shares corresponding to the same set of users in both libraries. Recall that interchangeable libraries hide their internal differences. In this case, the set of users is the same in the two libraries, so the security definition does not require shares to hide the identity of the users they belong to. Only the secret message needs to be hidden according to this definition. Indeed, if each user’s identity were appended to his/her corresponding share, it would have no effect on whether \(\mathscr{L}^{\Sigma}_{tsss-L} \equiv \mathscr{L}^{\Sigma}_{tsss-R}\).

    One could certainly write a security definition that required shares to be “anonymous” in this way, hiding the identity of their associated user. This could be accomplished by having the calling program provide two sets \(U_L\) and \(U_R\), with the two libraries using different sets.\(^{[1]}\) The result would be a perfectly reasonable definition, it just wouldn’t be the most standard one used to describe secret sharing. In many applications of secret sharing, it is in fact very convenient to give different users very different-looking kinds of values as their shares.

    Reference

    1. These two sets would have to be the same size, since we cannot disguise the number of shares being returned by the QUERY subroutine.