# Perfectly secret variable one-time pad

Consider a variable one-time pad, that is, $$\mathcal{M}:=\{0,1\}^{\leq \ell}$$ is the set of plain text. Now, this scheme is not perfectly secret, since you can take two plain text of different size, say $$|m_1| = 1, |m_2| = 2$$ and considering a cipher text $$c$$ of length 1, the next happens: $$Pr(E(k, m_1) = c) = \frac{1}{2},\ Pr(E(k, m_2) = c) = 0.$$

Thus, how can I make a construction of this variable one-time pad such that it's perfectly secret? Is it even possible?

I tried to make sub-one-time pads, i.e., $$\ell$$ one-time pads, but it doesn't work when you have two messages of the same length (same as above), so my other idea was to extend all messages to be length $$\ell$$ by adding zeros to the right. The problem though, is that if you consider $$\ell = 4$$, how can you decrypt the messages 1, 10, 100, 1000?

• your plaintexts are the same size, no? Mar 28, 2022 at 23:51
• @kodlu No, they are at most size $\ell$. Mar 29, 2022 at 0:40
• Hi Lug and welcome :-) Review the question please as it's confusing. What exactly are you asking? We love one time pads here though... Mar 29, 2022 at 1:43
• Thanks @PaulUszak! In simple words, I'm trying to form a variable length one-time pad that it's perfectly secret. Mar 29, 2022 at 2:41
• Okay. Yes OTP is informational secure. But you're talking formulae. Is there a device to produce the key material? And I don't understand the "variable" bit. Do you mean that |key| = |plaintext|? And what's $|m_1| = 1, |m_2| = 1$? One bit? Mar 29, 2022 at 3:00

The (binary) one-time pad is indeed proven to be perfectly secure in an information-theoretic sense, assuming the following: the message length exactly $$n$$ and a shared source of uniform randomness.
It is often overlooked that this security definition is not appropriate for general contexts where variable-length data is sent. For instance, an application where are yes and no are the only message sent would be insecure when applying the one-time pad naïvely.
Solution 1: Message padding The easiest way would be to apply a length hiding mechanism, a padding scheme that pads messages to the same length and then encrypts the padded message. Namely. for messages of length $$l$$, messages can be padded to length $$k = l + 2$$ (long can work as well). The padding of $$m$$ is $$pad(m) = m \|10^{k - |m| - 1}$$. This can be done since the problem statement does not restrict the length of the pads.
Solution 2: Encoding onto a group. Since there are $$k = 2^l$$ messages, another idea would be to encode (bijectively) messages into a group-like structure with the same cardinality; from there, one can apply the OTP over the group. Decryption requires decoding. The simplest example would be $$(\mathbb{Z}/k\mathbb{Z}, + )$$
• So I was reading again this solution and now I got one question for each solution. For solution 1, how do you decrypt the message to obtain $m$ again? The receiver can't know which bits they need to remove since the padding was also encrypted. And for solution 2, I think the number of possible messages is $\sum_{i=0}^\ell 2^i$ since it's variable. Mar 29, 2022 at 19:33