Homomorphic cryptosystem with respect to concatenation

Question

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?

Answer 1

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.