1
$\begingroup$

I am trying to prove that changing an input in a security game from a randomly permuted set to a set that is permuted using a pseudorandom permutation (PRP) results in a negligible distinguishing advantage between the two games. Does anyone know of any good examples in the literature of this kind of game hop. I have already read through the Shoup 2006 paper on games.

$\endgroup$
5
  • $\begingroup$ What do you mean by "changing an input"? $\endgroup$
    – fkraiem
    Aug 5 '15 at 11:52
  • $\begingroup$ Oh, i realise this is not clear now! I meant changing an adversaries input so if you have Game 1 that uses a random permutation in Game 2 this input is changed and the game is given a PRP instead. An adversary has to try and distinguish between outputs from each of these games. $\endgroup$
    – henry
    Aug 5 '15 at 12:34
  • $\begingroup$ i just edited the question, hopefully this makes more sense $\endgroup$
    – henry
    Aug 5 '15 at 12:36
  • $\begingroup$ The Shoup paper is probably the best reference I can think of. Otherwise I would just recommend reading proofs that uses this technique, to get a feel of it. It is very commonly used and often called a "hybrid argument". $\endgroup$
    – Guut Boy
    Aug 5 '15 at 14:14
  • $\begingroup$ As to your proof, as I recall it is a matter of definition that any PRP seeded with randomness of length proportional to the security parameter should be at least computationally indistinguishable from from a true random permutation. So this should be a pretty easy proof (however, please check the definitions yourself, dont just take my word for it). $\endgroup$
    – Guut Boy
    Aug 5 '15 at 14:19
2
$\begingroup$

While I cannot point you to a specific paper that works as a great example for this technique, the idea is quite simple.

Assume two distributions $X,Y$ which have the same support, so random variables distributed according to one of these distributions are drawn from the same set. Now assume you got a probabilistic adversary $A$ that takes as input $misc$ and a value $x$ that drawn according to $X$ and tries to solve some problem. Here $misc$ covers any additional inputs. As $X$ and $Y$ have the same support, we might also chose $x$ from $Y$ -- $A$ should at least accept such $x$ as input.

Let's switch to the games. Assume you got two games. In both you generate $misc$ the same way. But the games differ in how $x$ is chosen. In game 1 you chose $x$ according to $X$, in game 2 you chose $x$ according to $Y$. You might already see that if the success probability of $A$ differs, depending on if he plays in game 1 or in game 2, we can use this to distinguish the two cases, i.e. we can use this to decide from which distribution $x$ was chosen.

Say $A$ wins in game 1 with higher success probability than in game 2. Then we can built a distinguisher $D$ that takes a value $x$ and outputs 1 if $x$ was chosen from $X$ and $0$ if it was chosen from $Y$. $D$ simply runs $A(misc,x)$ and outputs 1 if $A$ succeeds. $D$ will distinguish the two cases exactly with $A$'s difference in success probability depending on which game he plays.

Hence, we can argue that if $X$ cannot be distinguished from $Y$ with probability greater $\epsilon$, the difference in $A$'s success probability between game 1 and game 2 must be limited by $\epsilon$.

That's how one game hop works. You can extend this arbitrarily. The important thing is that between two consecutive games you must only change the distribution of one of $A$'s inputs.

$\endgroup$
1
  • $\begingroup$ This is great, thank you for making it clear and simple :) $\endgroup$
    – henry
    Aug 13 '15 at 11:49
0
$\begingroup$

There is a similar approach to prove the semantic security of real world one time pad, using a pseudorandom generator. Basically the idea is to correlate the success probabilities of an alleged hard problem with the success probabilities of an attacker for your scheme. In the case of RWOTP once the simulator chooses a pseudorandom generator to pick up its key in order to reply to encryption queries by the attacker ($Pr[\mathcal{A}^{PRG}]$) and in the other case it chooses a uniform key($Pr[\mathcal{A}^{r\gets R}]$). The distinguishing probabilities of those two by definition of PRG is negligible: $Pr[\mathcal{A}^{PRG}]$ - $Pr[\mathcal{A}^{r\gets R}]=\epsilon$. But $Pr[\mathcal{A}^{r\gets R}]=\frac{1}{2}$ since $r$ is uniformly random. As such $Pr[\mathcal{A}^{PRG}]=\frac{1}{2}+\epsilon$. But $Pr[\mathcal{A}^{PRG}]$ equals the success probabilities of $\mathcal{A}$ which tries to break RWOTP.

Similar answer here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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