simply the one based on polynomial evaluation that sufficed for the proof
of Theorem <ref>, will do.  The particular locally-random
reduction of Theorem <ref> is easy to implement and very
efficient, so we use it directly.

Because the locally random reduction is in $NC^1$ (each $w_i$ is the
product of at most it can be secretly evaluated in constant rounds using
Theorem <ref>.  The system generates $N(n)$ sets of $n$ queries,
one set for each output bit.  The queries from each set are given to the
players individually.  The crux of the solution is that, though computing
the reduced functions $h^{nb}$ may be complicated, it is a local
computation requiring no interaction.

constant rounds!arbitrary functions

(Share $\hat{x}_1,\dots,\hat{x}_m.$)
Each player $i$ shares its input as
Variables $\hat{x}_{mn+1},\ldots,\hat{x}_{m}$ are taken to be 0.

(Expand variables.)
Compute new secrets $w_1,\dots,w_{r}$ by running protocol
to evaluate $w_i(\hat{x}_1,\dots,\hat{x}_m).$

(Select LRR.)
Select $rt$ random secrets $p_1^1,\dots,p_1^t;\ldots;p_r^1,\dots,p_r^t,$
using protocol .  These denote the higher coefficients of
polynomials $p_i(u)=w_i + \sum_j p_i^j u^j.$

(Apply LRR.)
Using protocol , compute new secrets
$w^i_j = p_j(\alpha_i)$ for $i=1..n,$ $j=1..r,$ in parallel.
Reveal $(w^i_1,\dots,w^i_r)$ to player $i.$

(Compute reduced problem locally.)
Each player $i$ computes

\[
v_i^b=h_F^{nb}(w^i_1,\dots,w^i_r)  \hspace{0.3in}  1 \leq b \leq N(n)
\]

and secretly shares $(v_i^1,\ldots,v_i^{N(n)})$ among the network.

(Protect against Byzantine failures.)
Run Protocol ($i,j$) for each $1\leq i,j \leq n;$
thus each player $i$ proves to the network in zero-knowledge that

\[
(F^{n1}(w^i_1,\dots,w^i_r),\ldots, F^{n,N(n)}(w^i_1,\dots,w^i_r))
\]

* Each player $j$ broadcasts a vote as to whether each player $i$ gave him a
satisfactory proof in step <ref>.  Disqualify each player $i$ who
is impeached by a majority; reveal its query
and use

\[
v_i^b=h_F^{nb}(w^i_1,\dots,w^i_r)  \hspace{0.3in}  1 \leq b \leq N(n)
\]

as publicly known constants for the remainder of the protocol.

(Reconstruct $f.$) Run protocol to secretly interpolate
each set $(v_1^b,v_2^b,\ldots,v_n^b),$ for $b=1..N(n)$ in parallel.
For each set, obtain the free term $y^b$ of the polynomial of degree $rt$
passing through the points.

Protocol to evaluate any $F$ in constant rounds and low fault-tolerance.

Locally random reductions, however, are not necessarily robust against
errors in the reduced computations.  Reducing the overall computation to
locally independent computations suffices for privacy but not for
robustness.  Thus we need to verify that the results of
step <ref> are accurate before using them to interpolate the
final answer.

Let us expand upon step <ref>.  Each player $i$ gives a ZKMIPS
proof (<ref>) to each player $j$ that the secret value of
$v_i^b$ it shared satisfies $v_i^b=h_F^{nb}(w^i_1,\dots,w^i_r),$ using the
methods of Chapter <ref>.  This is not quite sufficient per
se, since a faulty player may cause some good players to believe the proof
while others find fault.  Thus, after the proving phase, every player $j$
broadcasts a vote $V_{ji}$ as to whether it believes the proof of player
$i.$ If a majority vote to accept $i,$ then player $i$ is accepted.  A
majority vote in favor of player $i$'s honesty implies that at least one
reliable player found player $i$ correct, which means that player $i$ was
able to prove its correctness to someone, and its results are therefore
correct. If player $i$ is rejected by the vote, it failed to satisfy any
reliable player of its behavior, and the query $(w^i_1,\dots,w^i_r)$ with
which it is supposed to compute is revealed so that the reliable players
may incorporate it properly.

Thus, we have specified eight function families corresponding to the eight
modules of the protocol.  Each of these computes a robust and private
representation of its results (small lists of questions from the reductions
are independent of the inputs and hence private; the $v$ values are robust
given that the zero-knowledge proofs succeed, or else they are broadcast
implicitly through the revelation of $w^i_1,\ldots,w^i_r$; pieces of the
various secrets are robust and private representations).  By
Theorem <ref>, the composition is $t$-resilient.

The number of rounds is constant, by the following observations.
Step <ref> is an evaluation of several polynomials $w_i$ of
degree $2^q,$ which is an $NC^1$ computation.  By Theorem <ref>,
this takes constant rounds and polynomial message sizes.

Step <ref>, the selection of $n$ random polynomials of degree $t$
with free terms $p_1^1,\dots,p_1^t;\ldots;p_r^1,\dots,p_r^t,$ requires the
secret choice of $rt$ coefficients.  The selection of these random secret
values is performed in parallel and requires constant rounds.
Applying polynomials $p_1,\dots,p_r$ to the known, fixed values
$\alpha_1,\dots,\alpha_n$ is a linear combination and hence requires no

Each player $i$ computes $h_F^{nb}$ locally and non-interactively,
and its resharing requires polynomial bits and constant rounds.
The zero-knowledge proofs of step <ref> are slightly
more complicated yet still require constant rounds and polynomial
message sizes.
The interpolation of $y^b$ from $v_1^b,\dots,v_{n}^b,$
step <ref>, uses an $NC^1$ circuit.

tocpartApplications and Conclusions

CHAPTER: APPLICATIONS

The artist possesses the ability to breathe soul into the lifeless
product of the machine.

Walter Gropius

The bulk of this dissertation has addressed formal specifications of
protocols for networks of players to compute arbitrary functions in a
distributed manner.  In this chapter we present efficient and
practical solutions for useful and important computations.

It would certainly be impractical to require multiparty protocols around
each distributed computation a collection of processors must make.  Some
computations, especially administrative and system-security oriented
computations, are of greater importance than others, but at the same time
need to be performed less often.  For example, authenticating a user or a
remote process must be correct and secure but are performed with lower
frequency than other computations.  Authorizing access to a file is another

We propose very fast protocols for authenticationauthentication,
authorizationauthorization, and anonymous mailanonymous
mail. These protocols are designed with specific goals in mind and
capitalize on properties that a general-purpose protocol-compiler (based
only on circuit specifications) ignores.

For the purposes of ensuring distributed system reliability, we envision a
security kernel,security kernel in terms of processors and of
processes.  That is, not all the processors in a network need be involved
in ensuring the resilience of every computation.  A specific committee of,
say, seven processors would suffice, with the assurance that no more than
three are compromised.  These processors are tightly coupled with
high-speed secure communication lines.

With respect to the operations themselves, we propose that authentication
and authorization are infrequent yet essential computations, and that it is
reasonable to take special care to ensure the correct and secure operation
of a small body of desired processes.  Once a process has been
authenticated and authorized to read a file, the authorization need not be
repeated and the authentication can be omitted during repeated file access

The Secure UNIX of Reeds and McElroy [93, 94, 95, 108] adopts
this sort of approach, allowing two remote processes to communicate over a
single pipe that excludes other processes and that fails as soon as one
process detaches.  While this does allow certain attacks to succeed — a
corrupt operating system might capture an authorized line to a remote
system by running an authenticated process and substituting its own process
after the authentication with the remote host has occurred — the attacks
are more difficult and complex.  Furthermore, a repeated authentication of
the host operating system, not each individual process at each
individual request, would serve as a more efficient safety check.  If the
host is continually authenticated then presumably its operations are valid
and the processes it runs cannot be substituted after their initial
authentication.  This is a reasonable trade-off of absolute security for

Our efficient algorithms for specific tasks support the approach of
infrequent yet highly efficient and secure kernel operations.  We focus not
simply on achieving a constant number of rounds of interaction but on
achieving a small constant number of rounds, on the order of 2 or 3.

§ ON STRONG ASSUMPTIONS

In general, we assume a completely connected, synchronous network with
private linesassumptions!noncryptographic.  The robustness of
polynomial interpolation suggests the techniques developed here should be
adaptable to asynchronous models.  The fault-tolerance levels would be
lower, and many technical issues must be considered (such as the
availability of broadcast channels vs. Byzantine Agreement
subprotocols).  Because our protocols are robust against fail-stop faults,
their extension to problems of asynchronicity is natural.

A network without private lineschannel!private can still use the
protocols developed here if suitable encryption of the lines is available.
Care must be taken to ensure that this approach of treating sub-issues in a
modular fashion does in fact treat each module independently — for
example, to avoid unintended interaction between the design of the overall
protocol and the design of a communication line protection scheme, the same
encryption methods should not be used at all levels.  That is, if a
protocol assumes a private channel but also requires an encryption for
other reasons, the same encryption should not be used to replace the
private channel with an encrypted channelchannel!encrypted.
Proofs of security remain necessary.

We have also assumed a complete networknetwork!complete.  This
assumption is highly unlikely to hold except on a local-area network.  In
practical terms, however, it is not hard to achieve for a processor
security kernel with a small number of tightly-coupled processors.  In
theoretical terms, the issue of simulating a complete network using a
$t+1$-connected network is an interesting separate subproblem.

The modular treatment of the various subproblems provides optimism for the
design of very general protocols that are robust under very harsh
circumstances.  A word of caution must be interjected: as always, intuitive
claims to security require formal treatment.  But the modular approach
makes the analysis easier.

§ CHOICE OF FIELD

For the purpose of implementation, we suggest a few natural finite fields.

The first is $\gf(257),$ the set of integers modulo 257.  This field easily
encodes bytes using integers in the range 0—255.  Modular arithmetic is
fast and standard, though individual bit operations on the eight bits are
not quite so facile.  Two-byte words are supported by a modulus of

The other fields we suggest have characteristic 2: $\gf(256)=\gf(2^8),$
$\gf(65536)=\gf(2^{16}),$ $\gf(2^{32}),$ and $\gf(2^{64}),$
Field elements are represented as polynomials over $\gf(2)$ modulo an
irreducible polynomial (for example, $x^8+x^4+x^3+x^2+1$ for
$\gf(2^8),$ $x^{16}+x^{12}+x^3+x+1$ for $\gf(2^{16}),$ and
$x^{32}+x^{22}+x^2+x+1$ for $\gf(2^{32})$).

Each coefficient is a single bit, so that the field elements themselves
correspond naturally to common word-sizes.  Addition over these fields is
quite simple and normally requires a single machine instruction: take the
bitwise exclusive-or.  Multiplication is somewhat more complicated,
requiring one to reduce the product modulo the appropriate irreducible
polynomial, but fast algorithms exist.

Generating random bits as the exclusive-or of random bits supplied by
many players is much easier using a field of characteristic 2 than one of
characteristic 257, since addition of random secret 0/1 values will
suffice.  In general, bitwise operations are facilitated by using
arithmetic over a field of characteristic 2.

§ A FAST AND PRACTICAL PASSWORD SCHEME

In the UNIX$^{tm}$ passwordpassword scheme for user authentication,
the passwords are not stored in a file on the system.  Rather, each
password is encrypted (using a DES-like encryption function) and the result
is stored in a password file.  Even if the password file is compromised, an
attacker cannot learn the passwords directly from the file.  When a user
would like to log in to the system, his attempted password is encrypted and
compared against the stored encryption.  If they match, the user is

One can imagine a generalization to the distributed environment in which
each host authenticates the user and the system as a whole considers the
user acceptable if a majority of the hosts have authenticated him.  An
immediate problem surfaces with password schemes: if the same password is
used for all the hosts, then a single corrupt host will learn the user's
global password when the user requests authentication.  This can be
circumvented by having a different password for each host (requiring some
nontrivial and probably security-prone bookkeeping by the user).
Nevertheless, there are many disadvantages, including the fundamental
problem that the encryption function itself is only assumed to be

We propose a simple and efficient password scheme
This work was done while the author was on leave of absence from Harvard
University in the spring and summer of 1988.]

