Lecture notes by Michael Frei
In our last lecture on secret sharing we talked about how to use secret sharing in building an online service in general, where the service maintains a certain secret. The objective is to achieve both availability and confidentiality of the secret.
Replication is a standard approach to improving availability of an online service. However, replication of a secret increases vulnerability, and thus it is easy to see how secret sharing could be beneficial in such a distributed system.
In this class, we assume the following failure model. A server may
crash or may be broken into by an attacker. The attacker may steal information
from the server it breaks into, but is unable to modify the states or the
code of that server (there are mechanisms that deal with more powerful
adversaries where an adversary can modify a corrupted server in any arbitrary
way. We assume this more benign case to simplify the discussion).
A server is compromised if the server either crashes or is broken
Our objective is to design the on-line service that could tolerate
t-1 compromised servers.
Secret sharing in an online environment introduces new concerns. In an
(n,t) sharing scheme, it only takes (
servers to be compromised before an attacker can obtain access to the secret.
Thus, an attacker might eventually gain access to any secret given enough
time to break into t machines.
Suppose the service is going to run for 5 years, the adversary has
5 years to compromise
t servers in order to overthrow the
To counteract this,
the idea of a proactive secret sharing (PSS) scheme was introduced.
In an execution of PSS, servers generate new shares from old ones and delete
the old ones.
The secret is never reconstructed during the entire process. The new shares
are independent of the old ones and constiture a new
sharing of the same secret
s. (refer to
Secret Sharing lecture )
By executing of PSS at intervals, we seek to reduce the time period during
which the adversary has to compromise t servers in order to discover the
secret. For example, with periodic execution of PSS every month, the
adversary has to compromise
t servers within a month
(between two executions
of PSS) in order to obtain the secret (more precisely, between the start of a
PSS to the end of the next PSS). The previous lecture contains a much more
detailed explanation of our PSS scheme.
With this concrete example, we have to worry about how such a replicated service uses the shares to perform its operations. In the online CA case, the operation is to sign a certain message (a CRL, a certificate, or a validation confirmation of a certicate).
Well, we know that, with an
servers can get together and reconstruct the secret (i.e., the private key of
the CA). However,
no server can construct the private key on-the-fly and then use the private
key to sign a message. Otherwise, if the server is compromised after collecting
the shares, then the private key of the service is disclosed, which would
imply that the service cannot tolerate even a single compromised server.
We need a scheme for the servers to sign a message without recovering the private key first. We have been using simple and specific examples to illustrate the fundamental ideas of various concepts. This time, we actually try a different approach: let's generalize the idea first.
In abstraction, what we need is still a sharing of a secret
However, we are not interested in the capability of these parties to
recover the secret. Instead, we are interested in applying a certain
fs) on any input
m using the secret
We are in fact constructing a sharing of
So, this variation of secret sharing is also called function sharing.
In the case of the CA, the function
f is to generate a signature
from a message
m using a private key
(n,t) function sharing of function
f with respect
to a secret
s should achieve the following properties:
>= t) out of
nparties get together, they can generate
fs(m)for any possible input
m, which means they can apply the function
< t) out of
nparties get together, they cannot generate
fsfor an arbitrary input
Usually, function sharing is performed in the same manner as secret sharing:
s is divided into
n shares, one for each party.
In addition, function sharing provides a function
Now, instead of recovering the secret from the
n parties may be asked to perform function
f on a certain input.
So, instead of submitting the shares to recover the secret, each party
i applies function
g on the input
m using its share
si and submit
g(si, m). These results are called
The partial results have the property that: with at least
fs(s) can be computed; otherwise,
fs(m) cannot be constructed. A function sharing
scheme provides another function
g' that generates the
final result (
Let's illustrate the feasibility of function sharing through a very simple
example. Suppose we have a secret
s and want to share function
fs(m)= ms for any input
Let's say we want to construct a
Three components of function sharing:
gto compute partial results using shares
g'to generate the final result from 2 partial results
Here is how we generate the two shares: we randomly select shares
s2 so that
s = s1 + s2.
As we have shown in the last class, these two shares
(2,2) sharing of
Now we give these two shares to two parties and would like the two parties to
fs for an input
without reconstructuring s. Let
= msi and
=x * y.
For an input
g(m, s1) = ms1.
g(m, s2) = ms2.
we can easily compute
ms = g'(ms1,
ms2) = ms1 * ms2.
We have to be very careful here: not all functions can be shared. We may not
be able to disclose partial results in certain cases if shares or
the secret can be inferred from these partial results. More specifically,
s and the shares should not be disclosed during the
entire process of applying the function.
That corresponds to requiring both
g to be one-way
functions(e.g., signing a message is such an function).
If we re-represent the example in a certain finite field (i.e., doing modular
ms mod N , where
N satisfy certain properties), then the scheme would satisfy
After more than a decade of research, researchers have found threshold cryptography schemes for most popular public key cryptography schemes such as discrete-logarithm-based public key crypto schemes (e.g., DSS: Digital Signature Standard) and schemes such as RSA. We are not going to give details for these schemes -- this requires deeper understanding of the specific public key crypto schemes. In fact, the threshold RSA scheme has a similar flavor as the example we just gave.
Now go back to our CA. We can now use a threshold cryptography scheme.
The scheme provides a way to split the private key into
shares and give one share to one server.
The scheme also provides a function
g to compute
partial results (partial signature to generate signatures)
and a function
g' to generate the final result (signature or
decrypted message) from partial results.
Here is how servers generate a signature for a given input
(sent to every server).
generates a partial signature
g(m, si), where
si is the share held by the server.
i then broadcasts the partial signature to all other
When a server collects
t partial signatures, according to the
of function sharing, it can compute
(i.e. the signature of
m signed by the private key of the CA)
Proactive schemes can also be constructed for threshold cryptography. The idea is the same as PSS, where the servers refresh their shares without reconstructing the private key. Servers perform proactive threshold cryptography scheme periodically to enhance the security of the on-line CA.
Now we have this replicated online CA that can tolerate
compromised servers (
n >= 2t+1) within a short period of
time (between executions of the proactive scheme).
The service can sign certificates (or CRLs) online without disclosing any