1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – pg1989
    Nov 20, 2013 at 0:14
  • $\begingroup$ But my information theory knowledge is minimal, that's just a first guess. $\endgroup$
    – pg1989
    Nov 20, 2013 at 0:17
  • $\begingroup$ That's what I thought but decided to put it in just in case. $\endgroup$
    – rath
    Nov 20, 2013 at 0:17

1 Answer 1

Reset to default
0
$\begingroup$

What, exactly, are your trying to accomplish with this construction?

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Ilmari Karonen
    Dec 7, 2013 at 3:23

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.