Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

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

I am read this paragraph and I have a doubt.

"An adversary to PKC $\Pi$ is given by two probabilistic polynomial time algorithms, $A = (A1; A2)$. In the first stage, the "find" stage, the adversary analyzes the public key and tries to determine which plaintexts, when encrypted, are vulnerable to attack. This is the job of $A1$. In the second stage, the "guess" stage, the adversary $(A2)$ will be presented with a challenge ciphertext $y$, an encryption of one of the plaintexts he found in stage 1."

What is the "new" in use the challenge ciphertext $y$ if I know the its plaintext? How I will be able to make attack?

share|improve this question
Could you please provide a bit more context to your question? In particular, where did you see this paragraph, and what security property is it supposed to define? I can make some guesses based on what you wrote, but it would be nice to be able to tell for sure. – Ilmari Karonen Apr 30 '13 at 4:22
What "new"? The word "new" never appears in the quote you provided, so I'm not sure where you got that from or why you are asking. Perhaps you might want to spell out any assumptions you are making in more detail. Here's a hint: Ask yourself, why would you expect the ciphertext or its corresponding plaintext to be new? Answer: The plaintext that's encrypted isn't necessarily new; it's not known to the attacker (it might be one of multiple possibilities, and the attacker doesn't know which), but that doesn't mean it's new. It can be unknown without being new. – D.W. Apr 30 '13 at 6:59

It's hard to be sure without seeing a bit more context, but the paragraph you quoted looks like it's part of a definition of IND-CPA security (ciphertext indistinguishability under a chosen-plaintext attack) for public-key ciphers.

Here's the corresponding definition from the Wikipedia article I linked to above:

"For a probabilistic asymmetric key encryption algorithm, indistinguishability under chosen plaintext attack (IND-CPA) is defined by the following game between an adversary and a challenger. For schemes based on computational security, the adversary is modeled by a probabilistic polynomial time Turing machine, meaning that it must complete the game and output a guess within a polynomial number of time steps. In this definition $E(PK, M)$ represents the encryption of a message $M$ under the key $PK$:

  1. The challenger generates a key pair $PK, SK$ based on some security parameter $k$ (e.g., a key size in bits), and publishes $PK$ to the adversary. The challenger retains $SK$.
  2. The adversary may perform a polynomially bounded number of encryptions or other operations.
  3. Eventually, the adversary submits two distinct chosen plaintexts $M_0, M_1$ to the challenger.
  4. The challenger selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge ciphertext $C = E(PK, M_b)$ back to the adversary.
  5. The adversary is free to perform any number of additional computations or encryptions. Finally, it outputs a guess for the value of $b$.

A cryptosystem is indistinguishable under chosen plaintext attack if every probabilistic polynomial time adversary has only a negligible "advantage" over random guessing. An adversary is said to have a negligible "advantage" if it wins the above game with probability $\tfrac12 + \epsilon(k)$, where $\epsilon(k)$ is a negligible function in the security parameter $k$, that is for every (nonzero) polynomial function $\mathrm{poly}()$ there exists $k_0$ such that $|\epsilon(k)| < \left|\tfrac{1}{\mathrm{poly}(k)}\right|$ for all $k > k_0$."

Unlike the definition you quoted, the Wikipedia version doesn't explicitly represent the adversary as two polynomial-time algorithms $A1$ and $A2$, but it does note that the total computational time used by the adversary must be polynomial, which amounts to the same thing.

What the Wikipedia version does note explicitly, however, is that the adversary is supposed to choose (at least) two potentially vulnerable plaintexts, of which the challenger then encrypts one and sends it back to the adversary, who then tries to guess which of the plaintexts it corresponds to. The Wikipedia article also notes that the reason this isn't trivial is because the same plaintext can encrypt to many different ciphertexts:

"Although the adversary knows $M_0, M_1$ and $PK$, the probabilistic nature of $E$ means that the encryption of $M_b$ will be only one of many valid ciphertexts, and therefore encrypting $M_0, M_1$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary."

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.