Alternatives to cryptographic signatures

Question

I have a program I am developing and am currently using ed25519 to cryptographicaly sign messages. However, even those signatures are longer than I would like (64 bytes + the message).

The messages I am signing are generated from within my system (i.e. I am generating and signing the messages within my program, on different servers/nodes).
What are the implications if instead of encrypting the messages (with any strong cipher), I would limit the overhead of the signature?

The messages currently are 72 bits long (currently to limit collisions of a relatively small number of messages), but I am thinking about increasing that to 104 or so bits, and appending a salt to it (not sure how long is acceptable), and encrypting the salt+message. On the receiving node, I can then decrypt the message, and verify the salt (so it would need to be an acceptable length).

My overall goal is to be able to verify the message is valid, and retrieve the message (does not matter if it's visible or not) with the smallest overhead possible, with both endpoints under my control, but the communication is always stateless and easily modified by a third party.

Answer 1

My overall goal is to be able to verify the message is valid, and retrieve the message (does not matter if it's visible or not) with the smallest overhead possible, with both endpoints under my control, but the communication is always stateless and easily modified by a third party.

You don't seem to require encryption, since it "does not matter if [the message is] visible." Rather, you seem to just require an integrity check on the message.

So, instead of encrypting you can use a Message Authentication Code (MAC) that is appended to the plain text message. However, in order to avoid the adversary tampering with the MAC, you still need a shared secret key on both endpoints. In this case the key is an "integrity key" not an "encryption key."

There are well-known methods for creating a strong keyed MAC, one of these well-known methods is called "HMAC" (see Wikipedia for brief description).

If use use a SHA256-based HMAC then the overhead will be 32 bytes (256 bits).

Update: As mentioned in the comments, there are alternatives to the SHA256 hash function that can be used--HMAC can be used with any hash function, but for your purposes a cryptographically secure hash function (like SHA256) should be used. Also, the commentator mentions that the HMAC tag can be truncated from 32 bytes down to a smaller length such as 16 bytes. This is true. The trade-off is that truncation makes it easier for the attacker to forge a tag, but for your purposes the difference in attack difficulty in forging a 16 bytes tag vs a 32 byte tag may not be an issue.