I've read Bellare and Rogaway 2004 and Shoup 2004 about game-based cryptography proofs, but I lack precisions about how should be built the "learning" and "challenge" phases, since my games will probably have this structure.

And what are they suppose to provide anyway ? Security against Adaptive adversaries ? The games I have read are like:

  • learning phase: do whatever you're allowed to do
  • challenge phase: submit two challenge sets, read what the oracle send you back and guess which set has been chosen

Yet adaptive adversary should mean (citing wikipedia) ciphertexts may be chosen adaptively before and after a challenge ciphertext is given to the attacker

thanks for explanations and/or links


1 Answer 1


You're confused about a few different things here. Assume that you have some cryptographic concept and you need to write down a definition of security. Such a definition can typically be written down as a game. When you write down your definition, you consider what the adversary should be able to do, i.e. it's while writing down the game that you assume whether you want active adversaries or not. This will be reflected in the operations that you allow the attacker to do, i.e. what the oracles will be.

Once you have written down the games themselves, then you typically prove bounds for an adversary being able to distinguish between the games assuming some bound on the number of oracle queries. At this point you don't distinguish between the type of adversary. The adversary can do anything that the game allows.

As an example, assume you have a security definition where you want the attacker to get access to $n$ ciphertexts corresponding to some plaintexts $p_1,\ldots,p_n$. If you want a non-adaptive adversary, you define your game to contain an oracle that will take as input $n$ plaintexts and which will return $n$ corresponding ciphertexts and allow only one query. If you want an adaptive adversary, then you would provide a single oracle that takes a plaintext and returns a ciphertext, but which allows itself to be queried $n$ times.

You might then wonder where real world computational limits fit in. What you normally prove is that if you can distinguish between two games, then you can construct an algorithm for solving say DDH or CDH. This reduction argument then links distinguishing the two given games to something you assume that can't be done and this will give you an estimate of how hard it should be to distinguish between the original games.

  • $\begingroup$ Ok, so adaptive adversaries can do Oracle calls one after the other instead of all at once. But still, what are the rules for the learning phase / challenge phase construction ? $\endgroup$ Oct 23, 2014 at 8:25
  • $\begingroup$ I'm not sure what you mean by the rules? Coming up with a good definition typically takes experience. You have to think about what an adversary you want to consider can do and then you define a game with oracles that give out precisely the desired information and nothing more or less. $\endgroup$ Oct 23, 2014 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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