3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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. octet or bit depending on granularity thought). Note $E$ that 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 ryptography $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 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$ 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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