Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If we're considering Chosen-Plaintext Attack setting, then the adversary has access to the Encryption Oracle right, and we know that OTP is only considered secure if we use the key only once. How would we ensure that the adversary uses the key only once?

Or would it not matter how the adversary uses the encryption oracle since in the end they will be presented with a ciphertext corresponding to a plaintext not queried and the adversary would not be able to decrypt it because they don't know the key. Making it CPA-Secure. Is this second train of thought the correct way to think about OTP in CPA setting?

Thank you!

share|improve this question
I'm not sure the idea of a CPA even applies to an OTP. – cpast May 16 '15 at 20:20

Note: In this answer, I stick to a definition of the One Time Pad where the random pad is used only One Time; at least, I've the name of it as support! Otherwise, it is well known that the OTP encryption scheme consisting of XOR with a repeated key is insecure by even the weakest standard (unknown plaintext with redundancy).

INDistinguishability under Chosen Plaintext Attack applies to encryption schemes; there's no way the OTP can be made to match the definition of an encryption scheme, thus the formal definition of IND-CPA does not apply to the OTP.

Specifically, the OTP does not fit definition 3.7 in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, first edition (CRC Press, 2008):

A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms ($\text{Gen}$, $\text{Enc}$, $\text{Dec}$) such that: (..)

  1. The key-generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k$; (..)
  2. The encryption algorithm $\text{Enc}$ takes as input a key $k$ and a plaintext message $m\in\{0,1\}^*$, and outputs a ciphertext $c$. (..)
  3. The decryption algorithm $\text{Dec}$ takes as input a key $k$ and a ciphertext $c$, and outputs a message $m$. (..)

It is required that for every $n$, every key $k$ output by $\text{Gen}(1^n)$, and every $m\in\{0,1\}^*$, it holds that $\text{Dec}_k(\text{Enc}_k(m))=m$.

where $\{0,1\}^*$ is the set of all (finite-length) binary strings.

There's no way the OTP can fit this framework:

  • If we try to assimilate the random pad and the key, we hit the problem that in the above definition the same $k$ can be used for several messages (and further that some messages can be larger than the key, but that's secondary); the OTP does not allow that (due to the One Time requirement of OTP).

  • If we try to fit the random pad into $\text{Enc}$, and still keep the ciphertext as it is in the OTP (including, of the same size as the message), then we have no way to build a working $\text{Dec}$.

Note: some practical encryption schemes use message spaces deviating from $\{0,1\}^*$, like the set of all bytestrings up to some size, or even a fixed-size bytestring, perhaps even shorter than the key (which is common in block ciphers); and it is accepted to twist the definition of an encryption scheme to allow that. However it is an essential point of any encryption scheme that the total size of plaintext enciphered with a given key is allowed to increase significantly above the size of the key; again, the OTP does not allow that.

The OTP is secure under Choosen-Plaintext Attack for some definition of that; like allowing the adversary to choose some of the plaintext and defining success as the ability to guess other plaintext with odds better than random, in a setup meeting the OTP defining properties that the pad is perfectly random, unknown to the adversary, and never reused. However that custom definition, adapted to something not an encryption-scheme, is different from that of IND-CPA in modern cryptography.

Addition following a (now gone) comment: RSA encryption with random padding is an example of asymmetric encryption scheme that is (believed) IND-CPA (however with a restriction that any individual message must be smaller than the key, which is worked around in practice with hybrid encryption); see RSASSA-PKCS1-V1_5 or PKCS#1 RSASSA-PSS.

share|improve this answer
As I see it, the only problem of the OTP in respect to the formal definition of encryption schemes is that the message space is not $\{0,1\}^*$. If you relax the definition to allow encryption schemes with a different message space, then the OTP is one, and the concept of CPA-security applies. What's a "cipher"? – fkraiem May 17 '15 at 9:07
@fkraiem: even if we restrict the message space of a cipher to $\{0,1\}^{|k|}$, the OTP does not fit that definition of a cipher, because a cipher must allow encryption of multiple messages with the same key, and the OTP does not. – fgrieu May 17 '15 at 9:47
@fgrieu I'm not sure what you mean by "cipher"? Nevertheless, OTP can be used for the encryption of multiple messages with the same key. However, it would not be secure. You can liken the way OTP is used (different key each time) to the way certain modes of encryption, such as Output Feedback Mode, work. Output Feedback Mode is CPA-Secure and thus the logic should extend to OTP. Don't think about the OTP as using a different key each time, think of it as using a different section of the long key each time (Basically synchronized encryption where state is maintained). – Gordon May 17 '15 at 9:57
In summary, OTP under multiple-key usage is CPA-Secure, while OTP under same-key usage is not. However, the property of being CPA-Secure does apply to OTP (as well as any other encryption scheme) – Gordon May 17 '15 at 10:01
@Gordon: I (now) see what you mean. If we consider that the OTP allows key reuse then, yes, it is a cipher (perhaps, by a variation of the above definition where the plaintext size is restricted), but not a secure one under even the weakest definition of security (unknown plaintext with known redundancy). On the other hand, two of out three words in the name One TIme Pad are there to emphasize that the pad/key can not be reused, so this twists the definition of OTP. – fgrieu May 17 '15 at 10:03

Ciphertext indistinguishability under CPA is equivalent to semantic security. Semantic security is the computational complexity analogue to Shannon's concept of perfect secrecy. OTP is perfectly secure, therefor is CPA secure.

Under CPA, the adversary will be presented with a ciphertext corresponding to a plaintext queried (the adversary chose the plaintext) but will not be able to distinguish it from the ciphertext corresponding to other plaintext.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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