Secret Sharing Schemes
A secret sharing
scheme is a method via which a secret, commonly a cryptography
key, is divided into multiple parts called shadows
or shares and distributed to a collection of individuals. The agency
responsible for performing the division is often called the dealer,
and in many sharing schemes it is assumed that the dealer is
perfectly honest. In the simplest schemes, the secret is divided
into N shares
and can only be recovered by
gathering
all N together at once; i.e. an (N,N) scheme. This has the advantage
that it takes all of the participants to recover the secret, but
if any of the shares are lost, the secret is also lost. For this
reason,
many
secret sharing mechanisms are based on a (k, N) threshold mechanism
in which the secret is divided into N shares, but can be totally
recovered from any k (k<N) shares. Moreover,
knowledge of k-1 shares
should ideally
provide no more information than that known from a single share
(see definition of perfect sharing schemes). That is, the difficulty
of any attack including brute force should be the same regardless
of
how many
shares are
known
up
until the
threshold k is reached. These threshold mechanisms
are weaker in terms of security than methods requiring all shares,
but offer the ability
to recover
if
several
shares are lost. A final variant on secret sharing schemes occurs
when you have a (k, N) threshold scheme but somehow divide the
participants into authorized sets of k members such that the
key can only be recovered if all the participants contributing
shares actually form one of the authorized sets. Thus, not all
sets of k shares must yield the key. It turns out that this last
variant is the most general in scope as it encompasses the simple
scheme mentioned at the beginning when k=N and the prior (k,N)
scheme when all possible combinations of k shares form an authorized
set; therefore, this scheme is actually used in many papers as
the formal definition of a sharing scheme. Finally, the following
terms are used in the literature to clarify the nature of schemes:
- Trivial Secret
Sharing
Trivial secret sharing occurs when the secret is simply
divided N pieces and all N are required to rebuild it. This simplest
way
to accomplish this is to give out N-1 random numbers and one number
which is the difference between the secret and the sum of all the
shares
(Sn = K - (S1+S2+...+Sn-1)). Thus, the secret can be found by adding
up all N of the shares. Note that this can be done in binary by
replacing addition and subtraction with XOR.
- Perfect
Schemes
An m-out-of-n
secret sharing scheme is said to be perfect if any group of at
most m-1 participants (insiders) cannot determine more information
about the secret than an outsider. According to the article
on Ideal
Non-Perfect Secret Sharing Schemes by Pascal Pailler et. al.
linked below, a scheme is only perfect when this above condition
is enforced by "information-theoretic" concerns. As far as I
can tell this means that the robustness of the algorithm is enforced
by mathematical proof. This differs from non-perfect methods
in which the condition is guaranteed only by the computational
difficulty of recovering the secret with less than
m shares in a reasonable timeframe. Non-perfect schemes may eventually
be
broken
in sensible
times
as computing power grows. However, they are often easier/faster
to implement and require smaller sized shares.
- Ideal
Schemes
Perfect sharing schemes require the size of the individual
shares to be as large as the secret or larger. However, the longer
the
share is the harder it is to remember and this may cause security
problems if a participant writes down the key. Moreover, the larger
the share, the greater the amount of memory and processing power
needed to manipulate the shares. An ideal secret sharing scheme
is one in which the size of a share is exactly equal to the size
of the key. That is, the size of the shares is kept at the bare
minimum.
- Verifiable Schemes
Verifiable
schemes seek to prevent individuals from lying about their share
in order to obtain information about the other shares. According
to the Wikipedia entry, verifiable schemes allow
the participants to be certain that no other participant
is lying about the contents of their share, up to a reasonable
probability
of error. Presumably the chance of error is slight enough that
it is unlikely any of the participants could cheat the system.
The multiparty computing system created by Tal
Rabin and Michael Ben-Or allows players to detect dishonesty
on the part of the participants and the dealer. This makes these
schemes ideal for situations where nobody trusts anyone else.
- Proactive Schemes
Proactive
schemes seek to make the secret sharing mechanism more secure
in an insecure environment by regularly updating the shares.
The idea is that it takes some effort on the part of an attacker
to get/locate each share and before they can obtain the threshold
number, all of them will have been actively changed/overwritten
in such a way that the old shares cannot be used in conjunction
with the new set and copies of the old set can no longer be found.
- Visual Schemes
Visual
secret sharing schemes differ significantly from the other techniques
described here and fall more into the area of stenography. In
a visual secret sharing scheme, the secret is placed into an
image that is divided into pixels or a grid. The
shares
are then built onto transparencies from the grid using what
seem to be totally random pixels. However, when all of the shares
are overlapped,
the original
secret is revealed. For more information see:
Project Code and Proposal
Note, all the components are listed for each program. If the names
match, the code is actually identical.
- Project
Specification as a word document.
- Encoder
- Decoder
- Simple Server
- Get Shares
Client
- Send Shares
Client
Links to Related Web Sites
|
