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 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.
  • $\begingroup$ Can this be applied to ElGamal, @fgrieu? $\endgroup$
    – Fiono
    Mar 11, 2021 at 15:25
  • $\begingroup$ @Fiono: yes. Any cipher goes. Beware however of the considerable ciphertext expansion, and that textbook ElGamal is insecure $\endgroup$
    – fgrieu
    Mar 11, 2021 at 16:02
  • $\begingroup$ Thank you for the answer! I was trying to see if it could be used to answer this question, but I don't know how: crypto.stackexchange.com/questions/88760/… $\endgroup$
    – Fiono
    Mar 11, 2021 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.