The Paranoid Spy
David Wagner
In article <4v32oj$c...@net.auckland.ac.nz>,
Jon Haugsand <jon...@ifi.uio.no> wrote:
>
> THE PARANOID SPY PROBLEM
> ------------------------
>
> A spy has falled in disgrace with his now former employer. However,
> due to all the knowledge he has collected he is afraid that he might
> be killed to ensure the confidentiality of this information. The spy
> therefore tries to turn this threat into a life insurence by arranging
> it such that if he gets killed, the information will be released in
> order to damage his former employer. He must, however, take care to
> ensure the confidentiality of the information while he lives, but to
> be as sure as possible to disclose the information if he is killed.
[...]
> Suppose the spy knows $N$ persons he more or less trusts. That is,
> there is a probability of $p$ that any given (but arbitrary) person
> will fail to cooperate with the spy. If the ``collaborator'' is a
> traitress, she will try to disclose the information immidiately, and
> if the spies dies, she will try to deny disclosure. I.e. the
> non-traitresses will keep the information secret as long as the spy
> lives and disclose the information if the spy dies, while a traitress
> will try to do the opposite. The spy must consequently try to minimize
> the chance that his arrangement will fail.
[...]
> Suppose $(N,p)=(10,0.1)$. Find the best way to do it.
[...]
> 1. Can you find the best arrangement and prove it really is the best?
> What is the probability of success?
> 2. Can you generalize it for arbitrary $N$ and $p$?
> 3. If $p>0.5$, can $p[success]$ ever be greater than $0.5$?
>
Cool problem! This just cries out for an analysis based on secret sharing &
lattices.
Ok, here goes. This post is long, and I apologize for that in advance, but
I think it answers all your questions, and the solution is even fairly
elegant -- or at least, more elegant than you'd expect to see from a systems
guy. :-)
Any strategy for distributing the shares to the collaborators can be expressed
as a lattice $L$ of sets $S$, where $S \in L$ iff the set $S$ of persons can
recover the spy's secret information. Notice that if $L$ is an expression of
a secret sharing strategy, then $L$ will be "monotone", i.e. $S \in L$,
$S \subset T$ implies $T \in L$. Furthermore, given any monotone lattice $L$,
one can construct a corresponding secret sharing scheme. (Proof: for each
$S \in L$ with $|S|=k$, split the secret into $k$ shares in such a way that
the secret can be reconstructed only if all $k$ shares are available, and
give the $k$ shares to the persons names by $S$. Repeat for all $S \in L$.
One simple way to do such a splitting is to calculate random shares $s_1,
s_2, ..., s_{k-1}$ and let
$s_k = s_1 + s_2 + ... + s_{k-1} + secret$
where + denotes exclusive-or.) So this gives us:
Thm 1. Any strategy can be expressed as a monotone lattice, and vice versa.
Given a strategy, we can also express the elements of the probability space
as a lattice $M$, where each set $S$ describes the persons who are faithful
(i.e. not traiteresses): $M$ is defined so that $S \in M$ iff the strategy
succeeds on $S$. The lattice $M$ is endowed with a probability measure $p$,
defined on sets $S$ by
$p(S) = (1 - p)^{|S|} p^{n - |S|}$
and extended to the lattice $M$ additively by
$p(M) = \sum_{S \in M} p(S).$
Note that $p(M)$ is just the probability of success, which we want to maximize.
Of course $M$ is determined by $L$. Let's examine how. For any lattice $L$,
define the lattice $Rev(L)$ (think ``Reverse of L'') by
$S \in Rev(L)$ iff $V-S \in V'-L$
where I want $V$ to represent the full set containing all $n$ members and $V'$
to denote the full lattice containing all possible sets $S$ of persons; thus
$V-S$ is the set complement of $S$, and $V'-L$ is the lattice complement of
$L$. The $Rev$ operator has some nice properties: $|L| + |Rev(L)| = |V'|
= 2^n$, if $L$ is monotone then $Rev(L)$ is too, $Rev(Rev(L)) = L$,
$Rev(L \cap L') = Rev(L) \cup Rev(L')$, etc. When clarity is desired, write
$M(L)$ to represent the probability space induced by the strategy $L$. Now I
am ready to claim that
Thm 2. $M(L) = L \cap Rev(L)$ for all strategies $L$.
(Proof: certainly $M(L) \subset L$: that is the condition that some set of
faithful persons must be able to reveal the secret if the spy dies. Similarly,
we must have $M(L) \subset Rev(L)$: that is the condition that no set of
traiteresses can reveal the secret while the spy still lives. A converse also
holds: if both conditions are met (i.e. $S \in L \cap Rev(L)$), then the set
will represent success for the spy (i.e. $S \in M(L)$).)
Note, by the way, that $M(L)$ is monotone, since $L$ and $Rev(L)$ both are.
So we're getting somewhere: we can now calculate the probability of success
$p(M(L)) = p(L \cap Rev(L))$ for any strategy $L$.
It turns out that we can actually completely characterize the possible lattices
$M'$ which represent probability spaces attainable by some strategy. Clearly
if $M' \subset Rev(M')$, then $M'$ is an attainable probability space lattice,
as we may take $L = M'$ so that $M(L) = M'$. Conversely, for any strategy $L$,
we have $M(L) \subset Rev(M(L))$. (Proof: calculate $Rev(L \cap Rev(L)) =
Rev(L) \cup Rev(Rev(L)) = Rev(L) \cup L,$ and the result follows immediately)
So we have proved
Thm 3. $M$ represents an attainable probability space iff $M \subset Rev(M)$.
The original question is thus reduced to the problem of finding an attainable
$M$ which optimizes $p(M)$.
But now that's enough to solve all the questions you posed.
For example, when $n=9$, the optimal attainable probability space is the
lattice $M_9$ defined by
$S \in M_9$ iff $|S| > 4$.
One way to attain this is by the strategy $L_9 = M_9$. The success
probability of this strategy is
$p(M_9) = \sum{4 < i < 10} C(9,i) (1-p)^i p^{9-i}$
where $C(9,i) = 9! / (i! (9-i)!)$ is the binomial coefficient ``9 choose $i$''.
This strategy generalizes to all odd $n$.
As another example, take $n=10$. Then the archetypical optimum attainable
probability space is the lattice $M_10$ defined by
$S \in M_10$ iff either $|S| > 5$ or $S \in X$
where $X$ is a set of sets satisfying
$S \in X$ implies $|S| = 5$,
and $|X| = C(10,5)/2$.
All the optimal attainable probability spaces can be expressed in this form
for some choice of $M'$. Again, this can be attained by the strategy
$L_10 = M_10$. The success probability can be calculated as
$p(M_10) = \sum{5 < i < 10} C(10,i) (1-p)^i p^{10-i}
+ C(10,5)/2 (1-p)^5 p^5.$
I calculate that to be $p(M_10) = .999109$, though I could've made an
arithmetic error. This approach generalizes to all even $n$; we can see that
it's just a minor tweaking of the strategy for odd $n$.
To prove that these are the best strategies, note that $|Rev(L)| = 2^n - |L|$,
so that $|M| \le 2^{n-1}$ for any attainable probablity space $M$.
Furthermore, the strategies listed above meet that bound exactly, and $M_n$
ends up containing exactly the $2^{n-1}$ sets $S$ of highest probability
$p(S)$. So it should be apparent that one can't possibly do any better.
That answers all your questions, I believe. I hope that I haven't made any
serious mistakes, although I always seem to make a couple in any attempt of
this length.
I admit I haven't described an efficient way to implement the optimum threshold secret sharing scheme that
is described above, but I think with some additional thought you can figure
out how to improve the naive exponential-complexity method that I alluded to
in the beginning.
I'm sure this problem must be addressed somewhere in the literature, although
I'm not familiar with the published results on this kind of stuff. Anyhow, I
had far more fun figuring it out myself than I would've had with any book. :-)
You posed a very nice problem! It kept me entertained for two or three
pleasant hours. Thank you!
-- Dave Wagner
Greg Miller
On 17 Aug 1996 00:12:03 GMT, Jon Haugsand <jon...@ifi.uio.no> wrote:
>A spy has falled in disgrace with his now former employer. However,
>due to all the knowledge he has collected he is afraid that he might
>be killed to ensure the confidentiality of this information. The spy
>therefore tries to turn this threat into a life insurence by arranging
>it such that if he gets killed, the information will be released in
>order to damage his former employer. He must, however, take care to
>ensure the confidentiality of the information while he lives, but to
>be as sure as possible to disclose the information if he is killed.
>How to make such an arrangement I shall call the *Paranoid Spy
>problem*. (Can anyone suggest a better name?)
I have often wondered if there was a way to protect the information if
the spy was killed by someone other than his agency. If the information is
important enough to keep secret, then someone can benifit from it. And may kill
the spy so the informaiton will be disclosed.
Another problem is that members of the escrow party may begin killing
eachother to prevent disclosure.
So far, the best solution I've come up with is to have a very large
escrow party. Distribute parts of the keys small enough so that even if a few
members fail to follow the correct protocol, the message can still be cracked
using the combined processing power of the remaining escrow members.
The disadvantage is the need for a lot of "trusted" people. The
advantage is that the escrow members don't have to be trusted a great deal
independantly.
.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯
enum MicrosoftBoolean {TRUE, FALSE, MAYBE};
Greg Miller: Programmer/Analyst (gmi...@dey-systems.com)
http://grendel.ius.indiana.edu/~gmiller/
´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._.·´¯´·._
David R Brooks
Jon Haugsand <jon...@ifi.uio.no> wrote:
[snip]
>THE PARANOID SPY PROBLEM
>------------------------
>
>due to all the knowledge he has collected he is afraid that he might
>be killed to ensure the confidentiality of this information. The spy
>therefore tries to turn this threat into a life insurence by arranging
>it such that if he gets killed, the information will be released in
>order to damage his former employer. He must, however, take care to
>ensure the confidentiality of the information while he lives, but to
>be as sure as possible to disclose the information if he is killed.
>How to make such an arrangement I shall call the *Paranoid Spy
>problem*. (Can anyone suggest a better name?)
>
Is this not a case of shared secrets, such as discussed in Schneier
(1st edition) P383.. ?
May we reduce it to something like this:
Our spy selects N trustees, of whom he accepts that up to M may turn
traitress. What is needed is a secret that M participants cannot
obtain, but that Q = N-M infallibly can. Clearly Q > M, whence
M < N/2.
An example (from Schneier) would be the polynomial scheme. Our spy
chooses a polynomial f(x), of degree K, where M < K <= Q. The
coefficients of this polynomial represent the key to whatever cipher
protects the confidential information.
Each trustee is given the cooridnates of one point on the locus of
this function (ie a x,y tuple). K or more trustees in concert, can set
up and solve a system of equations to obtain f(x), and hence "open the
box". The M traitresses, since M < K, cannot. Neither can the
traitresses frustrate decryption following the spy's death, since
there remain Q=N-M "honest" trustees. Since K < Q, the solution is
possible.
-- Dave Brooks <http://www.iinet.net.au/~daveb>
PGP public key: finger da...@opera.iinet.net.au
servers da...@iinet.net.au
fingerprint 20 8F 95 22 96 D6 1C 0B 3D 4D C3 D4 50 A1 C4 34
What's all this? see http://www.iinet.net.au/~daveb/crypto.html
Ilias Kastanas
In article <4v32pt$c...@net.auckland.ac.nz>,
Jon Haugsand <jon...@ifi.uio.no> wrote:
>
>An ongoing discussion ("Decrypt 100 years from now?") in sci.crypt
>made me post the following problem of mine. (Please excuse my bad
>English.) (TeX notation for the math: "$"s enclose math expressions.
>"\simeq" means "approximal equal to".)
>
>THE PARANOID SPY PROBLEM
>------------------------
>
>A spy has falled in disgrace with his now former employer. However,
>due to all the knowledge he has collected he is afraid that he might
>be killed to ensure the confidentiality of this information. The spy
>therefore tries to turn this threat into a life insurence by arranging
>it such that if he gets killed, the information will be released in
>order to damage his former employer. He must, however, take care to
>ensure the confidentiality of the information while he lives, but to
>be as sure as possible to disclose the information if he is killed.
>How to make such an arrangement I shall call the *Paranoid Spy
>problem*. (Can anyone suggest a better name?)
A relative is "Court Wizard". The King asks him 'Well, wizard,
when am I going to die?'. The wizard gazes into his crystal ball and
says 'Your Majesty will die three days after I do'.
>Here I want to discuss a solution based on cryptographic techniques.
>Suppose the spy knows $N$ persons he more or less trusts. That is,
>there is a probability of $p$ that any given (but arbitrary) person
>will fail to cooperate with the spy. If the ``collaborator'' is a
>traitress, she will try to disclose the information immidiately, and
>if the spies dies, she will try to deny disclosure. I.e. the
>non-traitresses will keep the information secret as long as the spy
>lives and disclose the information if the spy dies, while a traitress
>will try to do the opposite. The spy must consequently try to minimize
>the chance that his arrangement will fail. To do this he encrypts the
>information one or several times and distributes the ciphertext and
>(some of) the keys (or information on how to generate the keys) to his
>collaborators. How should he do this? (Is this an old problem?)
>
>This is a cryptographic problem so reasonable assumptions apply: the
>information is atomic, all traitresses can contact each other undetected,
>the spy's arrangement is known to all, etc.
>
>Suppose $(N,p)=(10,0.1)$. Find the best way to do it.
>
>*First try:* encrypt (symmetric) the information and distribute the
>ciphertext and the key to all 10. Failure if one fails: she can
>disclose the information.
>$P[success]=0.9^{10} = 0.35$
>
>*Second try:* "serial" encrypt the information with 10 different keys and
>give each of the 10 a diffirent key. Failure if one fails: she can
>refuse to decrypt. $P[success]=0.35$.
>
>*Third try:* serial encrypt the information with 5 different keys and
>give 5 of the collaboraters one key each. Repeat this with 5 new keys
>and give the remaining 5 these keys. Failure if at least two persons,
>one from each group, fail (refusal to decrypt), or if all five in one
>of the groups fail (early disclosure). \\
>$P[disclosure]=0.1^5 +(1-0.1^5)*(0.1^5) = 0.00002$\\
>$P[refusal]=(1-0.9^5)*(1-0.9^5)= 0.17$\\
>$P[success] \simeq 0.83$
>
>*Fourth try:* serial encrypt with 5 keys. Give each key to two
>collaborators, such that each of them has exactly one of the keys.
>Failure if two with the same key fail (refusal to decrypt) and if 5
>with different keys fail (early disclosure).\\
>$P[disclose] = 0.19^5 = 0.00025$,
>$P[refusal] = 1-0.99^5 = 0.05$\\
>$P[success] \simeq 0.95$
>
>
>1. Can you find the best arrangement and prove it really is the best?
> What is the probability of success?
>2. Can you generalize it for arbitrary $N$ and $p$?
>3. If $p>0.5$, can $p[success]$ ever be greater than $0.5$?
I would suggest focusing on symmetric arrangements, where any k
collaborators can decrypt, but no k-1 many can. Easily, k = 5 gives
the best result (k = 6 also does). There is failure by early disclosure
iff there are >= 5 traitresses; if this does not happen, there will be
no failure by refusal to decrypt.
Let p = 0.1, q = 1-p. Using the binomial coefficients (10 pick m)
= 10! / m!(10-m)!, the probability of success is
q^10 + 10*p*q^9 + 45*p^2*q^8 + 120*p^3*q^7 + 210*p^4*q^6
which is approximately = 0.99825 .
To achieve this, a simple if wasteful way is as follows. There are
(10 pick 5) = 252 groups of 5 collaborators. (The full listing has 5*252
= 1260 entries, so each collaborator belongs to 126 groups, which checks
since 126 = (9 pick 4) ). For each such group the spy picks a different
key, encrypts, and distributes to each member of the group 1/5 of the key.
If this violates atomicity, serial encryption with five keys comes to the
same thing.
It seems plausible that this solution is best overall, but I haven't
looked for a proof. Generalization is obvious. For fixed p = 0.1, incre-
asing N improves the probability of success. E.g. for N = 4 it is 0.9477
and for N = 6, 0.9840.
If p > 0.5, however, the symmetric scheme grows worse with increa-
sing N. It seems to me one can do no better than N = 1, with probability
of success q; anything more involved will harm rather than help.
Ilias
Jon Haugsand
An ongoing discussion ("Decrypt 100 years from now?") in sci.crypt
made me post the following problem of mine. (Please excuse my bad
English.) (TeX notation for the math: "$"s enclose math expressions.
"\simeq" means "approximal equal to".)
THE PARANOID SPY PROBLEM
------------------------
A spy has falled in disgrace with his now former employer. However,
due to all the knowledge he has collected he is afraid that he might
be killed to ensure the confidentiality of this information. The spy
therefore tries to turn this threat into a life insurence by arranging
it such that if he gets killed, the information will be released in
order to damage his former employer. He must, however, take care to
ensure the confidentiality of the information while he lives, but to
be as sure as possible to disclose the information if he is killed.
How to make such an arrangement I shall call the *Paranoid Spy
problem*. (Can anyone suggest a better name?)
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Pho/fax: +47-22852441/+47-22852401
Addr: Bredo Stabells v.15, N-0853 OSLO, NORWAY, Phone: +47-22952152
Nicholas C. Weaver
In article <4v32oj$c...@net.auckland.ac.nz>,
Jon Haugsand <jon...@ifi.uio.no> wrote:
>THE PARANOID SPY PROBLEM
>------------------------
>
>A spy has falled in disgrace with his now former employer. However,
>due to all the knowledge he has collected he is afraid that he might
>be killed to ensure the confidentiality of this information. The spy
>therefore tries to turn this threat into a life insurence by arranging
>it such that if he gets killed, the information will be released in
>order to damage his former employer. He must, however, take care to
>ensure the confidentiality of the information while he lives, but to
>be as sure as possible to disclose the information if he is killed.
>How to make such an arrangement I shall call the *Paranoid Spy
>problem*. (Can anyone suggest a better name?)
Dames Bomb?
>Here I want to discuss a solution based on cryptographic techniques.
>Suppose the spy knows $N$ persons he more or less trusts. That is,
>there is a probability of $p$ that any given (but arbitrary) person
>will fail to cooperate with the spy. If the ``collaborator'' is a
>traitress, she will try to disclose the information immidiately, and
>if the spies dies, she will try to deny disclosure. I.e. the
>non-traitresses will keep the information secret as long as the spy
>lives and disclose the information if the spy dies, while a traitress
>will try to do the opposite. The spy must consequently try to minimize
>the chance that his arrangement will fail. To do this he encrypts the
>information one or several times and distributes the ciphertext and
>(some of) the keys (or information on how to generate the keys) to his
>collaborators. How should he do this? (Is this an old problem?)
I believe so, in a slightly different form. (This is memory
from a combinatorics class from 2 years ago, so pardon any mistakes).
A wealthy dowager has $k$ bickering neecies and nephiews, and one VERY
FULL swiss bank account. She wants to arrange things so that if $j$
of her relatives cooperate, they can get the number of the bank
account and the cash, but any number of relatives less then $j$ can
only guess, and guess no better then any nonrelative.
(Dames Bomb wants to require that at least $j$ of his ex-es to
have to cooperate in order to reveal his secret, and he believes that
there are less then $j$ traitoresses)
The secret $S$ is a random number from 0 to $M-1$, with $M$
being a large prime. All math is done mod $M$. ($S$ can be the bank
account number, or an encryption key, etc, but it must be a random
number). The dutchess creates a polynomial of degree $j-1$ of the form
$f = S + S_{1}x + S_{2}x^{2} .. S_{j-1}x^{j-1}$. $S_{1}$, $S_{2}$... are
all random numbers.
Then, to the ith relative, she gives them a pair
<$i$,$f(i)$>. In order to find $f(0)$ (which is equivalent to $S$),
$j$ relatives must cooperate, in order to determine the polynomial
$f$. If less then $j$ relatives cooperate, they lack the sufficient
information to determine $f$.
--
Nicholas C. Weaver Purveyor of Insights
http://www.cs.berkeley.edu/~nweaver Herder of Cats
nwe...@cs.berkeley.edu and All Around Nice Guy (tm)
It is a tale, told by an idiot, full of sound and fury, .signifying nothing.
Doug McKean
Jon Haugsand wrote:
>
> An ongoing discussion ("Decrypt 100 years from now?") in sci.crypt
> made me post the following problem of mine. (Please excuse my bad
> English.) (TeX notation for the math: "$"s enclose math expressions.
> "\simeq" means "approximal equal to".)
>
> ------------------------
>
> A spy has falled in disgrace with his now former employer. However,
> due to all the knowledge he has collected he is afraid that he might
> be killed to ensure the confidentiality of this information. The spy
> therefore tries to turn this threat into a life insurence by arranging
> it such that if he gets killed, the information will be released in
> order to damage his former employer. He must, however, take care to
> ensure the confidentiality of the information while he lives, but to
> be as sure as possible to disclose the information if he is killed.
> How to make such an arrangement I shall call the *Paranoid Spy
> problem*. (Can anyone suggest a better name?)
>
> Suppose the spy knows $N$ persons he more or less trusts. That is,
> there is a probability of $p$ that any given (but arbitrary) person
> will fail to cooperate with the spy. If the ``collaborator'' is a
> traitress, she will try to disclose the information immidiately, and
> if the spies dies, she will try to deny disclosure. I.e. the
> non-traitresses will keep the information secret as long as the spy
> lives and disclose the information if the spy dies, while a traitress
> will try to do the opposite. The spy must consequently try to minimize
> the chance that his arrangement will fail. To do this he encrypts the
> information one or several times and distributes the ciphertext and
> (some of) the keys (or information on how to generate the keys) to his
> collaborators. How should he do this? (Is this an old problem?)
>
Jon,
I'll answer this below.
spoiler below ---
I think, though an excellent discussion on
encryption, there's an entirely different
way to do this as stated in the problem AND
assuming the spy is in the United States.
I don't know if this will apply internationally.
The spy takes his information in an envelope with
instructions on the outside of it to a lawyer.
the instructions would read, "In the event of the
death of John Doe - Spy, deliver this envelope
to the nearest newspaper publisher."
He requests his lawyer to "chain" as many lawyers as he sees fit.
Then immediately leaves the lawyer's office.
(Here in the US its unlawful to disclose
confidentiality between lawyer and client.)
Now, the first lawyer goes to a second lawyer AS A CLIENT and
hands off the envelope to the second lawyer.
He instructs the second lawyer to do the same with a third lawyer,
and the third with the fourth, and so on.
The first lawyer could control this several ways unknown
to the spy.
1. He doesn't indicate in anyway how many "client"
lawyers there should be in the chain.
2. He writes a number on the front of the envelope with
instructions telling the receiving lawyer to cross
out the number on the envelope after subtracting one
from it. Write down the new number on the envelope.
If that number is equal to let's say zero, retain the envelope.
In this way, if the spy is caught, he truely does not know where
the envelope is. If he dies, the lawyer holding the envelope
is legally obligated to release the information to a newspaper.
Just a thought.
Doug
JOSEPHMIKHAIL
I'm not a cryptographer but I think you could use a secret sharing program
called secsplit.zip. It can divide a file into n pieces such that any
x number of people can assemble the file but not anything less than x. So
the spy could put all the information he knows, maps, name of people, time
sheets of projects, secret doucument, etc., into a zip file. Then he
could use secshare.zip to dived the file into lets say 7 pieces. He gives
them to his 7 best friends such that any four of them could assembe the
file and get the information upon hearing of his death. this prevents a
premature leak of information becuase if a person wanted to know the
contents of the file he would have to convience 3 other people to give him
thier pieces. As long as te spy has trusted friends he shouldn't have to
worry, of course how good of a friend can a spy have.
While were taking about this subject i have thought of a problem. Lets
say the spy was antisocial and has no friends and that he was an orphan so
has no realatives. Is there a way such that when he dies the information
he has goes directly to the email of every newspaper in the country along
with postings on every usenet board so that everyone in the world knows.
But can NEVER be realised as long as the spy is safe and well?
I hope my answer helps you out.
PS I just wanted to know, I'm new to usenet, if replying with the whole
message is necessary or not. the only thing I know about replying is not
to use all caps.
Herb Sutter
On Sat, 17 Aug 1996 14:35:57 -0400, JOSEPHMIKHAIL <Mik...@cris.com>
wrote:
>Is there a way such that when he dies the information
>he has goes directly to the email of every newspaper in the country along
>with postings on every usenet board so that everyone in the world knows.
>But can NEVER be realised as long as the spy is safe and well?
Use a dead man's switch.
Set up an automated system that can fire off the messages, and connect
it to a countdown clock which the spy (but no one else) has the
ability to periodically reset. If the clock reaches zero, the
messages fire. Every day (or whatever), the spy comes by and resets
the clock, preventing the messages from firing. If the spy is killed,
no one can reset the clock, it will go all the way to zero, and the
messages fire.
Of course, you need to ensure that no one else can reset the clock or
prevent the messages from firing. There is also the danger that if
the spy is unable to reset the clock on time, the messages fire even
though he is still alive (this may be good if you want the messages to
fire if the spy is detained).
>PS I just wanted to know, I'm new to usenet, if replying with the whole
>message is necessary or not. the only thing I know about replying is not
>to use all caps.
No, usually you should quote just what's necessary to let someone
reading your followup see what you're answering.
---
Herb Sutter (he...@cntc.com)
Current Network Technologies Corp.
3100 Ridgeway, Suite 42, Mississauga ON Canada L5L 5M5
Tel 416-805-9088 Fax 905-608-2611
Bryan Olson
Jon Haugsand wrote:
>
> Here I want to discuss a solution based on cryptographic techniques.
> Suppose the spy knows $N$ persons he more or less trusts. That is,
> there is a probability of $p$ that any given (but arbitrary) person
> will fail
> *First try:* encrypt (symmetric) the information and distribute the
> ciphertext and the key to all 10. Failure if one fails: she can
> disclose the information.
> *Second try:* "serial" encrypt the information with 10 different keys and
> give each of the 10 a diffirent key. Failure if one fails: she can
> refuse to decrypt.
[Third and fourth tries were makeshift thresholds]
First, what we need is a secret sharing (threshold) scheme. A
system in which m of n people can cooperate to recover a secret,
and m-1 cannot is an (m,n) threshold scheme.
> 1. Can you find the best arrangement and prove it really is the best?
> What is the probability of success?
> 2. Can you generalize it for arbitrary $N$ and $p$?
> 3. If $p>0.5$, can $p[success]$ ever be greater than $0.5$?
I've never seen the probabilities properly worked out, but I have
considered this myself for a related problem. First I don't
think the single probability p sufficiently describes the chance
of failure, since there are two distinct modes of failure: early
release and late release. Suppose that for each trustee the
chance of early release is p, and the chance of late release is q.
If we assume each trustee acts independently, then the expected
number of early releases is np, and late releases is nq.
We also find that the number of bad releases on both sides
should follow a binomial distribution.
Threshold schemes let us choose our m and n. Lets suppose we
have some n, and Ill try to graph the probability of failure
by early release for each choice of m. It should look something
like this:
| |
1 |--_ |
| \ |
| \ |
| \ |
| \ |
| \____ |
| ------_| 0
0 n
x axis: number of shares out of n to recover secret
y axis: chance of failure by early release
If zero shares can recover the secret, early release is certain.
If n+1 are required, early release is impossible.
Next, we graph the chance of failure by late release as a function
of m.
| |
| _--| 1
| / |
| / |
| / |
| / |
| ___/ |
0 |_---- |
0 n
x axis: number of shares out of n to recover secret
y axis: chance of failure by late release
Late release and early release are mutually exclusive, so
the total probability of failure is their sum.
| |
1 |- _ _-|
| \ / |
| \ / |
| \ / |
| \ / |
| --- |
| |
0 n
x axis: number of shares out of n to recover secret
y axis: chance of some kind of failure.
So in answer to your three questions:
1. With a singe probability of failure I don't think we
can know the best parameters, but if we assume that
your p is both my p and q, a 5 (or 6) out of 10
threshold is best, (obvious by symmetry?). I don't
have a binomial table handy to find the numbers,
but our spy's odds are very good.
2. It generalizes. We need binomial probabilities, or for
large n, the normal approximation to the binomial.
3. If p = q = 0.5, there will be a trivial dip in the
combined curve. But if we consider p and q
separately, the critical criteria is that
p + q < 1. Given p+q<1, we can make the
probability of failure arbitrarily close to 0,
by choosing a large n, and good m.
A couple notes: In practice we will not have a known
p and q which hold for all trustees. I'd phrase the
requirement (as I did in another thread) to be that
the failure probability for each server are "at most"
p and q. That way we get an upper bound on the
probability of failure. We could actually use multiple
probabilities if some trustees are more reliable than
others, and then divide the secret shares un-equally,
but I don't want to do the math.
--Bryan
Jeremy Buhler
Quoth Jon Haugsand (jon...@ifi.uio.no):
> THE PARANOID SPY PROBLEM
> ------------------------
> A spy has falled in disgrace with his now former employer. However,
> due to all the knowledge he has collected he is afraid that he might
> be killed to ensure the confidentiality of this information. The spy
> therefore tries to turn this threat into a life insurence by arranging
> it such that if he gets killed, the information will be released in
> order to damage his former employer. He must, however, take care to
> ensure the confidentiality of the information while he lives, but to
> be as sure as possible to disclose the information if he is killed.
It seems that any solution to this problem based on simple secret
sharing among some set of N trusted people is vulnerable to a
Terminator attack: if M people are required to reconstruct the secret,
the employer kills N - M + 1 of them. Similarly, if M of N people are
required to *prevent* the information from becoming known (a sort of
distributed dead-man switch), these people become targets for any
organization which wants the information disclosed prematurely.
There is also the issue of when the arrangement should expire. Must
the secret be released if the spy dies of natural causes (e.g.
hit by a falling meteor)? What if there is some question as to
whether his death is natural (e.g. a heart attack which might be
caused by a hard-to-detect poison)?
The whole issue would make a fascinating book (or even a K-volume
series, where M <= K <= N).
--
## Jeremy Buhler * peace through superior algorithms * U. Washington ##
Daniel L. Bates
In article <4v32oj$c...@net.auckland.ac.nz>, jon...@ifi.uio.no says...
>
>
>
>
>An ongoing discussion ("Decrypt 100 years from now?") in sci.crypt
>made me post the following problem of mine. (Please excuse my bad
>English.) (TeX notation for the math: "$"s enclose math expressions.
>"\simeq" means "approximal equal to".)
>
>------------------------
>
>A spy has falled in disgrace with his now former employer. However,
>due to all the knowledge he has collected he is afraid that he might
>be killed to ensure the confidentiality of this information. The spy
>therefore tries to turn this threat into a life insurence by arranging
>it such that if he gets killed, the information will be released in
>order to damage his former employer. He must, however, take care to
>ensure the confidentiality of the information while he lives, but to
>be as sure as possible to disclose the information if he is killed.
>problem*. (Can anyone suggest a better name?)
>
>Suppose the spy knows $N$ persons he more or less trusts. That is,
>there is a probability of $p$ that any given (but arbitrary) person
>traitress, she will try to disclose the information immidiately, and
>if the spies dies, she will try to deny disclosure. I.e. the
>non-traitresses will keep the information secret as long as the spy
>lives and disclose the information if the spy dies, while a traitress
>will try to do the opposite. The spy must consequently try to minimize
>the chance that his arrangement will fail. To do this he encrypts the
>information one or several times and distributes the ciphertext and
>(some of) the keys (or information on how to generate the keys) to his
>collaborators. How should he do this? (Is this an old problem?)
>
Then choose at random an mth degree polynomial and use it to encrypt the one
key. then pick n point of the curve generated by the polynomial
(x[i],f(x[i])) Give each of the n persons the encrypted key and exactly one
of the (x[i], f(x[i])).
The polynomial can be solved given m of the n points. So when m people agree
the polynomial is known and the decrypted key is known.
RGDS,
DanB.
Abigail
[Added rec.puzzles again]
In rec.puzzles Jon Haugsand <jon...@ifi.uio.no> wrote:
++ THE PARANOID SPY PROBLEM
++ ------------------------
++
[...]
++
++ Suppose $(N,p)=(10,0.1)$. Find the best way to do it.
++
[...]
++ *Fourth try:* serial encrypt with 5 keys. Give each key to two
++ collaborators, such that each of them has exactly one of the keys.
++ Failure if two with the same key fail (refusal to decrypt) and if 5
++ with different keys fail (early disclosure).\\
++ $P[disclose] = 0.19^5 = 0.00025$,
++ $P[refusal] = 1-0.99^5 = 0.05$\\
++ $P[success] \simeq 0.95$
Let's try to even out the number of people needed for an early
disclosure and a refusal:
Fifth try:
There are 252 ways to select 5 people from the group of 10.
Serial encrypt with 5 keys in 252 different ways. Give each
person 126 keys. We have an early disclosure if any 5 fail,
or a refusal if any 6 fail. (Hence, we won't get a refusal if there
wasn't an early disclosure).
P[fail] = 252 * 0.1^5 = 0.00252
P[sucess] = 0.99748.
++ 1. Can you find the best arrangement and prove it really is the best?
++ What is the probability of success?
It's better than your fourth arrangement, but I can't prove it's
the best.
++ 2. Can you generalize it for arbitrary $N$ and $p$?
Let k = ceil (N/2), l = N - k.
Serial encrypt with k keys, in C(N,k) ways.
Find all C(N,k) subgroups of k people, and map all groups to
an encryption (1-1). Now, divide the k keys of each encryption
over the members of a group. Every one gets C(N,k)/2 keys.
Any k people can decrypt the information, and it takes
at least k people to decrypt. Hence, we get an early disclose
if k people fail, or a refusal if k + 1 people fail.
So, the changes of failure are when at least k people fail.
$P[fail] = C(N,k) * p^k, with k = ceil (N/2).
++ 3. If $p>0.5$, can $p[success]$ ever be greater than $0.5$?
Abigail
Jon Haugsand
Bryan Olson <Bryan...@jhuapl.edu> writes:
>
> Jon Haugsand wrote:
> >
> > Here I want to discuss a solution based on cryptographic techniques.
> > Suppose the spy knows $N$ persons he more or less trusts. That is,
> > there is a probability of $p$ that any given (but arbitrary) person
> > will fail
> [...]
>
> First, what we need is a secret sharing (threshold) scheme. A
> system in which m of n people can cooperate to recover a secret,
> and m-1 cannot is an (m,n) threshold scheme.
>
> > 1. Can you find the best arrangement and prove it really is the best?
> > What is the probability of success?
> 1. With a singe probability of failure I don't think we
> can know the best parameters, but if we assume that
> your p is both my p and q, a 5 (or 6) out of 10
> threshold is best, (obvious by symmetry?). I don't
> have a binomial table handy to find the numbers,
> but our spy's odds are very good.
>
Many have suggested this solution, but is it really the best? Only one
has proved his solution is the best, and it is slightly different. Let
us use a simpler example: (N,p) = (4,0.4). Your scheme gives: m=3 (or
2) and $P[success]=0.6^3*0.4*4 + 0.6^4 = 0.475.
Can anyone (except those two who found it) increase this?
Jon Haugsand
Doug McKean <doug_...@paragon-networks.com> writes:
>
> Jon Haugsand wrote:
> >
> > THE PARANOID SPY PROBLEM
> > ------------------------
> >
> > A spy has falled in disgrace with his now former employer. However,
> > due to all the knowledge he has collected he is afraid that he might
> > be killed to ensure the confidentiality of this information. The spy
> > therefore tries to turn this threat into a life insurence by arranging
> > it such that if he gets killed, the information will be released in
> > order to damage his former employer. He must, however, take care to
> > ensure the confidentiality of the information while he lives, but to
> > be as sure as possible to disclose the information if he is killed.
> > How to make such an arrangement I shall call the *Paranoid Spy
> > problem*. (Can anyone suggest a better name?)
>
Interesting. However, I cannot see immediately why more than one
lawyer should be in the chain. What threat model do you use? Moreover,
your solution breaks down if only one lawyer fails. (Maybe som cash
would help.)