Skip to main content

Questions tagged [game]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
45 views

Proof that semantic security implies key-recovery security

I'm trying to prove that semantic security implies key-recovery security. There is already a question that addresses this, but it doesn't explain the setup of the security reduction, which is what I'm ...
cmplx96's user avatar
  • 113
4 votes
1 answer
223 views

Origin of "abort" in cryptography proofs

It's a very standard move in a game-based security proof to have a transition in which we "abort" on some event such as a hash collision; the two games are identical apart from the abort ...
Paul Crowley's user avatar
1 vote
0 answers
71 views

Proving 2-way nesting security

I recently came across the theorem about $n$-way nesting. It states that if $\mathcal{E}=(E, D)$ is semantically secure, then $\mathcal{E}$ is secure for $n$-way nesting. I'm trying to prove the ...
libre's user avatar
  • 11
3 votes
0 answers
99 views

"Simulator Based" vs "Game Based" security proof for a two-party computation protocol

I am trying to find out how to write a security proof for a two-party computation problem. I have read some examples to write simulators like $x_1 ∧ x_2$ problem and the example in Goldreich's book. I ...
m123's user avatar
  • 283
0 votes
1 answer
70 views

Special indistinguishability problem

I need some help for the following simple game: An adversary is given a multiplicative group $\mathbb{G}$ and the 4-tuple $(g_1, g_2, g_3, g_1^a \cdot g_2^b \cdot g_3^c)$ where $g_1$, $g_2$ and $g_3$ ...
Adam54's user avatar
  • 283
4 votes
1 answer
102 views

sUF-CMA security of Lyubashevsky's ID and signature protocol

I have been working on the post-quantum safe ID/signature-schemes of Vadim Lyubashevsky (https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf). I am in particular studying the security ...
Rory's user avatar
  • 335
2 votes
1 answer
298 views

Proving semantic security implies security from key-recovery attack

I am working on problem 2.11 from the book: A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. The problem reads as follows: Problem 2.11: Let $\mathcal{E} = (E, D)$ be a cipher ...
Tom Finet's user avatar
  • 125
0 votes
2 answers
57 views

How to understand "Test() query can only be issued to a fresh session" in game-based security proof?

In game-based security proof for key-exchange protocols, there is a Test query. The Test(U) query typically is only available to the adversary if the attacked instance U is fresh. (U represents either ...
Chandler's user avatar
1 vote
1 answer
763 views

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 ...
eternalmothra's user avatar
2 votes
1 answer
142 views

Hiding/Obscuring position information in a board game (Part 2)

This is basically a follow-up question to Hiding/Obscuring position information in a board game which technically answered the question, but raised some well deserved critique. To quickly summarize ...
fho's user avatar
  • 161
4 votes
1 answer
167 views

Hiding/Obscuring position information in a board game

There has been a question on the BoardGameGeek forums that basically boils down to this: There is a player character on a regular rectangle map at position (px,py). There is one "AI" ...
fho's user avatar
  • 161
2 votes
0 answers
70 views

Does the PRG game allow for bad randomness picks?

In the game-based definition, we say that $G: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^{\ell(n)}$ is a pseudorandom generator if For all ppt distinguishers $D$, there exists a negligible function $\nu$ ...
eternalmothra's user avatar
1 vote
0 answers
357 views

Building an Adversary for a PRF game

Here is the game: How can I make an $\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage $= 1 - 1/(p-1)$ Here is my idea so far: query $2^{-1}$, which when ...
Diego Starr's user avatar
0 votes
0 answers
44 views

How can we prove that the advantage for this hide game for any adversary is equal 0?

Here is the Scheme: Here is the HIDE game: Here is my idea but I am not quite sure. I would appreciate some input. We want to bring advantage = 0 for all adversaries. We can show that advantage = 0 ...
Diego Starr's user avatar
1 vote
1 answer
388 views

How are probabilities combined in the game hopping proof technique?

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup. On pages 9-11, he is ...
tur11ng's user avatar
  • 962
1 vote
0 answers
72 views

Algorithmic game theory and protocol design for communication

There is a field of exchanging information that combines cryptography and game theory. I am interested in understanding this field, but it's a little complex for me. To begin with there is a paper of ...
Hunger Learn's user avatar
0 votes
0 answers
93 views

MAC Security - MAC verification queries

In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that an adversary that is also capable of requesting the challenger for verification queries (in addition to ...
Evgeni Vaknin's user avatar