Timed-Release Crypto

Cypherpunks,

I want to share with you folks some preliminary ideas on "timed-release
cryptographic protocols," that is, methods for sending encrypted messages
into the future.

These ideas need more work, but since I have recently mentioned them to Hal
Finney, Max More, Mark Miller, and perhaps others, I guess it's time to say
something here.

Why would anyone want to send encrypted (sealed) messages into the future?

1. Foremost, to send money into the future, while protecting it in the
meantime from seizure, taxation, etc. This might be of interest to cryonics
folks who want to arrange for their own revival/reanimation at some time in
the future. (Existing systems have relied on creating endowments, insurance
contracts, trust funds, and the like. The trust of the agent is the means
for sending funds into the future--clearly this agent could be compromised,
raided, taxed, put out of business, etc. Though I am personally not a
cryonics client, I began thinking about this problem in 1989 and talked it
over with Phil Salin, who, ironically, is now himself in cryonic
suspension.)

2. To fulfill contracts with long payoff dates. One might wish to deliver
money at some future date, or to supply information at some future date.

3. "In the event of my death"-type messages, with guaranteed delivery of
some message or text in the event that something happens (or, of course,
that the message is not "countermanded" by the sender).

4. A software publisher might place source code in a timed-release escrow,
agreeing to release the code in 10 years, for whatever reason. (Of course,
he may lie, but that's another issue. Possibly the digital time-stamping
work of Haber and Stornetta can be used.)

I'm sure you can think of other uses. I argue that this timed-release
message is a kind of cryptographic primitive...though it may be argued that
it's just a variant of an ordinary message transmission, albeit one through
time instead of through space.

Diving right in, some approaches:

