# Homomorphic cryptosystem with respect to concatenation

Are there cryptosystems that are homomorphic with respect to the concatenation operation? those. there are data q1 and q2, where q3 = q1q2. then the encrypted data f(q1) = c1 and f(q2) = c2 and f(q3) = g(c1, c2) ? And are there cryptosystems that are homomorphic with respect to data fetch, i.e. reverse operation, with respect to concatenation?

## 1 Answer

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.