3.1: Definitions
- Page ID
- 7327
We begin by introducing the syntax of a secret-sharing scheme:
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 \mathcal{M}\) as input, and outputs a sequence \(s=\left(s_{1}, \ldots, s_{n}\right)\) of shares.
- Reconstruct: a deterministic algorithm that takes a collection of \(t\) or more shares as input, and outputs a message.
We call \(\mathcal{M}\) 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 . \mathcal{M}, \Sigma\).Share, \(\Sigma\).Reconstruct.
In secret-sharing, we number the users as \(\{1, \ldots, n\}\), with user \(i\) receiving share \(s_{i}\). Let \(U \subseteq\{1, \ldots, n\}\) be a subset of users. Then \(\left\{s_{i} \mid i \in U\right\}\) refers to the set of shares belonging to users \(U\). If \(|U| \geqslant t\), we say that \(U\) is authorized; otherwise it is unauthorized. The goal of secret sharing is for all authorized sets of users/shares to be able to reconstruct the secret, while all unauthorized sets learn nothing.
At-out-of-n TSSS satisfies correctness if, for all authorized sets \(U \subseteq\{1, \ldots, n\}\) (i.e., \(|U| \geqslant t\) ) (TSSS correctness) and for all \(s \leftarrow \operatorname{Share}(m)\), we have Reconstruct \(\left(\left\{s_{i} \mid i \in U\right\}\right)=m\).
Security Definition
We’d like a security guarantee that says something like:
if you know only 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 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:
Let \(\sum\) be a threshold secret-sharing scheme. We say that \(\sum\) is secure if \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}^{\Sigma} \equiv \mathcal{L}_{\mathrm{tsss}-\mathrm{R}}^{\Sigma}\), where:
In an attempt to keep the notation uncluttered, we have not written the type of the argument \(U\), which is \(U \subseteq\{1, \ldots, \Sigma . n\}\)
Discussion & Pitfalls
- 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 an attack scenario in which the adversary has partial knowledge or influence on the secret \(m\) being shared.
- 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). This does not mean that a user is never allowed to distribute an authorized number of shares (this would be strange indeed, since it would make any future reconstruction impossible). It just means that we want a security definition that says something about an attacker who sees only an unauthorized set of shares, so we formalize security in terms of libraries with this restriction.
- Consider a 6-out-of-10 threshold secret-sharing scheme. With the libraries above, the calling program can receive the shares of users \(\{1, \ldots, 5\}\) (an unauthorized set) in one call to SHARE, and then receive the shares of users \(\{6, \ldots, 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.
- Recall that in our style of defining security using libraries, it is only the internal differences between the libraries that must be hidden. Anything that is the same between the two libraries need not be hidden. One thing that is the same for the two libraries here is the fact that they output the shares belonging to the same set of users \(U\). This security definition does not require shares to hide which user they belong to. Indeed, you can modify a secret-sharing scheme so that each user’s identity is appended to his/her corresponding share, and the result would still satisfy the security definition above.
- 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), or how the shares should be delivered 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 an unauthorized set of shares gives no information about the secret, while any authorized set completely reveals the secret.
An Insecure Approach
One way to understand the security of secret sharing is to see an example of an "obvious" but insecure approach for secret sharing, and study why it is insecure. Let’s consider a 5-out-of- 5 secret-sharing scheme. This means we want to split a secret into 5 pieces so that any 4 of the pieces leak nothing. One way you might think to do this is to literally chop up the secret into 5 pieces. For example, if the secret is 500 bits, you might give the first 100 bits to user 1 , the second 100 bits to user 2 , and so on.
It is true that the secret can be constructed by concatenating all 5 shares, and so this construction satisfies the correctness property. (The only authorized set is the set of all 5 users, so we write Reconstruct to expect all 5 shares.)
However, the scheme is insecure (as promised). Suppose you have even just 1 share. It is true that you don’t know the secret in its entirety, but the security definition (for 5out-of- 5 secret sharing) demands that a single share reveals nothing about the secret. Of course knowing 100 bits of something is not the same as than knowing nothing about it.
We can leverage this observation to make a more formal attack on the scheme, in the form of a distinguisher between the two \(\mathcal{L}_{\mathrm{tsss}-\star}\) libraries. As an extreme case, we can distinguish between shares of an all- \(-\) secret and shares of an all- 1 secret:
Let’s link this calling program to both of the \(\mathcal{L}_{\mathrm{tsss}-\star}\) libraries and see what happens:
|
|
When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{tsss}-\mathrm{L}}\), it receives a share of \(0^{500}\), which will itself be a string of all zeroes. In this case, \(\mathcal{A}\) outputs 1 with probability \(1 .\) |
|
|
When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\mathrm{tsss}-\mathrm{R}, \text { it }}\) receives a share of \(1^{500}\) which will be a string of all ones. In this case, \(\mathcal{A}\) outputs 1 with probability \(0 .\) |
We have constructed a calling program which behaves very differently (indeed, as differently as possible) in the presence of the two libraries. Hence, this secret-sharing scheme is not secure.
Hopefully this example demonstrates one of the main challenges (and amazing things) about secret-sharing schemes. It is easy to reveal information about the secret gradually as more shares are obtained, like in this insecure example. However, the security definition of secret sharing is that the shares must leak absolutely no information about the secret, until the number of shares passes the threshold value.