Join Log in
Score:1
eternalmothra avatar Crypto

What exactly is a game, challenger, and adversary?

cn flag
eternalmothra

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?
81
0 + 0
Score:2
avatar Crypto
us flag
Mikero

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.

Are adversaries and challengers computers

I think that a computer is a device that can do what a program tells it to do. Adversaries and challengers are computers that run specific programs -- the challenger for a particular security game runs a fixed program but we consider an adversary running an arbitrary program.

What is $n$ supposed to be a parameter of?

Being a parameter means: it's a value that is chosen externally, and is provided publicly to both the challenger and adversary. The security parameter is given as input to all algorithms in the cryptographic scheme (although this input is often not written explicitly). Usually the security parameter specifies the size of the keys, etc.

The security parameter is like a knob that you can turn. A higher value makes it a little more expensive to run the cryptographic algorithms, but a lot more expensive to break it. Turn the knob until you are comfortable with how hard it is to break the scheme, and that's the value that you use when running this scheme.

0 + 0
eternalmothra avatar
cn flag
eternalmothra
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.