5
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ your plaintexts are the same size, no? $\endgroup$
    – kodlu
    Mar 28, 2022 at 23:51
  • $\begingroup$ @kodlu No, they are at most size $\ell$. $\endgroup$
    – Lug322d
    Mar 29, 2022 at 0:40
  • $\begingroup$ Hi Lug and welcome :-) Review the question please as it's confusing. What exactly are you asking? We love one time pads here though... $\endgroup$
    – Paul Uszak
    Mar 29, 2022 at 1:43
  • $\begingroup$ Thanks @PaulUszak! In simple words, I'm trying to form a variable length one-time pad that it's perfectly secret. $\endgroup$
    – Lug322d
    Mar 29, 2022 at 2:41
  • $\begingroup$ 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? $\endgroup$
    – Paul Uszak
    Mar 29, 2022 at 3:00

1 Answer 1

Reset to default
2
$\begingroup$

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}, + )$

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Lug322d
    Mar 29, 2022 at 19:33
  • $\begingroup$ @Lug322d, regarding 1) It is usually assumed that the legit receiver has access to the pads. So decryption works by applying the pad, and the undo the padding; obviously, another hidden point is no one did not modify that ciphertext. Regarding 2) That's a good point, I guess it also depends on what you consider as message. Do you consider "01" and "001" as different messages? $\endgroup$
    – Marc Ilunga
    Mar 29, 2022 at 20:15
  • $\begingroup$ I see, that makes sense. And yes, 01 can be distinct to 001. Still you could make that group though, but it will not be a finite field which, if it were, it will simplify a lot of things. $\endgroup$
    – Lug322d
    Mar 29, 2022 at 21:41
  • $\begingroup$ The second method would still work even if you differentiate 01 and 001. You just work in a larger group $\endgroup$
    – Marc Ilunga
    Mar 29, 2022 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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