Can the backdoor in Dual_EC_DRBG be used to create a public key stream cipher?

Question

Dual_EC_DRBG has the property that if $Q = e\cdot P$, someone who knows $e$ can break the PRNG.

This seems to lead to a public-key stream cipher:

• Alice chooses a random $P, e$, where $P$ is a generator.
• Alice computes $Q = e\cdot P$.
• Alice publishes $(P, Q)$ as her public key. She retains $(P, e)$ as her secret key.

To send a message:

• Bob chooses a random seed $S$.
• Bob publishes the first $n$ bits of the output.
• Bob uses the rest of the output as a keystream.

To decrypt, Alice uses her knowledge of $e$ to break "PRNG" and recover the keystream.

Is this system secure? Does it provide any advantage over other forms of asymmetric cryptography?

Answer 1

You can do something like what you are suggesting. But, the EC_Dual_DBRG also has biases in the stream and so you cannot use it without changes (e.g., truncating much more). However, this is based on the same operations as ElGamal.

The public key is set up exactly as proposed. Then, to encrypt a message $m$ of any length, do:

1. Choose a random $r\in\mathbb{Z}_q$, where $q$ is the order of the Elliptic curve group
2. Compute $U=r\cdot P$
3. Compute $k = H(r\cdot Q)$
4. Encrypt $m$ with $k$ using any symmetric encryption scheme you wish