# Ciphertext packing for bandwidth optimization

Let's say $$Alice$$ needs to send ciphertext $$c_b = enc(m_b,k_b)$$ to $$Bob$$ and ciphertext $$c_c = enc(m_c,k_c)$$ to $$Carol$$. For both the ciphertexts notice that underlying plaintexts are different (i.e. $$m_b, m_c$$).

Now imagine a single envelope needs to be sent to both $$Bob$$ and $$Carol$$ where both can decrypt and get their respective plaintexts $$m_b,m_c$$.

The trivial way is ($$c_b | c_c$$) (i.e concatenation) and use some delimiter for Bob and Carol to extract bits and decrypt respectively. But this needs bandwidth $$|c_b| + |c_c|$$.

Can we optimize this to use lesser bandwidth? Can such a thing exist at all?

• You can share e.g. IV if you take care, but you can't go below $|m_b|+|m_c|$. – otus Sep 15 '15 at 15:44

If $m_b$ has size $n_b$ bits, then there are $2^{n_b}$ possible messages $m_b$; and they MUST be all "possible" in the eyes of outsiders (including Carol). Similarly, there are $2^{n_c}$ possible messages $m_c$. Thus, there are $2^{n_b}\times 2^{n_c} = 2^{n_b+n_c}$ possible inputs to your problem.
If you have a system that can encrypt all such inputs into a sequence of $t$ bits, then there are $2^t$ possible output messages, and, from each such message, Bob and Carol can unambiguously extract $m_b$ and $m_c$, respectively -- if they work together, they will get both $m_b$ and $m_c$, unscathed. This implies that the encryption system must be injective: if $(m_b, m_c) \neq (m'_b, m'_c)$ (the message for Bob, the message for Carol, or both, are different), then they must encrypt to a different sequence of $t$ bits. Otherwise, it would not be possible to decrypt the result unambiguously.
Therefore, $2^{n_b+n_c} \leq 2^t$. This means that you cannot do really better than concatenation, in all generality.
In your specific case, you could also envision a compression scheme that exploits the similarities between Bob's and Carol's messages: split $(m_b, m_c)$ into three parts $(s_b, s_c, d)$ where $d$ is the part which is common in $m_b$ and $m_c$, $s_b$ is the part specific to $m_b$ and $s_c$ is the part specific to $m_c$. Then you can encrypt $d$ only once with a symmetric key $K$, and encrypt $K$ with the public keys of both Bob and Carol. Depending on the structure of your messages, this may save a lot of space. However, it also reveals to Carol a chunk of the the message sent to Bob; and even outsider can know how much data is shared between the two messages.