Introduction and Motivation

In his will, a man left a safe to his eleven squabbling relatives. To each individual heir, he gave a secret. In his will, he said that if eight or more of his eleven relatives could put aside their differences and pool their resources, they could compute the safe combination from their individual secrets. Otherwise, the safe would remain locked and no one would inherit anything.

In order to execute the will in this parable, a special protocol is required to allow a group of people to share a secret such that a quorum of them can recompute the secret, yet less than that quorum can gain no information. In addition, such a protocol requires the prevention of cheating so that participants are unable to extract more information than they reveal.

A protocol of this nature is called a $(q, n)$ threshold scheme or secret sharing problem. A secret sharing problem in general has the following characteristics:

1. a secret $S$ is divided into $n$ pieces, or shares;
2. knowledge of quorum $q$ or more shares allows $S$ to be easily computed;
3. knowledge of $q-1$ or less pieces reveals no information about $S$.

In addition, it must be assured that participants in the protocol are unable to cheat. The secret sharing problem implicitly assumes that shares will be pooled by the quorum to compute the secret. Various protocols have been created [5,8,1]. Some of these include techniques to catch cheaters who might put bogus values into the shared pool of information. Even if cheaters can be detected, a problem remains since cheaters can still see the contents of the pool before revealing their own shares. A workable protocol must be able to ensure that cheaters cannot see the contents of the pool without first adding their true shares to it. This would ensure that a cheating party could not gain any advantage.

Description

In order to solve a distributed secret sharing problem, a $(q, n)$ threshold scheme can be implemented. However, a few extra constraints are needed:

4.

Any party involved will be unable to extract someone else's share without revealing its own.

5.

Any party involved with the protocol will be detected if it cheats.

and optionally:

6.

New shares can be created which can replace or supplement older shares.

We assume that the secret is bounded by a public prime $p$, and $q \leq n$.

A protocol which has all of these characteristics can find application in a variety of settings. For example:

• Distributed Decision Making[4] Let the secret be a key, for example an access code. The question is whether the access code is allowed to be used. The solution: divide up the key into $n$ shares and give one share to each of the $n$ people involved. Let $q$ be the number of ``yes'' votes necessary to decide to use the access code. When someone decides to vote ``yes,'' she simply adds her share into a general pool. When $q$ shares are in the pool, the access code can be computed and used. Otherwise, the access code will remain safely anonymous.

• Hierarchical Access[6] Similar to distributed decision making, let the secret be a key. However, instead of giving one share to everyone, prioritize people according to authority. In a business, for example, you could give the CEO $q$ shares-the secret in essence. For each member of the board, you could give $\frac{q}{2}$ shares. For each manager, $\frac{q}{3}$ shares, and so forth. Thus, rather than requiring $q$ people to convene, all that is necessary is to gather people whom together have $q$ shares.

• Secure File Storage and Fault Tolerance[3,2] Let the secret be a file. Let $n$ be the number of disks available with each disk receiving one share, and let $q$ be the minimum number of shares needed to re-create the file. Thus, in order for an interloper to gain access to the file, he must gain access to $q$ disks. This provides much greater security for files than would exist by simply keeping the file in one central location as it requires an interloper to gain access to each individual disk. In addition, this method provides superior fault tolerance to a simple backup copy scheme. In order for the file to be lost, more than $n-q-1$ disks must fail. As this method does not require an extraordinary amount of additional data over the single backup scheme, it is doubly attractive.

Shamir's Solution

The first secret sharing protocol was created by Adi Shamir [6]. His protocol is not protected against cheating attacks.

In Shamir's original protocol, a Dealer, the person who knows the secret, creates a polynomial $f(x)$ of the form:

$$f(x) = x^q + a_{q-1}x^{q-1} + \cdots + a_1x + S \pmod{p}$$

where the coefficients $a_1 \ldots a_{q-1}$ are chosen independently from [0, $p$). $S$ is the secret (an integer modulo $p$) and $p$ is a large public prime.

The Dealer sends to each participant $C_1 \ldots C_n$ $f(i)$ (assume that the participants know their index). Hereafter, we will refer to $f(i)$ as $C_i$'s share $s$. When $q$ participants desire to recompute the secret, they exchange their shares with each other. We will refer to $q$ as a quorum. Once they have $q$ shares $s_1 \ldots s_q$, they can create $q$ equations. To find $S$, they need only solve for $S$ and each $a_i$ in the following system of equations:

