# Incorporating known ciphertext into new message

Which ciphers $c_k$ enable one to define a joining function $f_{c,k}$ such that:

$$f_{c,k}(c_k(p_1), p_2) = c_k(p_1 + p_2)$$

That is, the result of joining some known ciphertext $c_k(p_1)$ with a plaintext $p_2$ produces the same ciphertext as the concatenation of the respective plaintexts? Whilst there is some flexibility to modify $p_2$ (e.g. with padding) it cannot be chosen entirely arbitrarily.

What terminology applies to such cipher/function/messages?

-
Well, if $f_{c,k}$ is allowed to depend on the key, then any invertible cipher has this property; the $f_{c,k}$ function just needs to decrypt its first argument, concatinate the second, and then reencrypt the result. What are you trying to do? What are the actual requirements? –  poncho Jun 11 '12 at 21:21
@poncho: Duh, good point! Assume asymmetric cipher where only public key is known. I'm trying to devise means for Alice to store with Trent a message destined for Bob; Trent will later forward that message to Bob over pure HTTPS. –  eggyal Jun 11 '12 at 21:27
Okay, this was a dumb question as the actual session key negotiated between Trent and Bob won't be known by Alice in advance of that session. I presume therefore that there will need to be a higher encryption layer between Alice and Bob; it is simply not possible for Trent to store and forward HTTPS messages? –  eggyal Jun 12 '12 at 6:26
@eggyal, Without Trent knowing the plaintext, right? If Alice and Bob have a preshared secret, then it could possibly be done, though the solution would probably be non-standard. If they don't have a preshared secret, do they each have public/private key pairs? –  mikeazo Jun 12 '12 at 11:36
@mikeazo: Trent will not know $p_1$, that's correct (it would otherwise be a trivial problem, I think?); however he will know (indeed, he will generate) $p_2$ as that would be the HTTP headers and/or other application-layer encapsulation of Alice's message. Alice and Bob do indeed have public/private key pairs. –  eggyal Jun 12 '12 at 11:39

Using the homomorphic properties of ElGamal, you could turn $E_{pk}(b_0),E_{pk}(b_1),E_{pk}(b_2),E_{pk}(b_3),E_{pk}(b_4),\cdots,E_{pk}(b_n)$ (where $b_i\in\{0,1\}$, i.e., individual bits), into $E_{pk}(b_0||b_1||\cdots||b_n)$ (where $||$ is concatenation). This is done by using homomorphic scalar multiplication and addition (multiply by 2 then add the next bit, repeat as necessary).
What if the two messages are of different lengths? In my case, $p_2$ would be HTTP headers (generated by Trent) whilst $p_1$ is some arbitrary length message... Alice could inform Trent of its length if that wouldn't impair secrecy. –  eggyal Jun 11 '12 at 23:36
@eggyal, if Trent knows the length of $p_1$ (say $\ell$ bits), then Trent can multiply the cipher text by $2\ell$, then add in $p_2$. Remember though that the plaintext space of ElGamal is integers modulo $N$ where $N$ is the product of 2 primes. So, you won't be able to fit unlimited data into the ciphertext. –  mikeazo Jun 12 '12 at 11:34