discovered independently by Michael Rabin [105] that has some
similar properties but does not depend on the security of an encryption
function like DES.  That is, passwords cannot be obtained by capturing the
files on some fraction of the systems, and are certainly not compromised
during an execution in which one of the hosts is corrupt.  In order
to break the password directly, an attacker must corrupt a majority of the
hosts (we ignore dictionary searches and repeated attempts, which are
certainly valid issues for any password scheme but are orthogonal to the
problem of breaking the system directly).

The basic idea is as follows: a user secretly shares his password
$\password$ among the system at start-up.  Later, when he requests
authentication, he demonstrates his knowledge of the password by sharing it
again.  Let us call the second secret his attempt, $\attempt.$ The system
must compare $\password$ to $\attempt$ without revealing $\password$.

Let $E=\gf(2^{64}).$

User shares $\password.$

Each host $i$ selects two uniformly random 64-bit elements $r_i,s_i,$
and shares them.

Run the protocol (non-interactively) to secretly compute

$r=\sum r_j, s=\sum s_j:$

— More precisely, each host $i$ sets

$\piece_i(r) = \sum_j \piece_i(r_j)$

$\piece_i(s) = \sum_j \piece_i(s_j)$

Protocol to initialize a user's password in a distributed system of
$n$ hosts.

It does not suffice to compute $(\password - \attempt)$ and reveal the
result, since knowing $\attempt$ would then reveal $\password.$ This
remains true even if the user is not supplied with the result; if the
user cooperates with just one corrupted host involved in the
authentication, then that host can reveal the result when it learns it.

One solution is to use Theorem <ref> to secretly compute
$\norm{\password - \attempt}$ in a constant number of rounds.  The protocol
most certainly is correct and uses only a few rounds, but we propose an
even simpler and more efficient protocol that is designed with the
particular password problem in mind.

The essential information that the system must compute is whether or not
$\password = \attempt.$ The result of the computation should specify
whether or not they are equal, but it need not be a deterministic result;
that is, the result need not be either 0 or 1.  What matters is that if the
values are not equal, the result of the computation should have the same
distribution regardless of what attempt is made and of what the password
is.  The problem of revealing information about the password through a
failed attempt is then solved.

The trick is the following: compute and then reveal $(\password -
\attempt)\cdot r,$ where $r$ is secret and uniformly random over $E -
\set{0}.$ If the attempt is correct, then the result is always 0.  But if
the attempt is invalid, then the result will be a uniformly distributed
nonzero random field element, for any $\password$ and $\attempt.$ Thus, no
information about $\password$ or $\attempt$ is revealed by the result, apart
from whether they are identical or not.  The system accepts the user if and
only if the result is 0;
each host outputs accept if the result is 0 and otherwise outputs

The only minor inefficiency is to generate a nonzero random field element.
The protocol will generate a uniformly random secret $r$ in
$E,$ but we should then have to normalize it in order to test if $r=0,$
returning us to the original problem.  One simple and acceptable approach
is simply to finesse the problem by using a large field $E$ so that the
chance that $r=0$ is negligible.  This would allow some very low
probability that a failed attempt will succeed.  In fact, the chance of
such an event is the same as guessing a valid password.  See
Figure <ref>.

User shares $\attempt.$

Run the protocol (non-interactively) to secretly compute
$v=\password - \attempt.$

— More precisely, each host $i$ sets

$\piece_i(v) = \piece_i(\password) - \piece_i(\attempt)$

To be ready for the next authentication,
each host $i$ selects two uniformly random 64-bit elements
$r_i^{new},s_i^{new},$ and shares them.  Each host $i$ sets

$\piece_i(r^{new}) = \sum_j \piece_i(r_j^{new})$

$\piece_i(s^{new}) = \sum_j \piece_i(s_j^{new})$

Run the protocol to secretly compute $w=v \cdot r.$

$w=0$ accept the user, reject the user.

Protocol to authenticate user who has already shared password $\password.$

