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
into.
Our objective is to design the on-line service that could tolerate
up to `t-1`

compromised servers.

Secret sharing in an online environment introduces new concerns. In an
`(n,t) `

sharing scheme, it only takes (`>= t`

)
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
service.

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 `(n,t) `

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 `(n,t)`

sharing, `t`

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 `s`

among `n`

parties.
However, we are not interested in the capability of these parties to
recover the secret. Instead, we are interested in applying a certain
function (e.g., `f`

) on any input
_{s}`m`

using the secret `s`

.
We are in fact constructing a sharing of `f`

.
So, this variation of secret sharing is also called _{s}*function sharing*.
In the case of the CA, the function `f`

is to generate a signature
from a message `m`

using a private key `k`

.

An `(n,t)`

function sharing of function `f`

with respect
to a secret `s`

should achieve the following properties:

- if (
`>= t`

) out of`n`

parties get together, they can generate`f`

for any possible input_{s}(m)`m`

, which means they can apply the function`f`

_{s} - if (
`< t`

) out of`n`

parties get together, they cannot generate`f`

for an arbitrary input_{s}`m`

.

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 `g`

.
Now, instead of recovering the secret from the
shares, 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 `s`

and submit
the result _{i}`g(s`

. These results are called
_{i}, m)*partial results*.

The partial results have the property that: with at least `t`

partial results, `f`

can be computed; otherwise,
_{s}(s)`f`

cannot be constructed. A function sharing
scheme provides another function _{s}(m)`g'`

that generates the
final result (`f`

) from _{s}(m)`t`

partial
results.

Let's illustrate the feasibility of function sharing through a very simple
example. Suppose we have a secret `s`

and want to share function
`f`

for any input _{s}(m)= m^{s}` m`

.
Let's say we want to construct a `(2,2)`

sharing.

Three components of function sharing:

- How to split the secret into shares
- Function
`g`

to compute partial results using shares - Function
`g'`

to generate the final result from 2 partial results

Here is how we generate the two shares: we randomly select shares
`s1`

and `s2`

so that `s = s1 + s2`

.
As we have shown in the last class, these two shares
constitute a `(2,2)`

sharing of `s`

.

Now we give these two shares to two parties and would like the two parties to
compute function `f`

for an input _{s}`m`

without reconstructuring s. Let `g(m, s`

and
_{i})
= m^{si}```
g'(x,y)
=x * y
```

.

For an input `m`

,

- Party 1 computes partial result
`g(m, s`

._{1}) = m^{s1} - Party 2 computes partial result
`g(m, s`

._{2}) = m^{s2} - Party 1 and party 2 submit
`m`

and^{s1}`m`

.^{s2}

With both `m`

and ^{s1}`m`

,
we can easily compute ^{s2}`m`

.
^{s} = g'(m^{s1},
m^{s2}) = m^{s1} * m^{s2}

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,
the secret `s`

and the shares should not be disclosed during the
entire process of applying the function.
That corresponds to requiring both `f`

and
`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
exponentiation ` m`

, where ^{s} mod N `s`

and
`N`

satisfy certain properties), then the scheme would satisfy
this requirement.

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 `n`

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 `m`

(sent to every server).

Each server `i`

generates a partial signature `g(m, s`

, where
_{i})`s`

is the share held by the server.
Server _{i}`i`

then broadcasts the partial signature to all other
servers.

When a server collects `t`

partial signatures, according to the
property
of function sharing, it can compute `{m}`

(i.e. the signature of _{s}`m`

signed by the private key of the CA)
using function `g'`

.

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 `t`

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
secret information.