A message is encrypted (standard public key means, though private key
methods work the same way) and "sent out." Perhaps into a network of
remailers or a Cuperman-style "pool" (BTW, my compliments to Miron C. for
deploying such a thing..the first of many, I suspect). The encrypted
message is just a "passive" item in this scheme...it stays encrypted, is
available to all, etc. (in other words, the security of the message being
time-released does not in any way depend on hiding the existence or
location of the encrypted message, though of course it is important that
the encrypted message be widely distributed and not explicitly advertised
or tagged as being a timed-release message. 

(Detail note: Why not? Because some governments may see timed-release
messages as automatically being tax-avoiding, cryonics-supporting,
seditious, etc., messages and may attempt to hunt down and erase any such
messages...perhaps via "hunter-killer crypto viruses" or somesuch.)

Let us suppose the encrypted message is to be unlocked in 30 years. (It
could also be when some recognized event occurs, such as a Mars landing or
the death of the sender, or whatever...you'll see how this works). How can
the decryption key be prevented from being used in the meantime?

(To make this clear: both the encryted message _and_ the decryption key are
"in circulation" during all of those 30 years. Any scheme that relies on
the sender himself keeping the decryption key "secret" for those 30 years
is of course no fun at all...it's just what we have today and involved no
new cryptographic primitives, just ordinary human-mediated secrecy.) 

But if the encrypted message and the decryption key are both in circulation
for all of those 30 years, what's to keep someone from decrypting the
message in _one_ year, for example?

The answer: independent escrow agents who handle large volumes of messages
and agree to hold them for various amounts of time. Because they have no
idea of what's insided the encrypted messages they hold--and some may be
"test" messages deposited deliberately by reputation-rating or
credentialling agencies, such as "Consumers Crypto Guide"--and because
their business is holding things in escrow, they will not generally open
messages before the time specified.

"Aha!," I hear you exclaim, "Tim's scheme depends solely on the trust of
these escrow agents, and that's no different from depositing a sealed
envelope with your friendly lawyer and asking him to promise not to peek."

Here's how crypto and reputation-based sytems make my scenario different
(and stronger, I am arguing):

- an ecology of many escrow services, many pools, many encrypted-message
senders makes for a more robust system against subversion of any single
agent.

- no escrow agent knows what is contained in a sealed message, hence the
tempation to peek is reduced. (A wrinkle: escrow agents, like remailers,
will probably go to automatic hardware that is tamper-resistant (cf.
discussion of tamper-resistant or tamper-responding, modules in the Crypto
Glossary distributed at the first physical Cypherpunks meeting and
available in the archives). Thus, the hardware will automatically execute
certain protocols and make peeking a pain.)

- the best escrow agents (someday) may in turn increase security and their
own reputations by in turn using secondary contracts, i.e., by contracting
with _other_ escrow agents to seal parts or all of their messages.

- what results is that the original message is scattered around in various
publicly available locations (perhaps paid-for by dribbles of cryto-money
from crypto escrow agents, but this is a detail easily worked out in
various ways). The decryption key to the original message is itself broken
up into several or many pieces and scattered to a network of
"remailer"-like agents (they are essentially "remailers into the future,"
by agreeing as part of their protocol to hold messages for some amount of
time). As time passes, these various messages (pieces, remember) are
retrieved, forwarded, and generally bounced around the network.

- some escrow agents may be just "fixed delay" nodes. For example, "Alice's
Rest Stop" remailer node widely advertises that it will take in messages
and simply delay them for some fixed time, e.g., for a year. For some fee
based on message size. (Clearly the fixed time delay is a crufty approach,
much less flexible than variable delays negotiated by the messages
themselves, but it makes the idea clearer in some ways: a network of many
such one-year delays could thus "send" a message into the future in
one-year jumps.)

(It is important to remember that these messages are "first-class objects,"
to borrow a phrase, and that all messages essentially look the same and
have the same "rights" (Dean Tribble is probably barfing at my
appropriation of object-oriented lingo, but it seems appropriate). That is,
inspection of the bytes will not reveal to someone whether the message is a
$2 message, a simple love letter, a business contract, a remailed item, a
$100K cryonics payment, etc. Thus, the "authorities" cannot simply target
some class of messages and ban them or launch "hunter-killer crypto
viruses" against them, at least not without shutting down the whole
system!)

- the individual pieces may have instructions attached, such as "You will
be paid 10 crypto credits if you hold me for one year and then decrypt me."
(Not to belabor the point, but the means by which this "contract" can be
enforced are that the escrow agents never know when they're being tested,
when they're being monitored by rating services. This kind of "trust" is
what allows ordinary deposit banks to work...their business is talking
deposits and lending money, not repudiating the honest claims of
customers.)

- thus, I envision a swarm of messages being stored-and-forwarded in space
and time, with an observor seeing only  bits flowing around. Nobody except
the original "launcher" (who needs to be fairly careful about the path he
selects, about robustness against some fraction of the escrow/remailer
agents going out of business, etc.) knows what's going on.

- and as the end of the 30 years period approaches, to continue with the
example I started with, the decryption key gets "reconstituted" in various
ways (depends on what is desired, and how protocols evolve...I don't claim
to have the details already worked out). For example, after 30 years the
various messages stored in escrow accounts are forwarded separately to "The
Immortalist Foundation," which may in fact be a digital pseudonym (as we
have discussed so many times here). This entity puts the pieces together,
sort of like combining the missing pieces of a text and reconstituting a
genie or demon, and finds it can now unlock the original encrypted message.
It finds, say, a million crypto credits, or the location of some physical
treasure, or whatever. 

(Needless to say, there are some obvious questions about what long-term
money will be stable, what banks will still exist after 30 years, and so
on. I expect new forms of time deposits to evolve. Can the original sender
be expected to know what will evolve before he seals his original message?
Some obvious issues to work on--I never claimed it would be trivial, or
static. One approach is to allow some human intervention, where an
"investment agent" opens a digital money message, redeems it, and reinvests
it in some new instrument. As usual, he would not know who the original
investor was and would be "tested" by reputation-rating agencies. It _does_
get complicated, I know.)

The Key Point: Messages sent into this network of remailers, escrow
accounts, pools, and investment agents are untraceable to the sender and
are generally unidentifiable. To break a single message involves breaking
the entire system (or colluding with enough remailer nodes, as in any
DC-Net sort of system). As with remailer networks, the expectation is that
they will become sufficiently pervasive and trans-nationalized that
breaking the entire system is just too painful and difficult (much the way
the Net is already too pervasive to easily shut down, even if some uses of
it are undesirable to various national authorities).

Timed-release messages are objects that can be transmitted, encrypted, and
can carry further instructions on where to mail them next, on how much
digital money to pay to this next link, and various other instructions or
protocols.

(In other words, they are "agents" that can negotiate various contracts,
for remailing , for storage, etc. Since they are "powerless" in a human
sense, their security is provided by double-checks--perhaps by other agents
who are watching and waiting--and by the general "shell-game" system of
reputations, credentialling, and so on.)

To make this scheme clearer in a simple way, I could publicly post an
encrypted message to this list, or in one of the "pools," and then scatter
the decryption key in several pieces with several members of this list,
paying them $1 each to "hold" their piece for, say, a month. At the end of
the month, they would fulfill their end of the bargain by forwarding the
piece they hold to some public place or pool and the decryption key would
be reconstituted (don't press me for exact details....PGP doesn't support
this directly, but could). For robustness against loss of some of the
messages, an n-out-of-m voting scheme could be used (e.g., any 5 of 8
pieces are sufficient to reconstruct the decryption key).

The result is a message from the past, a timed-release message.

I'm anxious to hear your comments. I think such a cryptographic primitive
could be useful for a lot of purposes.

-Tim May

--

Timothy C. May               | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com        | anonymous networks, digital pseudonyms, zero
408-688-5409               | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA       | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: waiting for the dust to settle.

By coincidence, I was thinking about time-release protocols the other
day.  I've got most of a system worked out, but I need to write it up
and look at it for a while to make sure it works.  what I think I have
is a system in which the sender is given a key by a beacon which he
can verify, at issuance time, will be revealed by the beacon at some
future time.  The implementation (but not the basic idea) relies on
using multiple public RSA keys with the same modulus.  I know there
are some attacks against this, but I don't know their nature.  If
someone who knows about this (or knows where to find out) could
contact me I would be most appreciative.

As far as sending money into the future goes, there are some tradeoffs
between anonymity of payment, length of time in the future, and
message size.  Anonymity of payment is difficult, since digital cash
has to expire in order for the bank not have to keep ever huger lists
of deposited numbers.  Large payments are less frequent anyway, and
provide less covering traffic.  If you continuously rotate your money
into the future, therefore, all the steps must be encapsulated, making
the size of the message grow linearly with the number of hops.  One
might be able to use a financial intermediary for anonymity, though.
It's not obvious to me that this will work.

Eric

This is neat idea, T.C. May. Here are some things that popped into my
head thinking of it.

I think the idea of multiple encryption of the time-delay message would
be extremely useful here. Imagine this. You encrypt a message with as
many layers as there are intermediate escrows.  In other words, a
message is encrypted with layer1 pw, then reencrypted with layer2 pw,
then layer3, etc.  In the decryption message (separate) there is a long
sequence of keys.  The lower-level keys closer to the actual message
are also encrypted by the higher-level keys.  Now, suppose that the way
the message is held is this: after 1 level of protection has elapsed,
the password message and the encryption message are recombined to a
single escrow agent. That agent uses the top-level information (one key
is plaintext (maybe not), or encrypted with that agent's public key, or
whatever) to decode the top-level of encryption.  Then, he again
redistributes the next-lower-level of encryption password message and
actual message to unique escrow agents.

The beauty of this is that a given escrow agent, even once he gets a
password, can only strip off "his" topmost level of encryption (at
least, that's the intent). He is powerless to decrypt all the lower
levels and hence the message itself. Therefore to actually decrypt a
message ahead of time would require the collusion of many operators. 
The message should have some kind of indications at each level when it
is to be "reconstituted" (just add water), and escrow agents of course
should hold or reject messages that are sent to them for premature
decryption.  There is also the distinction of "joiners" and "storers"
although the two could be combined in some way (both are "forwarders").

The final destination should be the destination the original owner
intended, so that there is no final escrow agent that can decrypt the
message.  He only has an encoded message he can pass along, and another
agent only has a meaningless key and the final address as well.  When
the final destination is reached, the last layer of decryption can be
removed by the intended recipient (the money is in -X- account,
password -Y- or whatever).  I.e., the recipient is the final "joiner".

The idea of separating keys and the encoded messages is really
ingenious, and I'd guess this "disassociation" has other uses as well. 
An encrypted message with a password *existing* but *inaccessable* is
just as secure as a message using conventional encryption. In fact,
there is probably an added dimension of security---in most systems
*somebody* knows the key, but here, if it is generated automatically,
even the *key* is unknown for awhile!

Another possibility is to have some kind of standard protocol for time
encrypted messages (this is interesting and seems feasible). Let's say
I want a message [x] to be unencrypted on date [y].  I call a "time
encryption server" and ask for the secret key associated with my
message and date [y].  I encrypt the message and publicize that
version.  The time server is constantly spewing out the daily code for
messages that expire on that date. Anybody just listens to the
broadcast and decrypts the messages in their possession using the key. 
Note however that it is crucial that somehow the key depend on the
message itself (via the hashing approaches), otherwise everybody knows
everybody else's keys ahead of time just by submitting messages to the
server for the particular date.  I suppose public-key encryption could
be used here but I'm hazy on the details.

P.S. this is a really tricky situation compared to above, but it might
be possible to make messages with "insecure" passwords that can be
broken in a few lifetimes from searches. Of course, this depends very
crucially on the pace of technology and the resources devoted to the
cracking, two highly variable factors.

Also, keep in mind that every message in existence relying on
complexity of algorithms is encrypted based on the time-delayed release
of revolutionary and unforeseen computer techniques in cracking... or,
more specifically, the gamble that they will not occur...

[This is a first post by a crypto-naive person - be kind.]

>Another possibility is to have some kind of standard protocol for time
>encrypted messages (this is interesting and seems feasible). Let's say
>I want a message [x] to be unencrypted on date [y].  I call a "time
>encryption server" and ask for the secret key associated with my
>message and date [y].  I encrypt the message and publicize that
>version.  The time server is constantly spewing out the daily code for
>messages that expire on that date. Anybody just listens to the
>broadcast and decrypts the messages in their possession using the key. 
>Note however that it is crucial that somehow the key depend on the
>message itself (via the hashing approaches), otherwise everybody knows
>everybody else's keys ahead of time just by submitting messages to the
>server for the particular date.  I suppose public-key encryption could
>be used here but I'm hazy on the details.

What came to my mind as I read Tim's message was various competing
timed-key servers, each publishing its public key associated with
various future dates, and promising to release the associated private
key on that date (but not before).  

You then encode your message with an m-of-n scheme using n such
server's keys for your chosen date, and assume at least m of them will
eventually publish their promised key, and assume no more than m of
them will release early.  You then leave it with several escrow
services and ask them to try to decrypt it once a year with the new
year's keys.

To prove to all that a server is untrustworthy, simply reveal its
private key ahead of time, and win a bond posted by the service (easy
to implement - encode some money with the public key, see if anyone
cashes it.)  There are economies of scale in shared monitoring of
trust, so perhaps only a few dozen such servers would be needed.

Hmm.. but how does the server get paid if the public key is public
knowledge?   

Robin Hanson