I have a distributed system where each client writes many small messages, roughly the size of messages in a chat system, e.g. ~100-200 bytes each. I want each message to be signed so that we know for sure who sent each message, but the overhead of an RSA signature on each message is huge, so I need another approach.
One idea would be to sign the first message like normal, and include a hash of a random value. Then, in the next message, include that random value and a new hash of another random value. Each message "unlocks" the previous message's hash, showing that they were authored by the same client. Using a bcrypt/scrypt/argon2 hash with a work factor to meet about 10ms would mean that the random value could be kept small, say 64bit. Each message also has a unique id, which would be used as a salt. This is a huge improvement in overhead, but I have no real idea how secure such a system would be. Also, messages store ordering information, so once a message has been "unlocked", that random value cannot be used to "sign" a second message.
Some messages would contain encrypted fields, using some form of hybrid encryption. The servers only need signed metadata, not the actual messages.
I'd say this is a great example of where "don't roll your own 1. distributed system 2. crypto" applies. I've got the distributed system part, but I need your help with the crypto.
How can I sign many small messages (tens of thousands) with as little size overhead as possible, while still being secure? I've got 50MB of RAM and about 10ms of cpu time for decryption of each message. The client must be able to sign, encrypt and send messages without getting a response from the recipient(s).