Is public-key spread-spectrum communication possible?

Question

Alice wants to get a message to a large number of people living under a censorship-happy government, run by Eve. The traditional way of doing this is samizdat, but that process requires each person passing a message to take a certain risk. It would be nice of there were some way of doing this directly.

Spread-spectrum communications are resistant to jamming. However, this method assumes a shared secret key. It is implausible for this to remain secret when distributed to the audience, and when Eve obtains the key, she can jam the channel.

So, the question is: Is it possible to device a communications method like spread-spectrum, which does not require a shared key?

To be specific: A solution would require resistance to jamming, and that the receivers can authenticate that the message was sent by Alice. Secrecy is not a requirement (and is implausible anyway).

More formally: Alice wants to send a message m over the radio spectrum. Alice has a public/private key pair, and uses it to encode the message into a cyphertext C, (we can take C to include the details of how the message is modulated for transmission). Alice can only transmit at some power level Ap. Eve only knows the public key. Alice's recipients only know the public key. Eve can transmit a jamming signal, presumably at a much higher power level than Alice, although not without limit (especially on areas of the spectrum already being used for, say, TV channels). In a solution, Alice's followers will still be able to decode the message using only the private key.

Additionally, Alice would like to be able to repeat the exercise without having to circulate a new public key. Suppose that the system worked on the first message, but that Eve was able to obtain the cyphertext C. Then, if the system does not vary over time, Eve will be able to jam the channel using the C. So either the system must vary with time, or Eve must not be able to obtain the cyphertext.

Some authors have described public-key steganography schemes, eg [1]. considers active attacks that attempt to break the secrecy or authenticity of the scheme, by sending additional messages, but not than ones which perturb existing messages. [2] Does consider these kind of attacks, but their scheme is not obviously applicable to spread spectrum (to me, at least): It only copes with a limited amount of perturbation, and in doing so reduces the bandwidth of the channel a great deal.

Fingerprinting and covert channel schemes do consider 'jamming' type attacks, but I am not aware of them using public key crypto to counter such attacks.

[1] "Public-key steganography with active attacks", Michael Backes and Christian Cachin

[2] "On the limits of Steganography", Anderson and Peticolas

Answer 1

Google reveals that the System Security Group at ETH have done work on "jamming-resistant radio broadcast communication without shared secret keys". Perhaps this would be a good place to start?

Answer 2

Yes, it can be done. The following paper describes a construction that solves your problem:

• Anti-jamming Broadcast Communication using Uncoordinated Spread Spectrum Techniques. Christina Pöpper, Mario Strasser, and Srdjan Capkun. EEE Journal on Selected Areas in Communications (JSAC): Special Issue on Mission Critical Networking, 2010.

Their solution is actually even better than you asked for. They also provide security against insider attacks: even an authorized recipient does not obtain any information that would allow the recipient to jam the channel and prevent others from receiving the broadcast.