Skip to main content
1 of 7
fgrieu
  • 145.7k
  • 12
  • 319
  • 611

Yes, we can construct a cipher homomorphic with respect to the concatenation operation. 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 plaintext of single symbol (e.g. octet or bit depending on granularity thought). Note $E$ the encryption function, with $c_i=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 such that $\forall k,\forall r,\forall q,D(k,E(k,r,q))=q$. 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 is broken 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 is broken into $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$ has the property thought in the question, with $g$ concatenation; and can be shown (CPA or CCA-)secure as the original is.

$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 0x00 or 0xFF dependign of the bit's value). $P$ can be any PRP independent of $E$.

fgrieu
  • 145.7k
  • 12
  • 319
  • 611