From: Kay Ping <kping@nym.alias.net>
Date: Mon, 12 Jan 1998 16:49:45 +0800
To: cypherpunks@toad.com
Subject: Trust through anonymity; time vaults
Message-ID: <19980112083354.29846.qmail@nym.alias.net>
MIME-Version: 1.0
Content-Type: text/plain



-----BEGIN PGP SIGNED MESSAGE-----

Trust and anonymity may seem to be in contradiction but I intend to show
how anonymity can be used to achieve trust.

At the base of any cryptographic system is a trust model and it can only
be as strong as the assumptions made by the trust model. Of special
interest to us are distributed trust models. This posting was sent through
a chain of remailers. I do not need to trust any of them completely, just
assume that the chances that all of them are colluding or have been
compromised by an attacker are low.

Other types of services requiring a server infrastructure can be
implemented using distributed trust models. For example, I can submit a
document to be timestamped by several servers. Someone checking the
validity of the combined timestamps can have higher assurance that the
timestamp has not been generated by collusion between the document owner
and the timestamping service or by a compromised timestamper key.
Another type of service which can use a distributed trust model is a
digital time vault which will be described later.

One of the problems with distributed trust is reliability. A service can
be interrupted by any of the servers going down. The overall reliability
goes down exponentially with the number of servers. This can be solved
for some types of services by using a secret-splitting algorithm
requiring a minimum of N out of M parts. A user can select values of N
and M that satisfy both his reliability requirements and his paranoia.

But some are more paranoid than that. It may take a very large number of
unrelated servers around the world to earn their trust and an even larger
number to get acceptable reliability.

To those I propose the following idea:

Some of the servers will be anonymous. If they don't know each other, they
can't collude. If they are anonymous it will be hard for an attacker to
know which machine to break into.

One of the problem with this approach is that an opponent with sufficient
resources can set up a large number of anonymous servers and hope that a
user chooses a set of servers of which at least N are under his control.

If the user chooses a combination of anonymous and well-known servers he
gets good protection against this scenario. Even if all the anonymous
servers are run by <pick your favorite three letter acronym agency> it is
unlikely that they will collude with servers run by, let's say,
well-known remailer operators in other countries.

Anonymous server operators may try to collude but selfishness will stand
in their way: even if N-1 servers revealed their parts of the secret, the
last one can always refuse to cooperate and use the information, so none
of them has an incentive to reveal his part in the first place.
Simultaneous secret trading protocols will not help- they cannot
guarantee that a valid secret is contained in the message. The only way
to get selfish operators to cooperate is using zero-knowledge proofs of
their secrets. Zero-knowledge proofs work only for specific types of
secrets. It may be possible to use secrets for which zero-knowledge
proofs do not work.

The specific service I had in mind for this distributed trust model is a
digital time vault. It allows a sender to encrypt a message which can
only be decrypted after a certain date.

This is done by having a server generate secret/public key pairs for
future dates, publish all public keys at once and publish the private key
for each date at that date. Only after that date the message can be
decrypted. For reliability and security the message (or the session key)
can be split and encrypted it to the public keys of "next Friday"
published by several different servers.

This service can be used to send a public message that can only be read
after a certain date, without any action required by the sender at that
date. This may be useful if the sender suspects that he may be under
arrest, dead or otherwise uncapable of getting online at the target date.

Another possible use for this service is to destroy information to
protect yourself against threats or court orders and still be able to
recover it at a later date. Even if you don't actually do it, the
existence of the service gives you plausible deniability.

Many types of secret information are only secret for a limited time -
until an announcement is made or a deal is signed. Encrypting a message
to a future date as well as the intended recipient allows storing the
message in an unsecured archive for later reference.

This service can be implemented using existing software like PGP without
secret splitting algorithms: a conventional encryption passphrase is
encrypted to several different chains of public keys of the same date on
different servers, using combinations that create the same N out of M
result.

Since the time servers do not receive any information or participate in
the process in any way they will not generate any significant load except
during initial key generation. They can also be kept anonymous very
easily and cannot be held accountable for anyone's use of the service.
The servers will still attract attacks. Anonymous servers will get some
protection against this since their location is not known. Public servers
can protect themselves by encrypting future private keys to future date
keys on other servers and keep encrypted backups off-site. This should be
done carefully to ensure that future keys will not be lost because of
loops or servers going down.

Anyone wants to run such a service? You can run either an anonymous or
public server. You should run a public server only if you think your
reputation is good and you public key is trusted by many people. If you
want to run an anonymous server generate a new key without email or any
other identification except a pseudonym for the server.

You must commit to maintaining the service for a minimum period and
publish all the private keys for which you published the initial public
keys, but never before their time. The trial period for this service will
be three months and the interval will be one week, posted at midnight on
the beginning of the week, GMT. Date keys must be signed by the server
key.

Date private keys must have an empty passphrase so they can be used by
anyone after they are published. Until then they should be secured for
storage. Date Key IDs consists of a date in YYYYMMDD format followed by
the server name. The name may be followed by an optional email address of
the maintainer.

For the trial period keys should be published to alt.privacy.anon-server
and the list. Lists of public keys and past private keys should be
available through http, ftp or finger. If you run an anonymous server you
may ask someone, preferably a maintainer of a public server, to get your
lists and make them available.

The trial will let us experiment with this trust model and see if anyone
thinks of interesting ways to use the service.




- -----------------
Kay Ping 
nop 'til you drop

finger kping@nym.alias.net for key
DF 6D 91 18 A6 59 41 96 - 89 01 69 B7 9D0 4 AE 53

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: cp850

iQEPAwUBNLnGZRHPAso8Qp7tAQHnkwfQ9BpL82R1Mw1WY9EnOaFuXme+2y+OZZ60
Cb41fVtlSDC9EmAjAuV9K1dDP7FVGwFzGQ5j04IjgLocMbUgEyZDkKoFhe2Hgasw
XU2ick5adCsvA8I0USfMVeQj2L6tkzc+hr4l9NXH7AGEQQGZu2iZTlDNn72FNBeo
7gPjxj8/a/T2+zKMyJbS2ujYa4ZBuypXpQg2UaQ42m1uKUz/ymJFXcm51X1Do3hJ
TC2tvIST+v/cfYesblhAR1kRVAiKL+YUagLeWMU1I5X64E2MKVctOiPWBSHCLgQ0
LKtrwIHIvrIP2z0FMquR5GricvrLdFid89vtZFb1n8quQg==
=uVxx
-----END PGP SIGNATURE-----