Bob has an EC key pair. How can he receive a small integer in the least compute intensive way?

Question

Alice wishes to send Bob a number $n$ between 0 and 255.

Bob has a private, public EC key pair $(b, B)$ where $B = bG$ and $G$ is an already agreed upon base point on the ed25519 curve.

Alice could roll a random number $r$ and perform a Diffie Hellman exchange to compute the shared secret $rB$. Alice could then use the shared secret $rB$ as a symmetric key to encrypt $n$, resulting in an encrypted payload $p$. Alice can then send Bob $R$ and $p$ where $R=rG$.

Bob would compute the shared secret as $bR$ and then use this as a symmetric key to decrypt the payload $p$ to discover $n$.

This requires Bob to perform some considerable computation, particularly the EC multiplication required to calculate $bR$.

What alternative method can Alice use to send $n$ to Bob, making use of Bob's EC key pair $(b, B)$, which would require the least taxing computation by Bob?

We are not too concerned with how taxing the computation is for Alice. It's only Bob's computation time that we wish to minimize.

Assume that observers of the communication are aware that some number $n$ between 0 and 255 is being transmitted. It is important that only Bob can discover Alice's choice of $n$, and important that an observer cannot detect when Alice sends the same value of $n$ to Bob twice. Observers are aware of Bob's public key $B$.

Given that many different people will want to send Bob a number $n$, it is perhaps likely that a good solution may involve Bob using a pre-computed lookup table of some sort.

The transmission to Bob cannot be interactive.

Answer 1

Suppose there are many different Alices: Alice 0, Alice 1, Alice 2, etc. Suppose each Alice sends Bob not just one number, but a lot of numbers.

Bob has a secret Diffie–Hellman key $b$ and a corresponding public key $B$. The $i^{\mathit{th}}$ Alice has a secret key $a_i$ and a corresponding public key $A_i$. For some subset of Alices, Bob additionally stores a cache mapping $A_i$ to the shared secret $k_i = \operatorname{DH}(b, A_i)$.

For the $i^{\mathit{th}}$ Alice to transmit a number $m$, she generates a nonce $n$ uniformly at random and sends $A_i \mathbin\Vert n \mathbin\Vert c$, where $c$ is the authenticated encryption under key $k_i = \operatorname{DH}(a_i, B)$ of $m$. When Bob receives $A_i \mathbin\Vert n \mathbin\Vert c$, he consults his cache to find $k_i$ from $A_i$, or computes $k_i = \operatorname{DH}(b, A_i)$ if it's not cached, and caches the result, with some cache eviction policy if you want to limit the cache size.

This way, if there are $\ell$ different Alices, Bob is required to compute only $\ell$ different DH computations—no matter how many numbers he may be receiving. Depending on the cache eviction policy, he may need to recompute some of them from time to time. With a good cache eviction policy, if the number of numbers received is much greater than $\ell$, you can save a lot of computation.

The NaCl crypto_box API enables this by separating the per-peer DH computation, crypto_box_beforenm, from the per-message authentication and decryption, crypto_box_afternm. The control flow looks something like:

unsigned char k[crypto_box_BEFORENMBYTES];
unsigned char m[...];

if (!probe_cache(theirpub, k)) {
  crypto_box_beforenm(k, theirpub, mypriv);
  store_cache(theirpub, k);
}
if (crypto_box_afternm(m, c, clen, n, k) == -1) {
  bad();
}

You may have to be careful transferring key material intended for Ed25519 to the X25519 computations in NaCl crypto_box—figuring out how to do that safely, like XEdDSA does the other way around—is left as an exercise for the reader.