Score:5

Crypto

Perfectly secret variable one-time pad

Lug322d

7/28/23, 10:13 PM

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?

125

0 + 0

one-time-pad

kodlu

7/28/23, 11:51 PM

your plaintexts are the same size, no?

Lug322d

7/29/23, 12:40 AM

@kodlu No, they are at most size $\ell$.

Paul Uszak

7/29/23, 1:43 AM

Hi Lug and welcome :-) Review the question please as it's confusing. What exactly are you asking? We love one time pads here though...

Lug322d

7/29/23, 2:41 AM

Thanks @PaulUszak! In simple words, I'm trying to form a variable length one-time pad that it's perfectly secret.

Paul Uszak

7/29/23, 3:00 AM

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?

Lug322d

7/29/23, 3:38 AM

The definition for what I am talking is in the Example 2.2 of this book: https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf. And yes, they are one bit, though $m_2$ should be two bits.

Paul Uszak

7/29/23, 4:37 AM

Apologies. I didn't understand.

Maeher

7/29/23, 7:13 AM

Decrease the maximum message length by one and use one-and-zeroes padding. I.e. always add a single 1 bit and fill up the rest with 0 bits. To unpad remove all trailing zeroes and the first 1 from the end.

Lug322d

7/29/23, 7:49 PM

@Maeher But then it will no longer be an OTP. An attacker can simply remove those bits as well and they got variable-length OTP.

user253751

7/29/23, 7:58 PM

You assume that |E(K,m1)| = 1. Is this necessary?

Maeher

7/29/23, 8:30 PM

@Lug322d no they cannot. Obviously you pad *before* you encrypt.

Score:2

Crypto

Marc Ilunga

7/29/23, 7:19 AM

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

0 + 0

Lug322d

7/29/23, 7:33 PM

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.

Marc Ilunga

7/29/23, 8:15 PM

@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?

Lug322d

7/29/23, 9:41 PM

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.

Marc Ilunga

7/29/23, 9:47 PM

The second method would still work even if you differentiate 01 and 001. You just work in a larger group

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Perfectly secret variable one-time pad

TH: แผ่นแปรผันแบบใช้ครั้งเดียวที่เป็นความลับอย่างสมบูรณ์แบบ

RO: Pad unic variabil perfect secret

RU: Совершенно секретный сменный одноразовый блокнот

VI: Bàn phím một lần biến hoàn toàn bí mật

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.