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

On page 11, definition 2 of "Simultaneous Hardcore Bits and Cryptography Against Memory Attacks", the paper outlines the following steps

  1. (PK,SK) public key and secret key are generated by defender using Gen($1^n$).
  2. Adversary $A1$ generates $m_0$ and $m_1$ and a $state$ using PK.
  3. Defender randomly selects $b$ and encrypts $m_b$ invoking $ENC_{PK}(m_b) = y$, and given to $A2$.
  4. Using challenge $y$ and $state$ generated by $A1$, adversary $A2$ guesses if $m_0$ or $m_1$ was encrypted in step 3.
  5. The adversaries win if the guess is right.

My question:

In step 2, the $A1$ generates the two messages $m_0$ $m_1$ using the public key PK, but doesn't this make the game trivial for the adversary to win after seeing the challenge ciphertext in step 3? Couldn't the adversary just use PK to encrypt $m_0$ and $m_1$, and see which one matches the challenge ciphertext?
I feel like I'm a key point and would appreciate if someone could clarify what the paper is saying.

share|improve this question
Your title is completely different from the question in your post's body. $\;$ – Ricky Demer Sep 20 '13 at 23:38
you'd better reedit your question – T.B Sep 21 '13 at 2:02
@Alex : $\:$ Why "reedit" rather than "edit"? $\;\;\;$ – Ricky Demer Sep 21 '13 at 2:17
Sorry guys - I made an edit. But I am also curious to know what "state" is. – user1068636 Sep 21 '13 at 2:44
So far my understanding is the $A_1$ has access to the oracle but $A_2$ does not. $A_1$ also has access to the public key PK but strangely enough $A_2$ does not. It appears like $A_2$ only has access to the mystery "state" variable. – user1068636 Sep 21 '13 at 3:16
up vote 1 down vote accepted

The game is not trivial for the adversary to win because the author is suppressing $ENC\hspace{.02 in}$'s randomness, which makes it so for most PKE systems it will be the case that $\; \operatorname{Prob}\left(ENC_{PK}(m) = ENC_{PK}(m)\right)$
is exponentially small, in which case the probability that either $ENC_{PK}(m_{\hspace{.02 in}0})$
or $ENC_{PK}(m_1)$ matches the challenge ciphertext is also exponentially small.

"state" is the contents of $A$'s memory locations during step 3,
when there's just an $A$ rather than an $A1$ and an $A2$.

share|improve this answer
Perfect answer. This is exactly what I was looking for. Thanks Ricky – user1068636 Sep 21 '13 at 3:36

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.