Can a cryptosystem be unconditional secure if the same key $k \in \mathcal K$ is used for more than one encryption ?

I know that the one-time-pad doesn't have perfect secrecy and doesn't provide unconditional security provided the same key is used for more than one encryption.

Is this general for all encryption schemes, that unconditional security is unachieveable given that a key is used repeatedly ?

  • $\begingroup$ It's certainly necessary that the size of the key must be at least the total size of the messages. $\endgroup$ – CodesInChaos Dec 21 '14 at 21:40
  • $\begingroup$ You can combine shamir's secret sharing with a one-time-pad to arrive at a scheme that's perfectly secure as long as you're able to generate a unique nonce for each message. Unfortunately the running time is quadratic in the maximum number of messages you can send. This does not free you from the above size limitation, but it doesn't require you to keep track of which parts of the key you already used, $\endgroup$ – CodesInChaos Dec 21 '14 at 22:50

It is easy to construct an unconditionally secure encryption scheme where the key is reused to encrypt multiple messages. Simply take any unconditionally secure encryption scheme that can be reused $1$ time and then to generate keys sample $m$ keys of this original scheme (e.g., $m$ OTP keys). Now you can use these $m$ keys to encrypt $m$ messages and obviously the security is still that of the original scheme.

Of course, you may argue that this is 'cheating', because now we have an encryption scheme with keys of size $n\times m$, where $n$ is the size of a message. However, this cannot be helped. For the scheme to be unconditionally secure the key must be at least as long as the total amount of bits we can communicate using it. To see why this is the case consider that to have perfect secrecy given a series of ciphertexts any series of messages must be equally likely. This means that for each series of message bits (combining all the messages sent) we need one distinct key, i.e., the key must be at least the size of the total amount of bits encrypted.

  • $\begingroup$ This isn't actually unconditionally secure unless you have state. Without a state, you may end up reusing key material. $\endgroup$ – K.G. Dec 21 '14 at 21:34

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.