Suppose we can construct a secure (IND-CPA) encryption scheme for fixed length messages. I was wondering if there is a natural way to extend this construction for messages of variable length such that it is still an IND-CPA secure scheme.
The typical way to make an encryption scheme work for variable length message is to use a mode of operation.
Since you are starting with an already IND-CPA secure cipher, even the often despised ECB mode will work. That said, you will still need padding to make the plaintext length a multiple of the blocksize. If adding padding is out of the question, a streaming mode such as CTR will work.
If you want a real variable length, you loose the IND-CPA security:
You have to make all possible ciphertexts equally long, so that the attacker can not distinguish between the longest possible message and a 1 bit message. If maximum length is not known at the key generation, your ciphertexts would need unlimited length.
If you allow the attacker to know the message length (this isn't IND-CPA anymore), you can choose any kind of encoding (e.g. blockwise or arithmetically) and apply encryption on each part individually.