A shared secret...
Graham Toal
:I am looking for a way to have N people share a secret (such as a key) in
:such a way that any predefined subset of those N people could get together
:and produce the key shared among the entire group. For example, 8 people
:have pieces and 5 are needed to build the entire key, but it can be any 5
:of the 8. I thought I had seen a reference to something like this in this
:group a while back but I apparently didn't save it.
:If it is possible and/or people know any references for me I would
:appreciate hearing about them...
Look up 'n of m error-correcting codes'. Let's take a simplified example:
you have a four-bit key and four people to share it; any three can get
together and use the whole key, but fewer than three can't. In this case
you could use a 1-bit-correcting hamming code, and give each of the
participants a quarter of the key each (probably 2 bits from an 8-bit ecc'd
key)
For your purposes, just scale up the error-correction as necessary. These
codes are documented in several textbooks, often more engineering-biased
than comp sci ones.
Regards
Graham
Jim McCoy
I am looking for a way to have N people share a secret (such as a key) in
such a way that any predefined subset of those N people could get together
and produce the key shared among the entire group. For example, 8 people
have pieces and 5 are needed to build the entire key, but it can be any 5
of the 8. I thought I had seen a reference to something like this in this
group a while back but I apparently didn't save it.
If it is possible and/or people know any references for me I would
appreciate hearing about them...
Thanks,
jim
--
Jim McCoy | UT Unix Sysadmin Tiger Team
mc...@ccwf.cc.utexas.edu | #include <disclaimer.h>
j-m...@nwu.edu | pgp key available via finger or upon request
Mark A Biggar
>I am looking for a way to have N people share a secret (such as a key) in
>such a way that any predefined subset of those N people could get together
>and produce the key shared among the entire group. For example, 8 people
>have pieces and 5 are needed to build the entire key, but it can be any 5
>of the 8. I thought I had seen a reference to something like this in this
>group a while back but I apparently didn't save it.
One nice way to do this is to use the property of polynomials that an
Nth degree polymonial is uniquely determined if you know N+1 distinct
points anywhere on the curve. Using your example, where we want 5 pieces
to work but not 4, means we need a 4th drgree polyonomial. If we choose
a 4th degree polynomial P such that p(0) is the key, and give the
8 people the pairs (1,P(1)), (2,P(2)), ... (8, P(8)), (but not the
polynomial itself) then any 5 or more of them can use their set of points
to reconstruct the original polynomial and evaluate it at 0 to get the key,
but 4 or fewer do not have enough information to do that.
--
Mark Biggar
m...@wdl1.wdl.loral.com
Dane C. Butzer
>Nth degree polymonial is uniquely determined if you know N+1 distinct
>points anywhere on the curve. Using your example, where we want 5 pieces
>to work but not 4, means we need a 4th drgree polyonomial. If we choose
>a 4th degree polynomial P such that p(0) is the key, and give the
>8 people the pairs (1,P(1)), (2,P(2)), ... (8, P(8)), (but not the
>polynomial itself) then any 5 or more of them can use their set of points
>to reconstruct the original polynomial and evaluate it at 0 to get the key,
>but 4 or fewer do not have enough information to do that.
>
>--
>Mark Biggar
>m...@wdl1.wdl.loral.com
>
Why evalutae at 0? This makes only the constant term in the polynomial
significant. Wouldn't evaluating the polynomial at 1 (key = sum of the
coefficients) be better?
Mel Beckman
In article <1ou6bs...@geraldo.cc.utexas.edu> (sci.crypt), mc...@ccwf.cc.utexas.edu (Jim McCoy) writes:
> I am looking for a way to have N people share a secret (such as a key) in
> such a way that any predefined subset of those N people could get together
> and produce the key shared among the entire group. For example, 8 people
> have pieces and 5 are needed to build the entire key, but it can be any 5
> of the 8.
The obvious (but inefficient) way to do this would be using separate public
keys for each person to establish a shared archive containing the target
key multiply-encrypted using all possible permutations of member keys.
As only set membership, and not order, is important (you could assign an
arbitrary ordering among members), the number of permutations is small.
The sets could be genereated automatically, and while possibly time consuming
(today, an hour or more on a PC), presumably the importance of information
protected with such a complex scheme warrants the added time per instance.
My math might be in error, but off the top of my head, the formula for number
of encrypted sets should be m*(n-m+1), where n is the total population, and
n is the subset population. In the example, then, the number of encrypted
sets would be 5*(8-5+1) or 20. The identification of groupings could be
predetermined by the order of the sets. A given group of five people would
choose the set corresponding to their group, then apply their private keys
in the predefined sequence.
________________________________________________________________________
| Mel beckman | Internet: mbec...@mbeckman.com |
| Beckman Software Engineering | Compuserve: 75226,2257 |
| Ventura, CA 93003 | Voice/fax: 805/647-1641 805/647-3125 |
|______________________________|_______________________________________|
"You can observe a lot just by watching." -Yogi Bera
Walt Hyde
>such a way that any predefined subset of those N people could get together
>and produce the key shared among the entire group. For example, 8 people
>have pieces and 5 are needed to build the entire key, but it can be any 5
>of the 8. I thought I had seen a reference to something like this in this
>group a while back but I apparently didn't save it.
>
>If it is possible and/or people know any references for me I would
>appreciate hearing about them...
There's "Sharing Secrets Among Friends", by Bruce Schneier, in Computer
Language, April 1992. Is this luck, or what?
Mark A Biggar
>>One nice way to do this is to use the property of polynomials that an
>>Nth degree polymonial is uniquely determined if you know N+1 distinct
>>points anywhere on the curve. Using your example, where we want 5 pieces
>>to work but not 4, means we need a 4th drgree polyonomial. If we choose
>>a 4th degree polynomial P such that p(0) is the key, and give the
>>8 people the pairs (1,P(1)), (2,P(2)), ... (8, P(8)), (but not the
>>polynomial itself) then any 5 or more of them can use their set of points
>>to reconstruct the original polynomial and evaluate it at 0 to get the key,
>>but 4 or fewer do not have enough information to do that.
>significant. Wouldn't evaluating the polynomial at 1 (key = sum of the
>coefficients) be better?
First it doesn't matter where you evaluate the polynomial as long as it
is agreed on before hand and is not one of the distributed points.
Second using 0 makes selecting the polymonial trivial, just use the key
as the constant term and N random values as the coefficients, with
the limit that the highest order term can't be zero.
You method of selecting the polynomial is no more secure then any other
other method that works, it just cost more then using the evaluate at 0
method.
--
Mark Biggar
m...@wdl1.wdl.loral.com
Bruce Schneier
>such a way that any predefined subset of those N people could get together
>and produce the key shared among the entire group. For example, 8 people
>have pieces and 5 are needed to build the entire key, but it can be any 5
>of the 8. I thought I had seen a reference to something like this in this
>group a while back but I apparently didn't save it.
>
>If it is possible and/or people know any references for me I would
>appreciate hearing about them...
What you want is a threshold scheme, invented (independently) by Adi
Shamir and G.R. Blakley.
Shamir's original paper appeared in the Nov 79 (v. 24, n. 11) issue of
Comm ACM. I wrote an article on the topic in the Apr 92 Computer
Language.
Have fun,
Bruce
Tal Kubo
>
>One nice way to do this is to use the property of polynomials that an
>Nth degree polymonial is uniquely determined if you know N+1 distinct
>points anywhere on the curve. Using your example, where we want 5 pieces
>to work but not 4, means we need a 4th drgree polyonomial. If we choose
>a 4th degree polynomial P such that p(0) is the key, and give the
>8 people the pairs (1,P(1)), (2,P(2)), ... (8, P(8)), (but not the
>polynomial itself) then any 5 or more of them can use their set of points
>to reconstruct the original polynomial and evaluate it at 0 to get the key,
>but 4 or fewer do not have enough information to do that.
I think a bit more than that is necessary, because if something is known
about the polynomial (e.g. it has integer coefficients) then information
can be leaked. For example, if P(x)=0 for N distinct values
x=a1,a2,..,aN, and P has integer coefficients, then we know that P(0)
is divisible by the product a1*a2*...*aN.
Another thing to consider is that different coalitions of N players have
different amounts of information about the polynomial. In the above
example, the people who know the extreme values have a bit more information
than those who know the values in the middle of the range. This
discrepancy seems to persist in the general case when P has rational
coefficients, when you consider the "height" (in the sense of divisibility)
of the coefficients of the interpolation formula for determining an N'th
polynomial from its values at N+1 different points.
Maybe the way out would be to give the values of P at roots of unity.
This would give each individual player the same amount of information,
although there still seem to be problems with coalitions. Is there a
completely symmetrical method of distributing the information?
Germano Caronni
Yes.
Contemporary Cryptology - The science of Information Integrity
(c) 1992 - IEEE Press NY. IEEE Order Number: PC0271-7
ISBN: 0-87942-277-7
Simmons:Intro to shared Secret and/or Shared Control
He presents an approach based on geometrical bodys, and claims
that if (N-1) people share parts of the secret, they gain no
information about the N'th part of the shared shecret, which
would be needed to unlock.
Unluckily I do not have the paper at hand, and can not figure out
in my mind how exactly he defined things. Perhaps somebody could
quote ?
I may present an example for (2 out of N). Assume 3-dimensional space.
Given is a line (defined by two points). And a point of a plane.
Which would naturally need three points to be defined.
Control can be invoked, if one finds out where the plane has to intersect
with the line. Each member of the group knows one point lying in the plane,
and if two of them work together, they can calculate the plane, and inter-
sect it with the line. But one alone does not have any information about
the controlling point, as the plane could be turned around the line in nearly
every direction, and still match with the given line.
He presents more sophisticated structures (like needing two peoples from
Group A, or 5 peoples from group B, or 1 from A and 2 of B two unlock),
but I can't remember them exactly.
Greetings,
Germano Caronni
Steven Bellovin
>
> I am looking for a way to have N people share a secret (such as a key) in
> such a way that any predefined subset of those N people could get together
> and produce the key shared among the entire group. For example, 8 people
> have pieces and 5 are needed to build the entire key, but it can be any 5
> of the 8. I thought I had seen a reference to something like this in this
> group a while back but I apparently didn't save it.
>
> If it is possible and/or people know any references for me I would
> appreciate hearing about them...
The most-cited paper on the subject is
@article{sharesecret,
author = {Adi Shamir},
journal = {Communications of the ACM},
number = {11},
pages = {612--613},
title = {How to Share a Secret},
volume = {22},
year = {1979}
}
Gifford presents ways to implement all sorts of combinations:
@article{sealing,
author = {David K. Gifford},
journal = {Communications of the ACM},
number = {4},
pages = {274--286},
title = {Cryptographic Sealing for Information Secrecy and Authentication},
volume = {25},
year = {1982}
}
A good overview of the whole subject, with a large bibliography, is in
@incollection{Simmons92,
author = {Gustavus J. Simmons},
title = {An Introduction to Shared Secret and/or Shared Control Schemes and Their Application},
booktitle = {Contemporary Cryptology: The Science of Information Integrity},
year = 1992,
pages = {441--497},
editor = {Gustavus J. Simmons},
publisher = {{IEEE} Press}
}
D. J. Bernstein
> I think a bit more than that is necessary, because if something is known
> about the polynomial (e.g. it has integer coefficients) then information
> can be leaked.
As you would see if you checked Knuth, vol. 2, p. 486, the coefficients
are integers modulo some prime p. No information is ``leaked.''
---Dan
Tal Kubo
As you would see if you had read the thread more closely, rathing than
looking for nits to pick (I note that your article was posted exactly
nine minutes after your other article accusing me of amnesia),
(a) I wrote in response to Mark Biggar's article, where no mention
was made of using Z/pZ coefficients (or of Adi Shamir, for that
matter), just the the general idea of interpolating a polynomial from
its values. I pointed out some possible problems with that.
(b) I specifically considered only the case of characteristic 0, as
is also clear from the rest of my post which mentioned rational
coefficients
But thanks anyway for the reference. It's the only factual thing you've
posted here lately.
leic...@zodiac.rutgers.edu
@incollection{benaloh:generalized,
author = "Josh Benaloh and Jerry Leichter",
title = "Generalized Secret Sharing and Monotone Functions",
booktitle = "Advances in Cryptology: Proceedings of Crypto~88",
year = 1988,
month = aug,
editor = "Shafi Goldwasser",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
number = "403",
pages = "27--35",
note = "Also " # YALEU # " Technical Report TR-748, " # oct # " 1989"
}
-- Jerry