Questions tagged [game]
The game tag has no usage guidance.
16
questions
4
votes
1
answer
192
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 ...
- 215
1
vote
0
answers
56
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 ...
- 11
3
votes
0
answers
64
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 ...
- 283
0
votes
1
answer
63
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$ ...
- 239
4
votes
1
answer
81
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 ...
- 335
1
vote
1
answer
220
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 ...
- 115
0
votes
2
answers
56
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 ...
- 29
1
vote
1
answer
498
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 ...
- 395
2
votes
1
answer
129
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 ...
- 161
4
votes
1
answer
159
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" ...
- 161
2
votes
0
answers
66
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$ ...
- 395
1
vote
0
answers
304
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 ...
- 21
0
votes
0
answers
35
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 ...
- 21
1
vote
1
answer
334
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 ...
- 878
1
vote
0
answers
65
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 ...
- 279
0
votes
0
answers
87
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 ...
- 1,066