The chance that the scheme is broken through this error is less than that
of randomly selecting a password, and it is neither repeatable (the user
has no control over $r$) nor assisted by ulterior means (such as dictionary
lookups).  It therefore doubles at most the inherent chance of failure.
Figure <ref> describes the stripped-down scheme.  One round
suffices to share the attempt, and one to check it (with only fail-stop

A completely accurate solution is the following: generate a second random
secret, $s,$ and multiply it by $r.$ If the result is nonzero, then the
system has a proof that $r \not=0$ without revealing $r.$

The chance that randomly choosing $r$ and $s$ gives $r=0$ or that $r\not=
0$ and $s=0$ is small: $\frac{2 \mid E \mid -1}{\mid E\mid^2}.$ Otherwise,
with high probability the system has generated a uniformly random nonzero
secret $r,$ along with a (“zero-knowledge”) certificate that $r
\not= 0.$

For concreteness, let us use the field $\gf(2^{64})$ to handle passwords of
8 bytes.  The password set-up protocol is described in
Figure <ref>.  The authentication protocol is described in
Figure <ref>.  Note that in the authentication protocol, a failure
to obtain a nonzero secret $r$ requires that the network generate one; this
occurs with probability $2^{-64}$ and can essentially be ignored.

User shares $\attempt.$

Run the protocol (non-interactively) to secretly compute
$v=\password - \attempt.$

— More precisely, each host $i$ sets

$\piece_i(v) = \piece_i(\password) - \piece_i(\attempt)$

To be ready for the next authentication,
each host $i$ selects two uniformly random 64-bit elements
$r_i^{new},s_i^{new},$ and shares them.  Each host $i$ sets

$\piece_i(r^{new}) = \sum_j \piece_i(r_j^{new})$

$\piece_i(s^{new}) = \sum_j \piece_i(s_j^{new})$

Run the protocol to secretly compute $w=v \cdot r.$

Run the protocol to secretly compute $u=r \cdot s.$

(Refer to $r^{new}$ as $r$ and $s^{new}$ as $s.$)

Reconstruct $w$ and $u.$

$u \not= 0$ :

$w=0$ accept the user, reject the user.

$u=0$ repeat step (A2).

Protocol to authenticate user who has already shared password $\password.$

For $2t<n,$ protocol is statistically $t$-resilient and requires
a constant expected number of rounds.

Clearly, host $i$ outputs accept iff $r \not= 0$ and
$(\password-\attempt)\cdot r = 0,$ i.e. iff $\password = \attempt.$
If $\password=\attempt,$ the distribution on $(w,u)$ is

\[
\set{r \leftarrow \uniform(E); s \leftarrow \uniform(E): (0,rs) },
\]

regardless of the values of $\password$ and $\attempt.$
If $\password \not= \attempt,$ the distribution on $(w,u)$ is the

\[
\set{r \leftarrow \uniform(E); s \leftarrow \uniform(E):
((\password-\attempt) \cdot r,rs)},
\]

which for any (unequal) values of $\password$ and $\attempt,$
is fixed and identical to

\[
\set{r \leftarrow \uniform(E); s \leftarrow \uniform(E);
w \leftarrow \uniform(E-\set{0}): (w,rs)}.
\]

For $2t<n,$ Protocol is $t$-resilient against passive (or even
fail-stop) adversaries and requires only $(3+\epsilon)$ expected rounds,
where $\epsilon=4/\abs{E}$ is small.

Follows from Theorem <ref> and the observation that, when messages
are always correct, the number of rounds required for sharing and for
multiplying secrets is 1.  Step (A2) is repeated with probability
$\frac{2 \mid E \mid -1}{\mid E\mid^2},$ which gives an expected time
less than $4/\abs{E}$ when $\abs{E}\geq 7.$

Remark:  The secure authentication schemes we have
presented take the same amount of time as the simple method of having a
user authenticate itself to each processor separately and then taking a
vote.  They provide, on the other hand, a good deal more robustness.  For
example, once an intruder has recorded the message from a valid user to one
host in the voting scheme, that password can be re-used; the invader need
only accumulate enough attacks over time.  In our scheme, however, at least
half of the communications must be tapped simultaneously to obtain
any information at all.

§.§ Unanimous Secret Ballots

Secret ballots are fast and simple (<ref>), and by
Theorem <ref>, checking whether a secret vote is unanimous or
not, without revealing the tally, also admits a protocol in constant
rounds.  The authorization techniques listed above suggest a faster and
more direct method: first compute $v=\sum_i x_i,$ where each $x_1$ is a
verified 0/1 secret vote, generate a random (nonzero) secret $r,$ and
secretly compute $vr.$ Reveal the result.  If the ballot is unanimous, the
result will be 0; otherwise it will be a uniformly distributed nonzero

§ ANONYMOUS MAIL

anonymous mailmail

A mail system ought to provide privacy on two levels.  First, it should
hide the contents of each message from the general public, and certainly
from those involved in its delivery.  Second, it should not need to
identify the sender of the message, either to those involved in the
delivery or to the recipient.  It does not suffice simply to deliver a
message without attaching a sender's name in the header, since the name of
the originating host or workstation may be enough to reveal the sender.  In
fact, the delivery of anonymous messages in a network is powerful enough to
support general function computation [6], though we shall not go
into the details here.  Delivering mail anonymously even when hosts are
identified is thus a powerful and a useful tool.

To be practical, however, a mail scheme must be efficient.  If the message
is an undivided unit, then it traverses some path from the sender S to the
receiver R.  If every host on that path is corrupt, then the receiver can
identify the origin.  Thus the path must be longer than the number $t$ of
corruptible hosts.  Already this is a very inefficient solution.
Furthermore, it requires that the message be encrypted in some form so that
the intermediate hosts cannot read the contents.

We adopt a different approach: divide the message in an appropriate manner
and send each portion via a different path.  If sufficiently few pieces are
captured, then nothing is learned about the contents.  Secretly sharing the
message and reconstructing it for the recipient suffices.  This is trivial
in a complete network with private channels, but in an incomplete network,
when two players may be forced to communicate via intermediate players,
secret sharing solves the problem of privacy robustly.

Preserving the privacy of the sender, however, is a slightly more difficult
goal.  We must ensure that the paths to R do not identify S.  Thus, the
direct approach of as secretly sharing the message and reconstructing it
for R is suggestive, but not sufficient.  Every host knows who shared
the secret.

Consider the following situation: there is some secret permutation $\sigma$
on the elements $\set{1,\ldots,n},$ and each player $i$ knows $\sigma(i).$
Each player $i$ would like to send a message $M(i)$ to player $\sigma(i)$
without identifying itself.  We would like to compute a function $F$ such
that $F_{\sigma(i)}(M(1),\ldots,M(n),\sigma(1),\ldots,\sigma(n)) =M(i).$

One method to perform this computation would be to compute

\[
F_j(M(1),\ldots,M(n),\sigma(1),\ldots,\sigma(n) =
\sum_{i=1}^n M(i) \delta(\sigma(i),j)\index{delta}
\]

Because the delta function is in $NC^1,$ Theorem <ref> implies
there is a constant-rounds protocol to compute $F.$  Note that we have
omitted a verification that the secrets $\sigma(1),\ldots,\sigma(n)$ do
indeed define a permutation; malicious players could upset the protocol.
An additional function that compares each pair of destinations and makes
sure no collisions occur is a necessary prerequisite.

A more efficient way is the following.  Each player, instead of sharing
$\sigma(i),$ shares a set of $n$ secrets $d(i,1),\ldots,d(i,n),$ such that
$d(i,\sigma(i))=1$ and the remaining secrets are 0.  It is trivial to check
privately that every $d(i,j)$ is 0 or 1 by computing and revealing
$d(i,j)(d(i,j)-1).$ It is also trivial to ensure that each player shares a
valid vector, by computing $\sum_j d(i,j)$ for each $i$ and revealing the
sums.  Thirdly, it is trivial to check for collisions by taking $\sum_i
d(i,j)$ for each $j$ and revealing the sums.  (Collisions give a sum
greater than 1, which reveals no information to the faulty processors that
changed their destinations.)  Thus there are three simple verifications to
perform in parallel, requiring the time of one multiplication and

Given verified vectors, the final outputs are simply

\[
F_j(M(1),\ldots,M(n),d(1,1),\ldots,d(n,n)) =
\sum_{i=1}^n M(i) d(i,j).
\]

This construction gives an easy solution to the converse problem, limited espionage.espionage

[The terms espionage and anonymous mail were suggested
by M. Rabin.]

Like 1-out-of-2 Oblivious Transfer, in which the recipient chooses one of
two values to learn but the holder does not find out which, limited
espionage allows each player in the network to learn one secret from a list
of $N$ secrets without revealing which one it chose.  The protocol requires
each player to share a 0/1 vector specifying a 1 in the component
corresponding to the secret it desires, and the verifications are performed
as above before computing the simple weighted sum.  Note that in this case,
collisions need not be avoided; two players may look at the same secret.

The general problem of supporting arbitrary maps from sources to
destinations and multiple messages from a single player is somewhat more
involved.  Allow each player to send some number $N$ of messages to any
other player.  The set $\set{M(i,j,k) \mid i,j\in [n], k \in [N]}$
describes the list of all messages.  Player $i$ secretly shares each
$M(i,j,k)$ as a secret $s(j,(i-1)nN+k).$ The goal is to construct a random
secret permutation $\sigma \in {\cal S}_{nN}$ for each $j,$ and apply it to
the secrets $s(j,1),\ldots,s(j,nN)$ destined for player $j.$  The permuted
list of results hides the origins and is revealed directly to player $j.$
To generate a random secret permutation $X(j)$ on $nN$ indices, protocol
of <ref> suffices, using 0/1
matrices to represent permutations.  The permuted list of results for
player $j$ is computed by secretly multiplying the matrix $X(j)$ by the
vector of secrets $(s(j,1),\ldots,s(j,nN)).$

While mathematically correct, the size of the matrices makes this solution
prohibitive.  In a more practical vein, a different sort of approach is
preferable.  The approach used in delivering mail whose destinations are a
permutation of the sources is useful.  We provide each player $j$ with a
set of $n$ “mailboxes,” namely a fixed set of secrets $b(j,l).$ Each
mailbox has a corresponding set of flags $c(j,l)$ that indicate whether one
or more players have attempted to place a message in the mailbox.  The
protocol is simple: player $i$ sends a message $M(i,j,k)$ to player $j$ by
choosing a mailbox $(i,l)$ at random and sharing $M(i,j,k)$ as a secret
value $B(j,l,i)$ and sharing $C(j,l,i)=1.$ Other $C(j,l,i)$ values are
shared as 0.  The 0/1 verification is easy, and it is easy to bound the
number of messages sent by each player.

Finally, the players secretly compute $b(j,l)= \sum_i B(j,l,i)$ and
$c(j,l)= \sum_i C(j,l,i).$ Each $b(j,l)$ and $c(j,l)$ is revealed to player
$j,$ who detects if there is a collision by virtue of $c(j,l)>1.$ Each
player announces the boxes containing collisions and the protocol is
repeated so that the senders can try again.  By choosing the number of
mailboxes sufficiently large for the expected traffic — a practical issue
— the expected number of repetitions is small.

CHAPTER: CONCLUSIONS

Forsan et haec olim meminisse iuvabit.
[Perhaps this will be a pleasure to look back on one day.]

Virgil, the Aeneid

The issues of this dissertation are three-fold.  First, reliability and
security are best ensured by avoiding assumptions that particular
processors are reliable.  Second, proving the security and reliability of
distributed protocols requires clear and concise definitions.  Our
definition of resilience captures security and reliability simultaneously
and a priori captures all the intuitive properties one expects of a
robust system.  Third, theoretical protocols are interesting, but to be
practical a higher standard of efficiency must be met.  Protocols requiring
more than a dozen rounds of interaction are likely to be too complex or too
inefficient to be implementable; low communication complexity is of utmost

In general, we have made some strong simplifying assumptions, such as the
presence of a complete, synchronous network with private channels.  These
issues are of deep practical and theoretical significance, but we place
them aside in the hope that a modular approach provides a deeper
understanding of the fundamental nature of security and reliability in
interactive protocols.  Chapter <ref> (<ref>)
discusses the incorporation of solutions for underlying network problems.
The robustness of our protocols against message omissions and fail-stop
faults suggests a cautious optimism that, with appropriate formal proofs,
they can be provided with modular subroutines to withstand a weakening of
the simplifying assumptions.

The understanding of security and reliability has been hampered by a lack
of formal proofs and definitions.  Much current research develops
techniques that are intuitively secure but which have not been proven
secure.  We provide a definition for resilience that solidifies the
foundations of research into security.
Precise definitions of standard properties such as correctness and privacy
fall out as an easy consequence.  We believe that all the desirable
properties of security and reliability are captured a priori by
considering the ideal protocol as our standard of computational
resilience.  Privacy, correctness, and other properties are aspects of the
same definition, tied together by the idea of an ideal, trusted party,
and measurable by the idea of relative resilience.

Our definition for resilience provides not just a means to rate the
security of a protocol with respect to an ideal situation but a means
to compare arbitrary protocols.  The ability to measure relative resilience
provides a greater flexibility and modularity in proof techniques and
protocol design.  Rather than directly prove a protocol is secure, one can
compare it to an intermediate protocol that is itself proven secure.
Relative resilience also provides a conceptually easier means to show when
protocol concatenation preserves the security of the protocols, a very
important issue that is often difficult to analyze.

It remains to be seen if unconditional security, high fault-tolerance,
highly complex function computation, and low communication complexity can
be achieved simultaneously.  For functions of arbitrarily high complexity,
the locally random reductions of Chapter <ref> provide low
communication complexity, but at a cost of lower ($O(\log n)$) fault
tolerance.  Chapter <ref> achieves low communication complexity
and high fault-tolerance, but the results are conditioned on the existence
of a one-way function.  If the computational complexity of the function is
restricted, Chapter <ref> demonstrates that
low communication complexity and low local computational
complexity are simultaneously achievable.

Locally random reductions with better parameters — i.e. a higher
ratio of the independence-set size $k$ to the number $m$ of queries — are
one path to achieving higher fault-tolerance for arbitrarily complex
functions while using a constant number of rounds.  A characterization of
the achievable parameters for locally random reductions would be of general
interest beyond serving simply to provide more secure protocols.

We have separated the communication complexity of secure computation from
the computational complexity of the desired result.  This bodes well for
practical implementations, but is more striking from a theoretical
standpoint.  The crucial tool of locally random reductions vastly
reduces upper bounds on the number of rounds of communication for a
variety of cryptographic protocols.  In a deeper sense, it has triggered
other research leading to a result, $\ip=\pspace,$ which relates a
complexity class associated with interaction to a complexity class
associated with computational complexity.  The algebraic nature of the
locally random reductions we develop suggests not only wide
applications but a deeper understanding of the nature of interaction,
computational complexity, and reliable computation.

[1]
M. Abadi, J. Feigenbaum, J. Kilian.
“On Hiding Information from an Oracle.”
J. Comput. Systems Sci. 39 (1989), 21–50.

[2]
D. Angluin, L. Valiant.
“Fast Probabilistic Algorithms for Hamiltonian Paths and Matchings.”
J. Comput. Systems Sci. 18 (1979), 155–193.

[3] L. Babai, L. Fortnow, C. Lund.
“Non-Deterministic Exponential Time has Two-Prover Interactive Proofs,”

Submitted to FOCS, IEEE, 1990.

[4]
L. Babai, S. Moran.
“Arthur-Merlin Games: A Randomized Proof System,
and a Hierarchy of Complexity Classes.”
J. Comput. System Sci.  36 (1988), 254–276.

[5]
J. Bar-Ilan, D. Beaver.
“Non-Cryptographic Fault-Tolerant Computing
in a Constant Expected Number of Rounds of Interaction.”
Proceedings of PODC, ACM, 1989, 201–209.

[6]
J. Bar-Ilan, D. Beaver, M. Rabin.
Personal communication, 1988.

[7]
D. Barrington,
“Bounded Width Polynomial Size Branching Programs
Recognize Exactly those Languages in  $NC^1.$ ”
Proceedings of the $18^{th}$ STOC, ACM, 1986, 1–5.

[8]
D. Beaver.
“Distributed Computations Tolerating a Faulty Minority,
and Multiparty Zero-Knowledge Proof Systems.”
J. Cryptology, 1990.
A preliminary version appeared as,
“Secure Multiparty Protocols Tolerating Half Faulty Processors,”
in Proceedings of Crypto, ACM, 1989, and in Technical Report
TR-19-88, Harvard University, September, 1988.

[9]
D. Beaver.
“Perfect Privacy for Two-Party Protocols.”
Proceedings of the DIMACS Workshop on
Distributed Computing and Cryptography, Princeton, NJ, October, 1989,
J. Feigenbaum, M. Merritt (eds.).
Preliminary version in TR-11-89, Harvard University.

[10]
D. Beaver.
“Formal Definitions for Secure Distributed Protocols.”
Proceedings of the DIMACS Workshop on
Distributed Computing and Cryptography, Princeton, NJ, October, 1989,
J. Feigenbaum, M. Merritt (eds.).

[11]
D. Beaver, R. Cleve, S. Goldwasser.
In preparation, 1989.

[12]
D. Beaver, J. Feigenbaum.
“Hiding Information from Several Oracles.”
Harvard University Technical Report TR-10-89, May 1, 1989.

[13]
D. Beaver, J. Feigenbaum.
“Encrypted Queries to Multiple Oracles.”
AT&T Bell Laboratories Technical Memorandum, August 14, 1989.

[14]
D. Beaver, J. Feigenbaum.
“Hiding Instances in Multioracle Queries.”
Proceedings of the the $7^{th}$ STACS,
Springer–Verlag LNCS 415, 1990,

[15]
D. Beaver, J. Feigenbaum, J. Kilian, P. Rogaway.
“Cryptographic Applications of Locally Random Reductions.”
Proceedings of Crypto 1990.
Also appeared as
AT&T Bell Laboratories Technical Memorandum, November 15, 1989.

[16]
D. Beaver, J. Feigenbaum, V. Shoup.
“Hiding Instances in Zero-Knowledge Proof Systems.”
Proceedings of Crypto 1990.

[17]
D. Beaver, S. Goldwasser.
“Multiparty Computation with Faulty Majority.”
Proceedings of the $30^{th}$ FOCS, IEEE, 1989, 468–473.

[18]
D. Beaver, S. Goldwasser, Y. Mansour.
Personal communication, 1989.

[19]
D. Beaver, S. Haber, M. Yung.
In preparation, 1989.

[20]
D. Beaver, S. Micali, P. Rogaway.
“The Round Complexity of Secure Protocols.”
Proceedings of the $22^{st}$ STOC, ACM, 1990, 503–513.

[21] C. Bennett, G. Brassard, C. Crépeau.
Personal communication, 1989.

[22]
M. Bellare, L. Cowen, S. Goldwasser.
“On the Power of Secret Key Exchange.”
In preparation, 1989.

[23]
J. Benaloh.
“Verifiable Secret Ballot Elections”
PhD Thesis, Yale University, 1987.

[24]
M. Ben-Or, R. Cleve, “Computing Algebraic Formulas
Using a Constant Number of Registers.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 254–257.

[25]
M. Ben-Or, O. Goldreich, S. Goldwasser, J. Hastad,
J. Kilian, S. Micali, P. Rogaway.
“Everything Provable is Provable in Zero-Knowledge.”
Proceedings of Crypto 1988, Springer–Verlag, 1990.

[26]
M. Ben-Or, O. Goldreich, S. Micali, R. Rivest.
“Fair Contract Signing.”
Proceedings of the ICALP (1985).

[27]
M. Ben-Or, S. Goldwasser, J. Kilian, A. Wigderson.
“Multi-Prover Interactive Proofs: How to Remove Intractability.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 113–131.

[28]
M. Ben-Or, S. Goldwasser, A. Wigderson.
“Completeness Theorems for Non-Cryptographic Fault-Tolerant
Distributed Computation.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 1–10.

[29]
M. Ben-Or, R. El-Yaniv,
“Interactive Consistency in Constant Expected Time.”
Unpublished Manuscript, 1988.

[30]
S. Berkowitz.
“On Computing Determinant in Small Parallel Time Using a Small
Number of Processors.”
Info. Proc.   Letters 18:3 (1984), 147–150.

[31]
“Security Proofs for Information Protection Systems.”
Proceedings of the the 1980 Symposium on Security and Privacy,
IEEE Computer Society Press, NY (1981), 79–88.

[32]
M. Blum, S. Kannan.
“Designing Programs that Check Their Work.”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 86–97.

[33]
M. Blum, L. Levin, M. Luby.
“If Permanent with the Uniform Distribution
is in Average Polynomial Time then $\#$P $\subseteq$ ZPP.”
Unpublished Manuscript, October 31, 1989.

[34]
M. Blum, M. Luby, R. Rubinfeld.
“Self-Testing/Correcting with Applications to Numerical Problems.”
Preprint, November, 1989.

[35]
M. Blum, M. Luby, R. Rubinfeld.
“Program Result Checking Against Adaptive Programs
and in Cryptographic Settings.”
Proceedings of the DIMACS Workshop on
Distributed Computing and Cryptography, Princeton, October, 1989.

[36]
M. Blum, M. Luby, R. Rubinfeld.
“Stronger Checkers and General Techniques for Numerical Problems,
Proceedings of the $22^{nd}$ STOC, ACM, 1990, 73–83.

[37]
M. Blum, S. Micali.
“How to Generate Cryptographically Strong
Sequences of Pseudo-Random Bits.”
SIAM J. Comput. 13 (1984), 850–864.

[38]
G. Brassard, D. Chaum, C. Crépeau.
“Minimum Disclosure Proofs of Knowledge.”
J. Comput. System Sci. 37 (1988), 156–189.

[39]
D. Chaum, C. Crépeau, I. Damgaard.
“Multiparty Unconditionally Secure Protocols.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 11–19.

[40]
D. Chaum, I. Damgaard, J. van de Graaf.
“Multiparty Computations Ensuring Secrecy of Each Party's Input
and Correctness of the Output.”
Proceedings of Crypto 1987, Springer–Verlag, 1988.

[41]
H. Chernoff.
“A Measure of Asymptotic Efficiency for Tests of a Hypothesis
Based on the Sum of Observations.”
Annals of Math. Statistics 23 (1952), 493–507.

[42]
B. Chor, S. Goldwasser, S. Micali, B. Awerbuch.
“Verifiable Secret Sharing and
Achieving Simultaneity in the Presence of Faults.”
Proceedings of the $17^{th}$ STOC, ACM, 1985, 383–395.

[43]
B. Chor, E. Kushilevitz.
“A Zero-One Law for Boolean Privacy,”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 62–72.

[44]
B. Chor, M. Rabin.
“Achieving Independence in a Logarithmic Number of Rounds.”
Proceedings of the $6^{th}$ PODC, ACM, 1987.

[45]
R. Cleve.
“Limits on the Security of Coin Flips when Half the Processors are Faulty.”
Proceedings of the $18^{th}$ STOC, ACM, 1986, 364–370.

[46]
R. Cleve.
Personal communication, 1989.

[47]
J. Cohen, M. Fischer.
“A Robust and Verifiable Cryptographically Secure Election.”

[48]
A. Condon.
“Space Bounded Probabilistic Game Automata.”
Proceedings of the $3^{rd}$ Structure in Complexity Theory Conf.,
IEEE, 1988, 162–174.

[49]
A. Condon, R. J. Lipton.
“On the Complexity of Space-Bounded Interactive Proofs.”
Proceedings of the $30^{th}$ FOCS, IEEE, 1989, 462–467.

[50]
S. Cook.
“A Taxonomy of Problems with Fast Parallel Algorithms.”
Info. and Control 64 (1985), 2–22.

[51]
C. , J. Kilian.
“Achieving Oblivious Transfer Using Weakened Security Assumptions.”
Proceedings of the $29^{th}$ FOCS, IEEE, 1988, 42–52.

[52]
D. Denning,
Cryptography and Data Security.
Addison-Wesley, Reading, MA (1982).

[53]
Department of Defense Trusted Computer System Evaluation
US Department of Defense, Fort Meade, MD (August 15, 1983).

[54]
W. Diffie, M. Hellman.
“New Directions in Cryptography.”
IEEE Transactions of Information Theory IT-22 (November 1976),

[55] C. Dwork, L. Stockmeyer.
“Interactive Proof Systems with Finite State Verifiers.”
IBM Research Report RJ 6262 (61659), May 26, 1988.
Extended Abstract in
Proceedings of Crypto 1988, Springer–Verlag, 1990, 71–75.

[56]
T. Duff.
“Experience with Viruses on UNIX Systems.”
Computing Systems 2:2 (1989), 155–171.

[57]
S. Even,  O. Goldreich,  A. Lempel.
“A Randomized Protocol for Signing Contracts.”
Proceedings of Crypto 1982, Springer–Verlag, 1983, 205–210.

[58]
P. Feldman.
“A practical scheme for Noninteractive Verifiable Secret Sharing.”
Proceedings of the $28^{th}$ FOCS, IEEE, 1987, 427–437.

[59]
P. Feldman.
“One Can Always Assume Private Channels.”
Unpublished Manuscript, 1988.

[60]
P. Feldman, S. Micali.
“Optimal Algorithms for Byzantine Agreement.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 148–161.

[61]
J. Feigenbaum, S. Kannan, N. Nisan.
“Lower Bounds on Random-Self-Reducibility.”
AT&T Bell Laboratories Technical Memorandum, December 4, 1989.

[62]
L. Fortnow.
“The Complexity of Perfect Zero-Knowledge.”
Proceedings of the $19^{th}$ STOC, ACM, 1987, 204–209.

[63]
L. Fortnow, J. Rompel, M. Sipser.
“On the Power of Multi-Prover Interactive Protocols.”
Proceedings of the $3^{rd}$ Structure in Complexity Theory Conf.,
IEEE, 1988, 156–161.

[65]
Z. Galil, S. Haber, M. Yung.
“Cryptographic Computation: Secure Fault-Tolerant Protocols
and the Public-Key Model.”
Proceedings of Crypto 1987, Springer–Verlag, 1988, 135–155.

[66]
Z. Galil, S. Haber, and M. Yung.
“Minimum-Knowledge Interactive
Proofs for Decision Problems.”
SIAM J. Comput. 18 (1989), 711–739.

[67]
O. Goldreich, S. Goldwasser, S. Micali.
“How to Construct Random Functions.”
JACM 33:4 (1986), 792–807.

[68]
O. Goldreich and H. Krawczyk.
“On the Composition of Zero-Knowledge Proofs.”
Technical Report 570, Technion, Israel, June, 1989.

[69]
O. Goldreich, L. Levin.
“A Hard-Core Predicate for All One-Way Functions.”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 25–32.

[70] O. Goldreich, S. Micali, A. Wigderson.
“Proofs that Yield Nothing but Their Validity and a
Methodology of Cryptographic Protocol Design.”
Proceedings of the $27^{th}$ FOCS, IEEE, 1986, 174–187.

[71]
O. Goldreich, S. Micali, A. Wigderson.
“How to Play Any Mental Game, or
A Completeness Theorem for Protocols with Honest Majority.”
Proceedings of the $19^{th}$ STOC, ACM, 1987, 218–229.

[72]
O. Goldreich, R. Vainish.
“How to Solve any Protocol Problem – An Efficiency Improvement.”
Proceedings of Crypto 1987, Springer–Verlag, 1988, 73–86.

[73]
S. Goldwasser, S. Micali.
“Probabilistic Encryption.”
J. Comput. System Sci. 28 (1984), 270–299.

[74]
S. Goldwasser, S. Micali, C. Rackoff.
“The Knowledge Complexity of Interactive Proof Systems.”
SIAM J. Comput. 18:1 (1989), 186–208.

[75]
S. Goldwasser, M. Sipser.
“Private Coins vs. Public Coins in Interactive Proof Systems.”
Proceedings of the $18^{th}$ STOC, ACM, 1986, 59–68.

[76]
S. Haber.
Multi-Party Cryptographic Computation:
Techniques and Applications,
PhD Thesis, Columbia University, 1988.

[78]
S. Haber, S. Micali.
Personal communication, 1987.

[79]
J. Halpern, M. Rabin.
“A Logic to Reason about Likelihood.”
Proceedings of the $15^{th}$ STOC, ACM, 1983, 310–319.

[80]
N. Immerman, S. Landau.
“The Complexity of Iterated Multiplication.”
Proceedings of the $4^{th}$ Structure in Complexity Theory Conf.,
IEEE, 1989, 104–111.

[81]
R. Impagliazzo, L. Levin, M. Luby.
“Pseudo-Random Generation from One-Way Functions.”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 12–24.

[82]
R. Impagliazzo, S. Rudich.
“Limits on The Provable Consequences of One-Way Permutations.”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 44–62.

[83]
R. Impagliazzo, M. Yung.
“Direct Minimum-Knowledge Computation.”
Proceedings of Crypto 1987, Springer–Verlag, 1988, 40–51.

[84]
J. Kilian.
“Founding Cryptography on Oblivious Transfer.”
Proceedings of the $20^{th}$ STOC, ACM, 1988, 20–29.

[85]
J. Kilian. Personal communication, 1988.

[86]
J. Kilian.
“Zero-Knowledge with Log-Space Verifiers.”
Proceedings of the $29^{th}$ FOCS, IEEE, 1988, 25–35.

[87]
J. Kilian, S. Micali, P. Rogaway.
“The Notion of Secure Computation.”
Unpublished Manuscript, 1990.

[88]
E. Kushilevitz.
“Privacy and Communication Complexity.”
Proceedings of the $30^{th}$ FOCS, IEEE, 1989, 416–421.

[89]
R. Lipton.
“New Directions in Testing.”
Preprint, October, 1989.

[90]
M. Luby, S. Micali, C. Rackoff.
“How to Simultaneously Exchange a Secret Bit
by Flipping a Symmetrically Biased Coin.”
Proceedings of the $24^{th}$ FOCS, IEEE, 1983, 11–21.

[91]
K. Lund, L. Fortnow, H. Karloff, N. Nisan.
“The Polynomial Time Hierarchy has Interactive Proofs.”
Electronic mail announcement, December 13, 1989.

[93]
D. McIlroy, J. Reeds.
“A Security Model for Files and Processes in the UNIX System.”
AT&T Bell Laboratories Technical Report, April 14, 1987.

[94]
D. McIlroy, J. Reeds.
“Multilevel Security with Fewer Fetters.”
Proceedings of the the Spring 1988 EUUG Conference,
European UNIX Users' Group, London.

[95]
D. McIlroy, J. Reeds.
“Multilevel Windows on a Single-Level Terminal.”
Proceedings of the UNIX Security Workshop (1988),
USENIX, Portland, Oregon.

[96]
D. McIlroy.
“Virology 101.”
Computing Systems 2:2 (1989), 173–181.

[97]
N. Nisan.
Personal communication, 1988.

[98]
N. Nisan.
“Co-SAT has Multiprover Interactive Proofs.”
Preliminary draft, November, 1989.

[99]
I. Niven and H. Zuckerman.
An Introduction to the Theory of Numbers.
Wiley, New York, 1972.

[100]
Y. Oren.
“On the Cunning Power of Cheating Verifiers:
Some Observations about Zero  Knowledge Proofs.”
Proceedings of the $28^{th}$ FOCS, IEEE, 1987, 462–471.

[101]
W. Peterson and E. Weldon.
Error Correcting Codes.
Second Ed., MIT Press (1972).

[102]
M. Rabin.
“Digitalized Signatures.”
Foundations of Secure Computations, R. Demillo et al, Ed.
Academic Press (1978), 155–165.

[103]
M. Rabin.
“Digitalized Signatures and Public-Key Functions as Intractable as
Technical Report LCS/TR-212, MIT, January, 1979.

[104]
M. Rabin.
Personal communication, 1988.

[105]
M. Rabin.
Personal communication, 1989.

[106]
T. Rabin.
“Robust Sharing of Secrets When the Dealer is Honest or Cheating.”
Masters Thesis, Hebrew University, 1988.

[107]
T. Rabin, M. Ben-Or.
“Verifiable Secret Sharing and
Multiparty Protocols with Honest Majority.”
Proceedings of the $21^{st}$ STOC, ACM, 1989, 73–85.

[108]
J. Reeds.
“Secure IX Network.”
Proceedings of the DIMACS Workshop on
Distributed Computing and Cryptography, Princeton, NJ, October, 1989,
J. Feigenbaum, M. Merritt (eds.).

[109]
R. Rivest.
Workshop on Communication and Computing, MIT, October, 1986.

[110]
R. Rivest, A. Shamir, L. Adleman.
“A Method for Obtaining Digital Signatures and Public Key
Communications of the ACM 21:2 (1978), 120–126.

[111]
P. Rogaway, Personal Communication, 1989.

[112]
P. Rogaway.
“The Round Complexity of Secure Protocols.”
PhD Thesis, Massachusetts Institute of Technology, 1990.

[113] S. Rudich.
Personal communication, 1989.

[114]
A. Shamir.
“How to Share a Secret.”
Communications of the ACM, 22 (1979), 612–613.

[115]
A. Shamir.
“IP = PSPACE.”
Electronic mail announcement, December, 1989.

[116]
S. Toda.
“On the Computational Power of PP and $\oplus P$.”
Proceedings of the $30^{th}$ FOCS, IEEE, 1989, 514–519.

[117] M. Tompa and H. Woll.
“Random Self-Reducibility and Zero-Knowledge
Proofs of Possession of Information.”
Proceedings of the $28^{th}$ FOCS, IEEE, 1987, 472–482.

[118]
L. Valiant.
“The Complexity of Computing the Permanent.”
Theor. Comput. Sci. 8 (1979), 189–201.

[119] A. C. Yao.
“Protocols for Secure Computations.”
Proceedings of the $23^{rd}$ FOCS, IEEE, 1982, 160–164.

[120] A. Yao,
“Theory and Applications of Trapdoor Functions,”
Proceedings of the $23^{rd}$ FOCS, IEEE, 1982, 80–91.

[121]
A. Yao.
“How to Generate and Exchange Secrets.”
Proceedings of the $27^{th}$ FOCS, IEEE, 1986, 162–167.

[122] C. Yap.
“Some Consequences of Nonuniform Conditions on Uniform Classes.”
Theor. Comput. Sci. 26 (1983), 287–300.


# Who is Snoring? Snore based User Recognition

###### Abstract

Snoring is one of the most prominent symptoms of Obstructive Sleep Apnea-
Hypopnea Syndrome (OSAH), a highly prevalent disease that causes repetitive
collapse and cessation of the upper airway. Thus, accurate snore sound
monitoring and analysis is crucial. However, the traditional monitoring method
polysomnography (PSG) requires the patients to stay at a sleep clinic for the
whole night and be connected to many pieces of equipment. An alternative and
less invasive way is passive monitoring using a smartphone at home or in the
clinical settings. But, there is a challenge: the environment may be shared by
people such that the raw audio may contain the snore activities of the bed
partner or other person. False capturing of the snoring activity could lead to
critical false alarms and misdiagnosis of the patients. To address this
limitation, we propose a hypothesis that snore sound contains unique identity
information which can be used for user recognition. We analyzed various
machine learning models: Gaussian Mixture Model (GMM), GMM–UBM (Universal
Background Model), and a Deep Neural Network (DNN) on MPSSC - an open source
snoring dataset to evaluate the validity of our hypothesis. Our results are
promising as we achieved around or more than 90% accuracy in identification
and verification tasks. This work marks the first step towards understanding
the practicality of snore based user monitoring to enable multiple healthcare
applications.

Index Terms—  Snore, Identification, Verification

##  1 Introduction

Snoring is a common symptom of sleep disorder breathing (SDB). It is caused by
repeated bouts of decreased and stopped airflow during sleep. According to an
earlier investigation, about 50% of the adult population frequently snores
[1]. It has become a significant reason for poor sleep quality, degraded
memory, and diseases such as sleep disturbance and high blood pressure [2, 3].
Previous studies have revealed that analysis of snore sound is crucial for
respiratory and cardiopulmonary diseases at an early stage. Detected snores
can be further analyzed to extract more detailed attributes such as upper
airway condition. Thus, snore sound analysis is vital for passive health
monitoring systems.

The most prevalent and reliable technique for snoring sound monitoring and
diagnosis is polysomnography (PSG) [4]. Yet it is also confounded by problems
like long reservation lists, high nursing costs, and the ”first-night effect”
due to environmental changes [2]. Recently, acoustic monitoring using a
smartphone at home or ward has aroused considerable interest for its non-
invasiveness and cost-effectiveness. However, this raise an issue if the space
is shared by a bed partner or other patients since the raw audio may contain
interfering snore sounds which can cause false alarms and impact the
performance of the health monitors.

Previous studies have focused on snore sound classification of the four types
of snoring sounds (Velum, Oropharyngeal, Tongue, and Epiglottis) based on
their excitation source. For example, Wang et al. [5] proposed an architecture
based on Convolutional Neural Network combined with Gated Recurrent Unit (CNN-
GRU) to extract features solely from the training set in the corpus, and then
processed them through the Channel Slice Model to obtain an Unweighted Average
Recall (UAR) of 63.8%. Kun Qian et al. [6] carried out a multi-feature
analysis of the snore sounds. They applied those features to several
classifiers to rank the features based on their importance and achieved an UAR
of 78%.

In order to analyze the snoring sound in a shared environment, we must deal
with the snorer recognition problem in the first place. Inspired by the idea
that the feature of a subject’s cough is determined by the lung tissue and
vocal cord [7], we assume that the snoring sound may contain a unique
signature, which can be utilized to determine who actually snored. In this
paper, our main aim is to determine if users can be identified/verified on the
basis of their snore sounds. To this end, we created machine learning models
based on GMM, GMM-UBM, and Deep Neural Network (DNN) to extract snore patterns
and evaluated them on MPSCC data corpus. Our results are promising as all
three classifiers achieved an identification rate of more than 90% and less
than 15% equal error rate (EER) with just four snoring during the enrollment
per user. As for verification performance, snore embeddings derived from DNN
produce the best results by achieving over 95% specificity and sensitivity.
Our work is the first to show that snoring sounds have unique signatures and
can potentially be used for user monitoring in shared environments.

##  2 Related Work

Existing studies have focused on using audio such as speech and cough for user
authentication. However, no previous study has investigated if snore has
unique signature which can determine who produced it. As for speaker
recognition, Automatic Speaker Recognition (ASR) system aims at eliciting,
classifying, and recognizing the voice signal that conveys speaker identity
[8]. Modern approaches are mainly based on the statistical models of speech
signal. Reynolds et al. [9] proposed an individual speaker identification
method based on GMM. Later in 2000, Reynolds [10] proposed a modified GMM with
a Universal Background Model (UBM) for the adaption of each enrolled subject .
To decrease the complexity of the GMM supervector, Dehak et al. [11] exploited
i-vectors to train the classifiers and identify unknown speakers. Deep
Learning methods such as x-vectors have also been proposed for voice print
recognition [12]. The embeddings derived from x-vectors outperformed the
i-vectors.

For cough recognition, Whitehill et al. [13] implemented a multitask learning
system and achieved an identification accuracy of 82.15% . The model was
trained on both speech and cough to address the lack of sufficient training
data. Vatanparvar et al. [14] proposed a novel cough embedding model to do
cough-based user verification. A four-layer dense Neural Network is applied to
the training set of cough signals. The model achieved an average error rate of
below 10% with only five utterances per subject in the enrollment phase.
Recently, Cleres et al. [15] applied a triplet network architecture based on
CNN and proposed a metric learning algorithm for cough recognition. With the
audio recordings of asthmatic patients’ coughs, their method produced an
accuracy of 80% and an EER of 20% using 12 utterances in the enrollment phase.

##  3 Methodology

###  3.1 Data Set, PreProcessing and Feature Extraction

We used MPSSC (Munich-Passau Snore Sound Corpus) dataset [16] for our work.
This corpus obtained primary material from Drug-Induced Sleep Endoscopy (DISE)
examinations. After manual selection, the dataset only contains events without
interference and with a discernible, single point of vibration. Snore sounds
are divided into four categories based on their excitation location in the
upper airways. 828 utterances were collected from 219 subjects. The audio was
recorded with a sampling rate of 16KHz with 16-bit linear PCM mono channel.

We applied Short-time Fourier transform (STFT) on the audio signals to
represent the signal in the time-frequency domain by computing discrete
Fourier transform (DFT) over short overlapping windows. The audio was divided
into 25-ms frames by a Hanning window, with 15 ms of overlap. 25 MFCC
coefficients were extracted as feature inputs for all the three models. Figure
1 shows the spectrogram of two snorers.

(a) Subject 1

(b) Subject 2

Fig. 1: Spectrogram of two snorers

###  3.2 Model Design

Here we explain three models (GMM, GMM-UBM, DNN) for snore recognition along
with their training and evaluation.
GMM: Gaussian Mixture Model (GMM) is efficient in signal approximation because
it can fit complex probability distribution of time series by a small number
of parameters performing a weighted average of multiple simple normal
distributions. According to Reynold et al.[9], GMM offers a reliable speaker
representation for the challenging task of speaker recognition using
distorted, unrestricted speech and enables high recognition accuracy for short
utterances. So, we tried GMM with different components in our work.

Since the MPSSC corpus has limited utterances (snoring samples) for each
person, we select the subjects with at least five utterances/samples. 72
subjects meet our requirements. The first four samples are used for training
and the other one for testing. In the training phase, we first extract the
frame-level feature vectors and stack the ones of the same subject together to
form an aggregated feature matrix. We model all the snorers independently from
the extracted features. The model for each subject is constructed by fitting
the distribution with the feature matrix. For the evaluation phase, for each
sample, the model with the highest likelihood score is considered as the
identified snorer (identification) or the likelihoods are compared to a
threshold to determine if the sample matches the model for verification.
GMM-UBM: It is an extension of the Gaussian Mixture model. It is particularly
effective for users with limited enrollment speech samples. The core is to
employ other users’ data for pre-training and reduce the dependence on the
subject data. We first need to train a background Gaussian Mixture Model based
on all the user’s data, then fit each Gaussian distribution to the target
user’s data. This procedure is called adaptation using Maximum a posterior
(MAP) algorithm [10]. We can fuse the obtained new parameters with the
original parameters of the UBM model to get the target speaker’s model. We use
the same concepts in our work for the snore sounds. Similar to the evaluation
phase for the GMM model, we also calculated the log-likelihood of a given
utterance from each model and choose the one with the highest score as the
predicted subject. For the verification, the decision is made through a preset
threshold.

DNN: Inspired by the success of Deep Neural Network (DNN) on speaker
verification and cough recognition [17, 14], we used DNN as a snore embedding
extractor. We used the same methodlogy as proposed in CoughMatch [17] by
dividing the task into three parts. In the development phase, we train a
supervised DNN, based on the frame level, with all the subjects in the
dataset. For the subject that has more than four utterances, we use the first
four. Otherwise, we use all its audio. we assume the training utterance from
the snorer s as:

$X_{s}=\left\\{O_{s1},O_{s2},\dots,O_{sn}\right\\}$ (1)

Each utterance is represented by several selected observations (frames):

$O_{si}=\left\\{o_{1},o_{2},\cdots,o_{m}\right\\}$ (2)

The network’s input is formed by stacking each observation’s 25-dimensional
MFCC features vector with the ones of its 49 adjacent frames. Thus, the
dimension of the input vector is 1250. The output is a 1-hot N-dimensional
identity vector, where the only non-zero item is the one corresponding to the
subject identity. N is the number of the subject.

In the enrollment phase, 72 subjects with 5 utterances are used for the
embedding extraction. We freeze all the dense layers and remove the output
layer. The input feature is generated in the same approach as described above.
For each subject, an independent snore embedding is constructed with four
training utterances. Here, each utterance contains 15 selected observations
(frames), the distance between adjacent observations is five frames:

$O_{ei}=\left\\{o_{1},o_{2},\cdots,o_{15}\right\\}$ (3)

We feed every observation with its 50 neighboring frames to the supervised
trained DNN; L2-normalize the output obtained from the last hidden layer, and
accumulate for all the observations from utterance $O_{si}$. The outcome
vector is referred to as the utterance-level snore embedding. Finally, the
subject’s snore embedding is acquired by averaging the embeddings of the four
utterances in $X_{s}$.

In the evaluation phase, another utterance from each of the 72 subjects is
used for testing. The testing sample is strictly excluded from either the
development set or the enrollment set. We implement the same feature
extraction (feeding it to the DNN) for the testing utterance and compare the
cosine similarity between the test embedding and the claimed subject’s
embedding. The decision is made on the subject that has the highest similarity
(identification) or comparing the similarity to a threshold (verification). We
created a 4-layer network with 128 nodes per layer and adopt rectified linear
units (Relu) as the activation function for hidden layers. We adopt ’Softmax’
as the activation function for the output layer and insert a 15% Dropout
before the output layer to mitigate the overfitting problem. The network is
trained for 80 epochs with Adam optimizer.

##  4 Results

###  4.1 Snore Signature

We firstly show the visual patterns of snores obtained from different users.
Fig. 2 shows the t-sne plots [18]. The left hand side shows the distribution
of MFCC features of the first eight subjects. Each point represents an
utterance from the training set, and the point’s color represents a certain
subject. The distribution of the same eight subjects’ snore embeddings
obtained from DNN is shown on the right side. We only show eight to ensure the
readability of the plot. It can be seen that the snore embeddings have better
clustering performance over the MFCC features. This also shows that snore have
unique signature which varies between users and can be useful for snore
tracking and user recognition.

(a) MFCC features

(b) Snore embeddings from DNN

Fig. 2: T-SNE Plots Table 1: GMM and GMM-UBM identification accuracy Number of Components | GMM | GMM-UBM
---|---|---
5 | 0.9722 | 1.0000
10 | 0.9722 | 0.9861
15 | 0.9583 | 0.9722
20 | 0.9583 | 0.9722
25 | 0.9444 | 0.9583

(a) GMM

(b) GMM-UBM

(c) DNN embeddings

Fig. 3:  Heatmap of the three models - Verification

###  4.2 Results for Identification

We obtain more than 90% accuracy with the GMM based models as shown in Table
1. Theoretically, the fitting effect should be promoted with the increment of
Gaussian components. However as the number of training samples were few, the
accuracy decreases with the number of components.

(a) GMM

(b) GMM-UBM

(c) DNN embeddings

Fig. 4: ROC of the three models - Verification

GMM-UBM model improves the system performance by pre-training a universal
background model. The identification accuracy over the number of components is
shown in Table 1. The accuracy of GMMM-UBM at each component gets slightly
better than a GMM model which verifies the superiority of GMM-UBM over GMM. In
fact, the accuracy ranges from 95% to 100% for GMM-UBM. For the DNN, we
obtained an accuracy of 0.9306 with snore embeddings.

###  4.3 Results for Verification

For user verification, we set the number of the Gaussian components at 10 as
that obtained the best performance in our analysis. We initially visualize the
verification performance intuitively, using the heatmap, for the three models
successively (see Figure. 3). The row index denotes the test number, while the
column index denotes the embedding number. Item color varies with the
evaluation value. Thus the ideal case is that the item on the diagonal line
has the deepest shade if all the test audios are correctly verified. It can be
seen visually that the snore embedding extracted from the DNN has the best
verification performance.

We analyzed the verification performance using different metrics. Firstly, we
compare the specificity (True Negative Rate) and sensitivity (True Positive
Rate) values satisfying an equal error rate (EER). We adjust the threshold for
each model to get the best performance (see Table 2). As shown, the snore
embeddings from the DNN model achieve the best results over the other two
models based on GMM. Next, we calculated the receiver operating characteristic
curve (ROC) to evaluate the verification performance. The bigger the area
under the curve, the better the result is. ROC curves of the three models is
illustrated in Figure 4. Similar to our previous result, the DNN based model
has the highest TPR rate (sensitivity) and the smallest TPR-TNR distance.
Thus, it achieves the best verification result among all the three models.

Table 2: Verification performance for the three models  Model | Threshold | TPR | TNR
---|---|---|---
GMM | -33.2 | 0.9028 | 0.8940
GMM-UBM | -71.1 | 0.9444 | 0.9701
DNN | 0.45 | 0.9583 | 0.9523

##  5 Discussion and Conclusions

Passive health monitoring of snore sounds using ubiquitous devices is becoming
prevalent due to its non-invasiveness and low cost. However, such monitoring
will fail in scenarios where many people share the same environment such as in
a house. Thus, snorer recognition is a subject worthy of study. This paper
evaluated three models for snorer identification and verification based on the
MPSSC corpus. MFCC features are extracted to create each subject’s snore
model, which is later used to check if the testing utterance can match the
individual snore pattern. We mitigated the overfitting problem due to limited
training data by introducing a Universal Background Model. A Deep Neural
Network is also applied to train the snore embeddings to improve the system’s
performance. Our results are encouraging and show that the models can achieve
over 90% identification accuracy. As for verification results, the snore
embedding model based on DNN obtains over 95% for sensitivity and specificity.
To conclude, our work takes the first ever step towards understanding the
practicality and proving the feasibility of user recognition through snores
that can lead to creation of accurate and ubiquitous snore monitoring systems
in the future.

## References

  * [1] E. Lugaresi, F. Cirignotta, G. Coccagna, and C. Piana, “Some Epidemiological Data on Snoring and Cardiocirculatory Disturbances,” _Sleep_ , vol. 3, no. 3-4, pp. 221–224, 09 1980. [Online]. Available: https://doi.org/10.1093/sleep/3.3-4.221
  * [2] J. Sun, X. Hu, Y. Zhao, S. Sun, C. Chen, and S. Peng, “Snorenet: Detecting snore events from raw sound recordings,” in _2019 41st Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC)_ , 2019, pp. 4977–4981.
  * [3] Z. Zhang, J. Han, K. Qian, C. Janott, Y. Guo, and B. Schuller, “Snore-gans: Improving automatic snore sound classification with synthesized data,” 2019.
  * [4] H. E. Romero, N. Ma, and G. J. Brown, “Snorer diarisation based on deep neural network embeddings,” in _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 876–880.
  * [5] J. Wang, H. Strömfeli, and B. W. Schuller, “A cnn-gru approach to capture time-frequency pattern interdependence for snore sound classification,” in _2018 26th European Signal Processing Conference (EUSIPCO)_ , 2018, pp. 997–1001.
  * [6] K. Qian, C. Janott, V. Pandit, Z. Zhang, C. Heiser, W. Hohenhorst, M. Herzog, W. Hemmert, and B. Schuller, “Classification of the excitation location of snore sounds in the upper airway by acoustic multi-feature analysis.” _IEEE transactions on bio-medical engineering_ , 2016.
  * [7] E. C. Larson, T. Lee, S. Liu, M. Rosenfeld, and S. N. Patel, “Accurate and privacy preserving cough sensing using a low-cost microphone,” in _Proceedings of the 13th International Conference on Ubiquitous Computing_ , ser. UbiComp ’11. New York, NY, USA: ACM, 2011, pp. 375–384. [Online]. Available: http://doi.acm.org/10.1145/2030112.2030163
  * [8] D. A. Reynolds, “An overview of automatic speaker recognition technology,” in _2002 IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 4, 2002, pp. IV–4072–IV–4075.
  * [9] D. Reynolds and R. Rose, “Robust text-independent speaker identification using gaussian mixture speaker models,” _IEEE Transactions on Speech and Audio Processing_ , vol. 3, no. 1, pp. 72–83, 1995.
  * [10] D. A. Reynolds, T. F. Quatieri, and R. B. Dunn, “Speaker verification using adapted gaussian mixture models,” _Digit. Signal Process._ , vol. 10, pp. 19–41, 2000.
  * [11] N. Dehak, P. J. Kenny, R. Dehak, P. Dumouchel, and P. Ouellet, “Front-end factor analysis for speaker verification,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 19, no. 4, pp. 788–798, 2011.
  * [12] D. Snyder, D. Garcia-Romero, G. Sell, D. Povey, and S. Khudanpur, “X-vectors: Robust dnn embeddings for speaker recognition,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2018, pp. 5329–5333.
  * [13] M. Whitehill, J. Garrison, and S. Patel, “Whosecough: In-the-wild cougher verification using multitask learning,” in _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 896–900.
  * [14] K. Vatanparvar, E. Nemati, V. Nathan, M. M. Rahman, and J. Kuang, “Coughmatch – subject verification using cough for personal passive health monitoring,” in _2020 42nd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC)_, 2020, pp. 5689–5695.
  * [15] S. Jokić, D. Cleres, F. Rassouli, C. Steurer-Stey, M. A. Puhan, M. Brutsche, E. Fleisch, and F. Barata, “Tripletcough: Cougher identification and verification from contact-free smartphone-based audio recordings using metric learning,” _IEEE Journal of Biomedical and Health Informatics_ , vol. 26, no. 6, pp. 2746–2757, 2022.
  * [16] B. Schuller, S. Steidl, A. Batliner, E. Bergelson, J. Krajewski, C. Janott, A. Amatuni, M. Casillas, A. Seidl, M. Soderstrom _et al._ , “The interspeech 2017 computational paralinguistics challenge: Addressee, cold & snoring,” in _Computational Paralinguistics Challenge (ComParE), Interspeech 2017_ , 2017, pp. 3442–3446.
  * [17] E. Variani, X. Lei, E. McDermott, I. L. Moreno, and J. Gonzalez-Dominguez, “Deep neural networks for small footprint text-dependent speaker verification,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014, pp. 4052–4056.
  * [18] L. van der Maaten and G. Hinton, “Visualizing data using t-sne,” _Journal of Machine Learning Research_ , vol. 9, no. 86, pp. 2579–2605, 2008\. [Online]. Available: http://jmlr.org/papers/v9/vandermaaten08a.html