I am using ElGamal and Paillier schemes to encrypt a large number of short messages: typical 4-byte integers. I do this for the homomorphic properties of these schemes.
However, the way the encryptions work, with, say, a 1024-bit key a 4-byte integer will blow up into two values of overall size of 4096 bits or 512 bytes, which is, well, mildly inconvenient :)
As I deducted from examining the ECRYPT II report, the recommended key size for ElGamal is at least 1024 bits. I did not find recommendations for Paillier, though. However, as I understood, these recommendations are typically for larger messages. Hence, some questions:
1. Is there a difference in choosing a key length based on the size of a message?
2. What would be acceptable key sizes in the situation described above for both cryptosystems? If possible, I would like references to analyses I could read.
Bonus question: Let's assume an adversary gets a hold of an array of encrypted integers and tries to crack the encryption. How would he be able to determine whether he found a proper private key or not, if we assume that he is unable to tell a properly decrypted array from a random array?