I've been trying to come up with more uses for Wirehair FEC to get the most benefit out of my work on that problem. It seems like you could use it for Threshold Cryptography.

What's Threshold Cryptography? Here's an example:

You have a bunch of people with parts of a key. No one person knows the whole key. If enough of them (N) people get together and share their key parts with each other, then they can recover the whole key.

This sounds a lot like the way Wirehair FEC works. In Wirehair FEC, if enough (N) file parts are received, then there is a high probability (97%) that you can recover the original file.

So to combine the two:

(1) Central authority generates a large random file, splits it into N pieces, and initializes Wirehair FEC with the file.

-- Each file piece is 256 bits.

(2) Central authority distributes the file pieces to lots of people (more than N).

(3) If any N of them share file parts with each other, they can probably recover the whole file.

(4) Use a 256-bit hash function applied to the whole recovered file to produce a shared secret key.

This is cryptographically secure because without at LEAST N parts, you cannot gain any information about the missing parts (they are XOR'd together).

It's really fast! Wirehair FEC is lightning fast, and hashes are even faster.

The downsides are that you need a central authority to decide what the secret key should be, so it's not a distributed scheme, and it also is not 100% guaranteed that you'll be able to recover the key with just N. You may need N+1 or more key parts. Also, Wirehair FEC is written in C++ so it doesn't run in a few places (like browsers) where it might be interesting.

What it does buy you is that you can generate 2^^32 different key parts and any N of them will very likely reveal the secret, and it's very fast. This might be useful for an offline scavenger hunt, where people can use this primitive math as a starting point to prove that they found all the pieces without validating each one with the central server.

What's Threshold Cryptography? Here's an example:

You have a bunch of people with parts of a key. No one person knows the whole key. If enough of them (N) people get together and share their key parts with each other, then they can recover the whole key.

This sounds a lot like the way Wirehair FEC works. In Wirehair FEC, if enough (N) file parts are received, then there is a high probability (97%) that you can recover the original file.

So to combine the two:

(1) Central authority generates a large random file, splits it into N pieces, and initializes Wirehair FEC with the file.

-- Each file piece is 256 bits.

(2) Central authority distributes the file pieces to lots of people (more than N).

(3) If any N of them share file parts with each other, they can probably recover the whole file.

(4) Use a 256-bit hash function applied to the whole recovered file to produce a shared secret key.

This is cryptographically secure because without at LEAST N parts, you cannot gain any information about the missing parts (they are XOR'd together).

It's really fast! Wirehair FEC is lightning fast, and hashes are even faster.

The downsides are that you need a central authority to decide what the secret key should be, so it's not a distributed scheme, and it also is not 100% guaranteed that you'll be able to recover the key with just N. You may need N+1 or more key parts. Also, Wirehair FEC is written in C++ so it doesn't run in a few places (like browsers) where it might be interesting.

What it does buy you is that you can generate 2^^32 different key parts and any N of them will very likely reveal the secret, and it's very fast. This might be useful for an offline scavenger hunt, where people can use this primitive math as a starting point to prove that they found all the pieces without validating each one with the central server.

last edit by catid
edited (>30 days ago) 9:30am Thu. May 24th 2012 PDT