$\begin{array}{rcll}f(s_1) & = & s_1^q + a_{q-1}s_1^{q-1} + \cdots + a_1s_1 + S ... ...s_q) & = & s_q^q + a_{q-1}s_q^{q-1} + \cdots + a_1s_q + S & \pmod{p}\end{array}$

where $p$ and each $f(s_i), s_i$ are known.

To solve for $S$ and $a_1 \ldots a_{q-1}$, all that is required is to solve for $q$ unknowns with $q$ equations in a modulo field. In matrix form ( $\vec{u} = M\vec{v}$, where $\vec{u}$ and $M$ are known) this is:

$$\underbrace{\left[ \begin{array}{c} f(s_1) \ f(s_2) \ \... ... a_1 \ S \end{array} \right]}_{\mbox{\em unknown}} \pmod{p}$$

All that is needed to solve for $\vec{v}$ (and thus $S$) is a simple matrix inversion modulo $p$ and multiplication. Computation modulo $p$ is simple to do since the integers modulo $p$ form a field $(\integers/p\integers)$.

Proof of Correctness

Weaknesses

There are two major weaknesses in Shamir's protocol:

1. Bogus values are undetectable.
2. Participants need not reveal their true share.

These two weaknesses are distinct, because even if a bogus value was detected, it would not necessarily give any information about the true value. However, should some participant $A$ give another participant $B$ invalid information after $B$ has already given valid information to $A$, even if $B$ could detect $A$'s bogus information $A$ will still have more information than $B$. To see this, consider the following example:

Ben-Or/Rabin Solution

Tal Rabin and Michael Ben-Or improved on the protocols of Shamir and others [8,1] by introducing a zero-knowledge proof based upon Check Vectors into the protocol [5]. The improvement to Shamir's secret sharing protocol that we are concerned about is as follows:

For every participant $A, B$ the Dealer picks two positive non-zero integers $b_{AB}, y_{AB} \in \integers_p$ and calculates

$$c_{AB}=(b_{AB})(y_{AB})+s_A \pmod{p}$$

Then instead of just distributing a share $s_A$ to $A$, the dealer gives $A$ $s_A$ and $y_{AB}$ and $B$ the pair $(b_{AB}, c_{AB})$. This pair is known as a Check Vector. It is important to note that $A$ keeps $s_A$ and $y_{AB}$ secret, just as $B$ keeps $(b_{AB}, c_{AB})$ secret.

When a quorum of participants wish to recompute the secret, each participant $A$ exchanges his information privately with participant $B$. $B$ then uses his check vector $(b_{AB}, c_{AB})$ to ensure that:

$$s_A + (b_{AB})(y_{AB}) = c_{AB} \pmod{p}$$

Thus, $A$ cannot try to pass $B$ a bogus value.

Proof of Correctness

We need to show two things to prove that this protocol works as stated.

Weaknesses

The weaknesses of Shamir's solution were twofold: participants could reveal bogus information into the protocol and thereby prevent the secret from being recomputed, and secondly they could give invalid information after receiving another participant's valid information. The Ben-Or/Rabin protocol detects fraudulent values handily, eliminating one of the weaknesses of Shamir's protocol. Unfortunately, the other still remains, namely:

• Participants need not reveal their true shares.

As this protocol involves an exchange of information, the following situation is quite possible:

Alice and Bob decide to recompute the secret. Bob sends his partial secret to Alice, but after receiving both Bob's secret Alice decides to send either a bogus value or nothing at all. Thus, Alice can now compute the secret, but Bob cannot, nor is he able to prevent Alice from doing so.

Conclusions and Future Research

Secret sharing is unusable unless it can ensure that the people involved with the protocol are unable to cheat. The ybc vector protocol ensures that any person involved with the protocol is unable to gain any information from another person without revealing an equal amount of his own information (within a constant factor of 2). However, this protocol does have the following limitations:

