3
$\begingroup$

How can you encrypt $n$ messages with the same key, and have the same theoretical security you'd have encrypting a single message with a one time pad? For example, how can you encrypt two messages with the same key, and have that same theoretical security?

I think for $n=2$, something like $E(M) = (K_1M + K_0) \mod p$ should work, for prime p, $0 \leq M \leq p-1$, and each part of the key $K_i$ randomly chosen so $0 \leq K_0 \leq p-1$ and $1 \leq K_1 \leq p-1$.

This seems like the sort of thing that may have already been worked out or proved impossible, but I couldn't find it.

$\endgroup$
4
  • $\begingroup$ Where have your multiple messages gone in the description of your algorithm? In general, anything trying to perform an algorithmic solution to reuse keys for a random pad fails. $\endgroup$
    – Maarten Bodewes
    Aug 15 '15 at 15:50
  • $\begingroup$ @MaartenBodewes say your messages are $M_1$ and $M_2$. Then the encrypted messages are $E(M_1) = (K_1M_1 + K_0) mod (p-1)$ and $E(M_2) = (K_1M_2 + K_0) mod (p-1)$ $\endgroup$
    – user26167
    Aug 15 '15 at 15:57
  • $\begingroup$ Actually, in your example, $E(M) = (K_1M + K_0) \bmod p-1$, then either you leak $M_0 - M_1 \bmod 2$, or you can't uniquely decrypt. If $K_1$ is even, you can't uniquely decrypt (because $p-1$ is even). If $K_1$ is odd, then $E(M_0) - E(M_1) \equiv M_0 - M_1 \pmod{2}$ (again, because $p-1$ is even). Try $E(M) = (K_1M + K_0) \bmod p$ instead $\endgroup$
    – poncho
    Aug 15 '15 at 17:16
  • $\begingroup$ @poncho thanks, you're right, and I think $M$ and $K_0$ should range from $0$ to $p-1$ so I'll change that too. $\endgroup$
    – user26167
    Aug 15 '15 at 19:34
4
$\begingroup$

What you need for this is something called an $n$-wise independent hash function (like "pairwise independent" but $n$ instead). Such a hash function has the property that when applied to at most $n$ different inputs, its outputs are completely random. These can be constructed efficiently; e.g., a random polynomial of the appropriate degree works. What you actually defined with $E$ in your question is a linear polynomial with random coefficients and this is pairwise independent. There has been significant research on how to construct these, how to construct such functions that are almost independent, and so on.

Having said all of the above, you don't really gain anything cryptographically with this, since the size of the key still needs to be larger than the size of everything you compute. So, you may as well use the one-time pad each time. However, there are other applications that such functions are useful (mainly in complexity, but they are also sometimes used in crypto).

$\endgroup$
1
  • $\begingroup$ It's also worth mentioning that even using such functions in this way, encrypting the same message twice yields identical ciphertexts -- so the attacker sees when messages are the same. Avoiding this problem requires an encryption algorithm that is not deterministic, e.g., one that's stateful or randomized. For example, a stateful algorithm can just throw out the part of the key it's already used, and use a fresh part for each successive message. $\endgroup$ Aug 17 '15 at 0:46
2
$\begingroup$

Perfect secrecy requires that your key be as long as the plaintext you are encrypting. If you want to use the same key to encrypt multiple messages, you can use each part of the key once as a one-time pad.


Your idea (assuming you fix the issue raised by poncho) seems to be just a more complicated way to achieve the same thing. If you remove the multiplication by a key part, you are back to adding a one-time pad, which is a part of the key used only once.

Whether you add a one-time pad to the message modulo the message space or XOR/add a character a time does not matter.

$\endgroup$
2
  • $\begingroup$ Yes, you'd need a key as long as all the messages put together. Using parts of the key as one time pads would work in some cases, but I had in mind that you could encrypt a PIN code and store the encrypted result on a remote computer. If you get the same PIN again it needs to encrypt to the same ciphertext. But if a single wrong PIN is put in, the remote computer is prevented from using the two encrypted PINs to find a relationship between the plain text PINs. Or if your device didn't have any writable persistent storage and couldn't keep track of which parts of the key had been used. $\endgroup$
    – user26167
    Aug 15 '15 at 15:37
  • $\begingroup$ @user26167, you can't have perfect secrecy if multiple identical messages must encrypt to the same ciphertext. I would recommend just using convergent encryption in that case, perfect secrecy isn't normally needed or practical. $\endgroup$
    – otus
    Aug 15 '15 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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