From daw@joseph.cs.berkeley.edu Fri Aug 16 22:55:31 PDT 1996
Article: 56344 of sci.crypt
Path: agate!not-for-mail
From: daw@joseph.cs.berkeley.edu (David Wagner)
Newsgroups: sci.crypt
Subject: Re: The Paranoid Spy
Date: 16 Aug 1996 22:53:34 -0700
Organization: ISAAC Group, UC Berkeley
Lines: 156
Message-ID: <4v3mou$3rk@joseph.cs.berkeley.edu>
References: <4v32oj$c6g@net.auckland.ac.nz>
NNTP-Posting-Host: joseph.cs.berkeley.edu

In article <4v32oj$c6g@net.auckland.ac.nz>,
Jon Haugsand  <jonhaug@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