The objective is to broadcast information over a noisy digital channel (corruption rate of say, 10-20 %, where bits flip). Assume the broadcasting software is public and there is no possibility of embedding secret information so a public key cryptosystem must be used. Let the adversary have full knowledge of the software but no control or knowledge of a broadcasting node.

Traditional methods to do this such as a "secretbox" or some other DH mechanism will give you a bit-string which is indistinguishabile from random but that string will be subject to corruption if transmitted naked.

So you have to use error correction coding. How to do this so that an adversary listening to the channel cannot detect the presence of the communication by detecting error correction codes? An adversary can do this by continually attempting to decode "noise" over the channel. Decoding tends to fail on random strings.

Note that this only has to be done for the DH part, afterwards an unauthenticated stream cipher can solve this.

From my search it seems that perhaps only Goppa codes in a construction similar to McEliece's Public key cryptosystem can help, but I do not know how to proceed.

  • 1
    $\begingroup$ How is DH involved? Can you reframe your question so that you state, at the outset, who the parties are, what resources they have, what the powers of the adversary are, and what you are trying to ensure the adversary cannot do? $\endgroup$ Apr 7, 2019 at 21:45
  • $\begingroup$ Stream cipher for the communication. Take your plaintext, authenticate it, encode it with error correction, then encrypt. Not typically recommended (encrypt then authenticate is the recommended secure approach)! However, this method provides secrecy along with reliable decryption and authentication. As for the key exchange? You desperately need a signaling channel to coordinate. You can try broadcasting an equivalent to TOTP codes to get a secure random number to signal the start of a key exchange. This assumes a pre-shared secret. Use the secret to also symmetrically encrypt the key exchange $\endgroup$
    – Natanael
    Apr 8, 2019 at 0:29
  • $\begingroup$ Using a pre-shared secret to encrypt the key exchange will both offer PFS and hide the communication attempt from anybody watching the noise. The key exchange could be a password authenticated key exchange like OPAQUE, also using the pre-shared secret to authenticate. After authentication, you switch from using the pre-shared secret to encrypt communications to using the session key to encrypt. All of this effort to avoid detection still assumes you can actually broadcast without the signal being detectable by strength alone, or similar. Also assumes consistent white noise as background noise $\endgroup$
    – Natanael
    Apr 8, 2019 at 0:39
  • 1
    $\begingroup$ So Alice and Bob share public information, but no secrets, and the goal is to establish a shared secret with high probability over a noisy channel, so that the distribution of the handshake messages has some prescribed maximum statistical distance from the distribution of the noise? $\endgroup$ Apr 8, 2019 at 1:46
  • $\begingroup$ So Bob knows public information about Alice, but no secrets, and his goal is to anonymously send Alice a secret message over a noisy channel, so that the distribution of the ciphertext has some prescribed maximum statistical distance from the distribution of the noise? $\endgroup$ Apr 8, 2019 at 2:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.