1. A cheater can gain an advantage of one bit. Should a cheater decide to take this advantage during the middle of a transaction and then attempt to exhaustively search for the remaining bits, then he will have an advantage of a factor of 2 on the other person. If both parties have equivalent computational power, then this is not an advantage. However, this could be a consideration if the cheater has substantially more computational power (enough so that he can compute the secret by brute force before the victim is able to do something about it).
2. The memory requirements of this protocol are $O(n^2)$. For a reasonable $n$, this is not necessarily burdensome; however, for very large $n$, this can be a problem. For example, this protocol could be used with ease to implement electronic balloting with a constituent of 20, but would be clearly impractical for a popular vote with a constituency of the United States.
3. This protocol only allows for a one-time use of a secret. Once the secret has been revealed, all outstanding keys become useless, and there is no way to re-secure the secret. In the business hierarchy example presented earlier, the access code would need to be changed at every use, and every person involved with the protocol would need a new share (as well as all extra data required).

Future research on secret sharing would require that we extend the protocol to overcome these limitations. One idea would be to explore the use of a secure co-processor [9,10] with the protocol. Proper use could remove the need for any form of check vector requirement as well as allowing the secret to be re-secured; if the secure co-processor is the only entity that interpolates and discovers the secret, then no participant will ever have knowledge of it. This idea naturally scales to handle tamper-proof smart cards.

Acknowledgments

I would like to thank my advisor, Doug Tygar, for his amazing support and help in creating this work. I cannot thank my parents enough, without whom I doubt very much I would be here. I'd also like to thank the Logic & Computation seminar for giving me some different perspectives, the Information and Networking Institute for funding my Small Undergraduate Research Grant, and Mark Stehlik for being an all-around great guy.

Notation

Check Vector

A pair $(b, c)$ used to verify a share $s$.

Dealer

The person who originally has the secret and distributes the shares to the $n$ people.

Participant ($A, B, C, etc.$)

A person involved with recomputing the secret.

$k$

The number of bits in the secret.

$n$

The number of people involved with the secret sharing.

$p$

A large public prime.

$q$

The quorum of people needed to re-create the secret (this must be less than $n$).

$S$

The secret. For simplicity, we'll assume this is an integer modulo $p$.

$s$ (share)

An integer value which, when combined with other shares, re-computes the secret.

$s_{[i]}$

The $i^{th}$ bit of $s$.

$\vec{y}_{ABi}$

The $i^{th}$ component of vector $\vec{y}$ which is used by $B$ to verify information from $A$.

Bibliography

1

Josh D. Cohen.
Keeping shares of a secret secret.
Technical Report YALEU/DCS/TR-453, Yale University Dept. of Computer Science, February 1986.

2

Maurice P. Herlihy and J. D. Tygar.
How to make replicated data secure.
In Carl Pomerance, editor, Lecture Notes in Computer Science #293. Advances in Cryptography, Springer - Verlag, 1987.

3

Michael O. Rabin.
Efficient dispersal of information for security load balancing and fault tolerance.
Technical report, Aiken Computation Laboratory, Harvard University, 1986.

4

Michael O. Rabin and J. D. Tygar.
An integrated toolkit for operating system security.
In W. Litwin and H.-J. Scheli, editors, Lecture Notes in Computer Science #367, Paris, France, June 1989. Foundations of Data Organization and Algorithms, Springer - Verlag.

5

Tal Rabin and Michael Ben-Or.
Verifiable secret sharing and multiparty protocols with honest majority (extended abstract).
Communications of the ACM, pages 73-85, 1989.

6

Adi Shamir.
How to share a secret.
Communications of the ACM, 22(11):612-613, 1979.

7

Gilbert Strang.
Linear Algebra and its Applications.
Harcourt Brace Jovanovich, Inc., third edition, 1988.

8

Martin Tompa and Heather Woll.
How to share a secret with cheaters.
Research Report RC 11840, IBM Research Division, March 1986.

9

J. D. Tygar and B. S. Yee.
Pysically secure coprocessors.
Technical Report CMU-CS-91-140R, Carnegie Mellon University, May 1991.

10

J. D. Tygar and B. S. Yee.
Strongbox.
In Jeffrey L. Eppinger, Lily B. Mummert, and Alfred Z. Spector, editors, Camelot and Avalon: A Distributed Transaction Facility. Morgan Kaufmann, 1991.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 cheaters.tex

The translation was initiated by Erik W. Selberg on 2003-05-25