Can the byte overhead of an ECDH based hybrid cryptosystem be reduced by encoding data in ephemeral key?

Question

Motivation

I have a use case that involves sending small (25-50 byte) encrypted messages over a very constrained channel. Many senders send public key encrypted messages to other receivers. Anonymity (eavesdropper can't tell which sender sent a message) is the reason for using asymmetric crypto.

I'd like a cryptosystem that imposes the least byte overhead.

RSA-OAEP

RSA-OAEP allow packing data into the asymetric primitive to cut down on overhead. When encrypting a single message, the byte overhead of the n-bit RSA integer that established that message's symmetric encryption key can be reduced by packing data into it. The receiver undoes the RSA public operation to recover the OAEP encoded integer, reverses the OAEP padding and can recover message bits the receiver packed into integer in addition to the symmetric key used to encrypt the rest of the message.

For large enough messages, packing bits into the RSA ciphertext makes the overhead quite low.

• some bits of randomness in the RSA plaintext
  • establishes the per-message symmetric key
  • randomises the RSA ciphertext to prevent attackers verifying a known plaintext
• some MAC bits to prevent message tampering.

Note that this wouldn't be vanilla OAEP anymore since that does impose a lot more overhead.

Can something similar be applied to an ECDH based cryptosystem?

The minimum recommended key size for RSA is 2048 bits. A low overhead OAEP-like message encryption system will have a minimum encrypted message size of 2048bits/256bytes, since each message will contain an RSA ciphertext of that size. for small plaintexts, this adds a lot of overhead.

For ECDH, one simple optimisation is to use the ephemeral key as a MAC tag. A fully deterministic $Enc(K_{receiver},Message)$ cryptosystem can be checked against a guess by an attacker, which is annoying. Additional per-sender secrets (EG:known sender public/private keypairs) can mitigate this though forward secrecy is lost regardless since there's no randomization of ciphertexts.

There's a few primitives that would be useful here:

• a generator/distinguisher for a small subset of points.
  • sender generates P=pG as an element of the subset.
  • Adds a pseudorandom point X=xG to get an ephemeral key K=P+X.
    • this acts as a MAC tag
  • Receiver recalculates and subtracts X then verifies P is in the subgroup.
• something similar but now the generator/distinguisher pack some bits into the element P
  • EG:$P=xG,0\leq x<2^k$
    • can split k bits into a u bit lookup table of the first 2^u multiples of G and calculation of 2^v values to check against lookup table.
    • allows somewhat efficient recovery of discrete log where scalar multiple of G is small (32-48 total bits is doable).
    • baby-step/giant-step algorithm doesn't seem to work. Confining to the 2^k range or similar seems impossible without knowing the discrete log beforehand, can confine to $2^{k^2}$ range but then lose sqrt(n) benefit.

Obviously packing in all the bits won't work, at least if the scalar is recoverable, that would require solving the full discrete log problem at the other end. Is there some way to pack 64-100 bits into a point efficiently?

Alternately some way to split of a subset of 2^64-2^128 points from a group of around size 2^256 (curve25519, P256, etc.) that satisfy a verification equation but whose discrete logs are known at generation time?