Suppose you have a public program P(n) which takes message n and generates an encrypted output (utilizing asymmetric cryptography) for some entity which has the private key to decrypt it.

Using a scheme such as Elligator (for elliptic curves) it is possible to have P which has output indistinguishable from random.

But a problem arises when the output is expected to be subject to corruption (bit flips). An application of error correcting codes seems to break the 'indistinguishable from random' requirement.

After considering the problem I arrived at the following consideration. The actual message n is encrypted by a symmetric encryption scheme using some shared secret, the same shared secret (after KDF) can be used to whiten (w/ stream cipher) the result after the application of error correcting codes to it. Would there be a problem with this approach?

This leaves the ephemeral public key (~256 bits) which due to Elligator is indistinguishable from random. But is subject to corruption. How can error correction be used on it such that the result is itself indistinguishable from random?


There appears to be some confusion regarding the encryption part. It's a standard anonymous sender sealed box. https://libsodium.gitbook.io/doc/public-key_cryptography/sealed_boxes

ephemeral_pk ‖ box(m, recipient_pk, ephemeral_sk, nonce=blake2b(ephemeral_pk ‖ recipient_pk))

The 'indistinguishable from random' requirement is mandatory, there is a Markov chain that mixes it with a structured format. Extraction of this embed cannot be allowed to yield something containing detectable error correcting codes, betraying its presence. In its absence, actual noise with no statistical pattern is extracted instead.

  • $\begingroup$ Hi, I've been thinking about the exact same problem, elligator and all. I came across this question which has some interesting answers, although I've yet to decide on the best solution crypto.stackexchange.com/questions/19340/… $\endgroup$
    – Retr0id
    Commented Mar 5, 2023 at 21:18

1 Answer 1


The actual message n is encrypted by a symmetric encryption scheme using some shared secret

The symmetric encryption is keyed by what key? Is it something that the encryptor picks? If so, how does it get to the decryptor (as the decryptor would need it before he can attempt a decryption). Is it something that both sides share? If so, how is this 'public key encryption' (which typically assumes that the encryptor has access only to publicly available information)? And, if you do have a shared symmetric key, what are you bothering with asymmetric crypto?

On the other hand, might I suggest considering thinking about this 'indistinguishability from random' option (and why it is a requirement)? In general, we usually don't need something that is literally indistinguishable from a set of random bits (some cases do arise; they're comparatively rare). Instead, it is generally enough to have 'indistinguishable from a random selection from a specific set' (and it doesn't matter what that set it); that formulation preserves the IND-CPA property we are typically interested in. And, if you just generate the 256 bit indistinguishable-from random word, and then apply your error correcting code to it, this set becomes 'the set of all valid code words in your error correcting code', which is enough for most purposes.

I had to put in some cavaet language in there, because there are some uses that really do require 'indistinguishability from a set of random bits'; what is your use case?

  • $\begingroup$ Shared secret = ECC (ephemeral public key, static private key) = ECC(static public key, ephemeral private key) The ephemeral public key is concatenated with the encrypted message... I believe this construction even has a name in some libraries, sealed box or something like that. Edit: libsodium.gitbook.io/doc/public-key_cryptography/sealed_boxes $\endgroup$ Commented May 22, 2020 at 21:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.