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

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.

• The EC setting is because the users in the theoretical system are already assigned EC key pairs and already communicating via ECDH. However, if Bob has never communicated with another party previously via ECDH, it would be extremely useful for him to be able to receive a small integer from a stranger without the computational overhead of the full ECDH operation. The system is one where everyone is aware of everyone else's communication. – knaccc Feb 13 '17 at 3:03
• Just using a lookup table would not work because Bob needs to be able to receive values of $n$ from strangers that have not prearranged a lookup table with Bob. If they had a chance to confer beforehand, obviously a symmetric key could be used, but the problem involves receiving messages from strangers. – knaccc Feb 13 '17 at 3:12
• Bob does know $R$, he is sent $R$ and $p$. He can be sent other things too if necessary. – knaccc Feb 13 '17 at 6:36
• Curve25519 should be able to handle up to 100k DH operations per second on a fast quad-core. Switching to a faster DH function like gls254 should bring that up to 400k or so. – CodesInChaos Feb 13 '17 at 9:15
• @CodesInChaos the reason performance is critical is because Bob will be reading through many gigabytes of data to process discover each $n$ that he is sent. – knaccc Feb 13 '17 at 13:29

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) {