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 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?

  • $\begingroup$ I don't get it. RSA-RSA-OAEP is used for encryption, where you want to use key-encapsulation ( RSA-KEM better). Why do you want to mangle ECDH with encryption? $\endgroup$
    – kelalaka
    Commented Nov 16, 2023 at 10:57
  • $\begingroup$ The ECC overhead for a curve with 128 bit security is 32 bytes. Are you saying that 32 bytes is too much for you? $\endgroup$
    – poncho
    Commented Nov 16, 2023 at 20:41
  • $\begingroup$ Yes, 32 bytes can be quite a bit. LoRa radio packets are a good example of a constrained application. An entire packet might be 50 bytes. If I can pack data into the point to be sent that can cut message size quite a bit. $\endgroup$ Commented Nov 17, 2023 at 11:23
  • $\begingroup$ So to be succinct, you want key establishment with reduced overhead in number of bytes transmitted, correct? $\endgroup$
    – Maarten Bodewes
    Commented Nov 17, 2023 at 13:14
  • $\begingroup$ Not key establishment, but per message secrecy/tamper_resistance. Each message is encrypted to the receiver's public key and contains an ECDH ephemeral key, symmetrically encrypted ciphertext and MAC tag to prevent tampering. $\endgroup$ Commented Nov 17, 2023 at 17:25


Your Answer

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

Browse other questions tagged or ask your own question.