# Perfect secrecy over Stirling numbers

For all $c_0\leftarrow m_0 \oplus k$ there exists a $k'$ such that $c_1 \leftarrow m_1 \oplus k'$, where $m_0 \neq m_1$ and $c_0 = c_1$.

Assuming a truly random $k$, the first assignment is a one-time pad. If we were to repeat the process over all $m \in M$, we would create a Stirling set of the first kind.

To use better notation, each key $k_n$ can be given by $G(k_{n-1},m_{n-1})$ where $k_0$ is a perfectly random bitstream.

The scheme would be a bit impractical, but let's not focus on that initially. Since all $c \in C$ are exactly the same, and assuming that no two $m$s are the same, is it safe to claim that the above scheme is perfectly secure?

Subquestion: Is $k'$ still perfectly random?

To clarify: This construction is completely useless. I thought it would be fun to come up with a OTP variation which allows key reuse, not necessarily one that would be of any practical value.

• The two questions you ask are equivalent (I think). You might be able to prove $k'$ is perfectly random by proving inductively that the min-entropy of successive $k_n$ does not change. Nov 20, 2013 at 0:14
• But my information theory knowledge is minimal, that's just a first guess. Nov 20, 2013 at 0:17
• That's what I thought but decided to put it in just in case.
– rath
Nov 20, 2013 at 0:17

Yes, you're correct in that, given a sequence of messages $m_0, m_1, m_2, \dotsc$ and a fixed ciphertext $c$ (assumed to be all of the same length), we can easily calculate a sequence of keys $k_i = c \oplus m_i$ such that $k_i \oplus m_i = c$.
However, I don't see any way to get a useful cryptosystem out of this. If you don't transmit the keys $k_i$ to the recipient, there's no way for them to recover the messages $m_i$ just from $c$; indeed, that would be clearly absurd, since $c$ may be chosen to be completely random and independent of all $m_i$. Conversely, if you do transmit the keys $k_i$, then the system is easily broken by an adversary who intercepts the "keys" — it's basically just a many-time pad.
Also note that you can't transmit the keys in advance, since, once $c$ is fixed, each key $k_i$ will depend on the corresponding message $m_i$. So, unlike a traditional one-time pad, your scheme isn't even good for the "have secure channel now, need to communicate securely later" scenario.
• Ps. Also, yes, if $k$ is uniformly distributed over $\{0,1\}^n$ (i.e. "perfectly random"), then $k' = c_1 \oplus m_1$ $= k \oplus m_0 \oplus m_1$ (where $m_0, m_1 \in \{0,1\}^n$) is also uniformly distributed. This follows easily from the observation that the map $x \mapsto x \oplus m_0 \oplus m_1$ is invertible (and, in fact, its own inverse) on $\{0,1\}^n$. Dec 7, 2013 at 3:23