[freehaven-dev] Just In Time Signatures - reasons for use and possible candidates

[dmolnar <dmolnar@hcs.harvard.edu>]

At the meeting today, someone brought up "just in time" signatures as a
possible tool for free haven. In case you didn't take or design the 6.857
midterm this year, a "just in time" signature is a signature
scheme for which much of the computation can be done independent of the
message to be signed. The results of this precomputation can then be
combined extremely efficiently with the message to create a real
signature.

We would want such a scheme to deal with "bursts" of messages which need
signing all at once. Such bursts might occur...actually, I'm having 
trouble remembering when we wanted this? I seem to remember it coming up
in the context of broadcasts, but there we could sign the message once and
then *encrypt it many times*. So we really want a "just in time encryption
scheme" ? 

Anyway, continuing with signature schemes : 

The 6.857 midterm noted that ElGamal sigs can be made "just in time."
I just noticed that there's a paper in the last ACM Computer and
Communications Security Conference proposing another "just in time" 
scheme :

"On the Fly Signatures Based on Factoring"
Guillaume Poupard , Jacques Stern
http://www.dmi.ens.fr/~poupard/ps/PoSt99.ps

Maybe more interesting than the scheme proposed there is a table comparing
various signature schemes with regards to their online and offline
computational complexity, key size, and underlying assumption. 

It's maybe too early to consider this in full depth now, but maybe down
the line we can look at this in more detail. 

Thanks, 
-David