Yes, we can construct a cipher homomorphic with respect to the concatenation operation (noted $\mathbin\|$ ). In short, we make the encryption of a concatenation the concatenation of the encryptions.
Start from any (CPA or CCA-)secure cipher capable of enciphering into a fixed-size cryptogram a single-symbol plaintext (e.g., an octet or a bit depending on granularity thought). Note $E$ the encryption function, with $c=E(k,r,q)$ the result of the encryption under key $k$ with random nonce $r$ of the single symbol $q$, and $D$ the decryption function $c\mapsto D(c)$ such that $\forall k,\forall r,\forall q,D(k,E(k,r,q))=q$ (for asymmetric cryptography $k$ can be a public/private key pair with the public key used for encryption), Also assume a public pseudo-random permutation $r\mapsto P(r)$.
Then extend $E$ by stating that when $q$ is the concatenation of more than one symbol, it can be expressed as $q=\hat q\mathbin\|\tilde q$ with $\hat q$ the first symbol of $q$ and $\tilde q$ the rest, and $E(k,r,q)=E(k,r,\hat q)\mathbin\|E(k,P(r),\tilde q)$.
Correspondingly extend $D$ by stating that if $c$ is wider than the (constant-width) encryption of a single symbol, it can be expressed as $c=\hat c\mathbin\|\tilde c$, with $\hat c$ just wide enough for a single symbol, and $D(k,c)=D(k,\hat c)\mathbin\|D(k,\tilde c)$.
Using that operator $\|$ is associative, that construction $E$ can be shown (CPA or CCA-)secure as the original is (we use that applying the PRP $P$ iteratively on random/nounce $r$ generates a pseudo-random sequence); and has the property thought in the question, with $g$ concatenation.
$E$ can for example be AES-CTR with random IV $r$ at the beginning of the ciphertext; or RSAES-OAEP (with symbol a byte, or with encryption of a bit defined as encryption of the byte 00 or FF depending of the bit's value). $P$ can be any PRP independent of $E$.
One drawback of the above simple construction is that it expands ciphertext size considerably. However, that can be fixed, as follows.
- we start from any cipher than can cipher an arbitrary string of symbols, and prepend a single 1 bit to its ciphertext in that simple case
- we define $g(c_1,c_2)$ with $c_1$ of $k>0$ bits as the concatenation of
- as many 0 bit(s) as there are bits in the binary representation $k$
- the binary representation of $k$, big-endian (thus starting with a 1 bit)
- $c_1$
- $c_2$
- decryption parses the ciphertext
- if it starts with 1 then it is elementary and what follows the 1 is deciphered normally;
- otherwise, the ciphertext is composite; the number of initial 0 gives the length of the binary representation of $k$; $k$ follows; then $c_1$ follows on $k$ bits; then the rest is $c_2$; $c_1$ and $c_2$ are then deciphered, recursively.
