🚀 go-pugleaf

Subject: Re: time-release keys
References: <1dohq8INNbs4@transfer.stratus.com>

cme@ellisun.sw.stratus.com (Carl Ellison) writes:

>We could encrypt millions of times over, using different keys, but the
>computation time preparing the secret might take longer than the
>transmission (or at least a sizeable fraction of it).


>Does anyone out there have an idea of how to achieve this time-release of
>info (probably of an encryption key rather than of a body of text) with the
>independence of human good behavior but a decent time interval?

There was a paper at Crypto (by names I can't recall at the moment)
that dealt with the problem of time locks in the context of preventing
junk mail. They wanted to turn "computation" into a surrogate for
cash and force the junk mailers to do a massive computation in order
to decrypt your name. 

But I think the context of time locks is more general. I've considered
the problem a bit and decided that there are two things you need
to make the system practical:

1) A function that takes much longer to decrypt than encrypt.

2) A good estimate on the complexity of time needed to do this
decryption.

The public-key systems like RSA are good solutions to 1, but
we have only experimental evidence about the amount of time
needed to break the system. In fact, different keys of the 
same size in RSA could take substantially different amounts
of time to break using the current algorithms. If you could
come up with some good theoretical bounds to solve 2 then
you would surely make some people happy.

Another solution is to use a block cipher like DES and require
the "decryption" to be done by brute force. This allows us
to get a much better handle on the "complexity" of breaking
a cipher. 

The disadvantage of this approach is that it is weak to 
large parallel machines. The people with more firepower
can spin the clocks of these time locks faster than the 
owners of a 486 box.

One way to resist this approach is to compose many time
locks in a row. Let f be a block cipher (like DES) with
n bits where n is a number that is small enough so that
all of the 2^n keys can be tested rather rapidly. Then
compose these until you've got a time lock that takes
the right amount of time. The disadvantage of this is 
that you are reducing your amount of leverage by reducing
the ratio between the encryption and the decryption time.

Unfortunately, the biggest single problem to solving this
equation is predicting the future power of computers and
new algorithms. Many people have noted that the best way
to do a calculation that would take 100 years on a current
machine is to wait something like 30 years and do it in 
minute on the machines of that generation. The workstation
market seems to be accelerating even faster than they thought
it would in their predictions. This is why I've always
contended that P=NP. The power of computers doubles by
a power of 2 every few years. As long as this keeps
going, any exponentially growing problem can be sovled
in a linear number of years. But I digress...

On the balance, I think it is a good thing that time
and computation aren't equivalent.

But, there are also strict hardware solutions. Why not
lock some chip with a built in clock and battery in a 
shielded, tamper resistant box and program it not to
reveal the information until The Day? It's just a problem,
then, of finding something suitably impermiable.

-Peter Wayner

>-- 
>-- <<Disclaimer: All opinions expressed are my own, of course.>>
>-- Carl Ellison					cme@sw.stratus.com
>-- Stratus Computer Inc.	M3-2-BKW		TEL: (508)460-2783
>-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298	FAX: (508)624-7488