# What exactly is a game, challenger, and adversary?

Here is my understanding of the concept of security games. I bolded some parts that I am not sure about.

A cryptographic object is formally defined by its algorithms and what security notions it achieves. Such notions capture an adversary’s power and show how the adversary may "break the cryptosystem". "Breaking a cryptosystem" means winning a GAME associated with the cryptosystem’s security. The game (i.e., algorithm) is played between an adversary and a challenger. Both adversary and challenger are computers who run probabilistic algorithms. The probability the adversary wins should be negligible relative to some target probability for the scheme to be secure.

For example, in an encryption scheme, a strong adversary should not be able to distinguish encryptions from each other even if they choose the messages. In other words, an adversary guesses which bit the challenger flipped. The target probability is $$\frac{1}{2}$$, as an adversary can randomly guess which bit was flipped. The adversary must win with probability no more than $$\frac{1}{2} +negl(n)$$, where $$n$$ is security parameter in the scheme.

1. Is a game not an algorithm? If not, then what is it? https://www.shoup.net/papers/games.pdf Shoup says they are probabilistic processes. But is there a difference between probabilistic processes and probabilistic algorithms?
2. Are adversaries and challengers computers? They are doing some computing (even if the process is like a random oracle). Is it correct to say so?
3. What is $$n$$ supposed to be a parameter of?

At the risk of being pedantic and nit-picky (you did ask a question about terminology after all), I propose that you call these objects "interactive programs" rather than algorithms or computers.

Is a game not an algorithm

The challenger and adversary can certainly be described in terms of some programmatic/algorithmic logic. But I think of an algorithm as a non-interactive thing that takes an input, gives an output, and then is done. A cryptographic security game is more interactive than that. There are often several distinct rounds where information is exchanged, and the challenger usually provides a collection of subroutines/oracles that the adversary can call, many times. I think it's important to highlight this interactive nature.

Technically you could identify an interactive program with its "next action function," which is indeed a simple non-interactive algorithm. For example, the challenger is characterized by an algorithm that computes the logic: "if the adversary is making kind of query, then respond with action." In fact this might be how you would choose to define what an interactive program is, in terms of non-interactive algorithms. Apart from such very formal definitions, it is rare to really think & talk about challengers and adversaries in this way, but occasionally it is useful to think of protocol specifications in this way.

What is $$n$$ supposed to be a parameter of?
• This is very helpful! I did want to be pedantic (well, pedagogic) here. The only thing I am not sure of: is $n$ actually a security parameter, or is it input size? The distinction might be you need X length keys to get Y bits of security, for example. Commented Jan 26, 2022 at 20:37