Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
1  
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

1 Answer

up vote 2 down vote accepted

Not sure if this fits your requirement, but, here goes.

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).

This could be generalized to larger messages (not just individual bits) if Trent is told the lengths of the messages.

Any cipher that is homomorphic with respect to addition could be used.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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