Fast patent-free error-correction?

[Nick Mathewson <nickm@alum.mit.edu>]

[Please show the relevant part of this message to people who know a lot
about the topic; it may be that nobody on this list knows.]

[Please send replies to me; I'll summarize to the list.]

I have a new design for end-to-end.  It's better, more consistent, and
adds: real integrity checking, a more consistent vocabulary, and message
compression.

What I don't have is k-of-n.  Moreover, I'm not even sure how to do it. 
All of the algorithms I can find out about are either slow, patented, or
both.

Can anybody help out?  I need an algorithm with the following
parameters:

Given a M-packet message, the algorithm must yield N packets.  Given K
randomly-chosen packets, it should be possible to reconstruct the
original message. (When packets are lost, they are erased at random, not
corrupted.)

The packet size is about 28 kilobytes. Messages range from one packet to
several megabytes.  N should be about 2*M.   K should be very close to
M.  Encoding and reconstruction should be efficient.  

What "efficient" means:  On an Athlon XP 1700+, a sender currently
spends about 80 msec per 28k packet.  A receiving server spends about
9.3 msec per 28k packet.  It would be great if the error-correction
method didn't overwhelm these times.

Tradeoffs: efficient reconstruction matters more than efficient
encoding.  More messages will be short than long.

Patents: The method must not be patent encumbered at all.

Stuff I've looked at:

 - Rabin: Roger says it's patented.  It's also slow.
 - Cauchy: Faster than Rabin, but still unpleasantly slow.  I don't know
	if it's patented.
 - Tornado: Very fast, very cool, but patented.  Unpleasant start-up 
        time to do precomputation for a given set of K/M/N parameters.
 - "This Other Thing Besides Tornado That Luby Did".  Even cooler than
        Tornado.  Way less start-up time. Still patented.
 - "This Thing With Vandermonde Matrices That Luigi Rizzo Did".
	Looks faster than Rabin, slower than Tornado.  Patent status 
	unknown.

Can anybody give me a hand here?  Are there any algorithms that work for
this domain that aren't patented?  If not, is anybody out there willing
to give free (or GPL, or LGPL?) software an unrestricted license to
their technique?

Yours,
-- 
Nick