2
$\begingroup$

Sometimes, we use $1$ to represent "succeed". In CPA, if the adversary guesses $b'=b$ outputs $1$. But I am confusing about the meanings of the following $1$.

  • Take the DDH for example, $$|\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\le\operatorname{negl}(n)|$$ where n is security parameter.

Does $1$ mean succeed or output the same thing?

$\endgroup$
  • $\begingroup$ In this specific case it could mean "the given tuple is a DH tuple". $\endgroup$ – SEJPM Dec 5 '18 at 17:34
  • $\begingroup$ If we consider the adversary A as a distinguisher. The above inequation means that the distinguisher cannot distinguish g^{ab} and g^c. In this setting, what does 1 mean? Just out the same thing or not? $\endgroup$ – Qiang Wang Dec 5 '18 at 17:42
  • $\begingroup$ I do not change the question. Because the adversary $\cal{A}$ can be a distinguisher in the simulation. I want to understand this in the simulation. $\endgroup$ – Qiang Wang Dec 5 '18 at 18:22
2
$\begingroup$

If we write $$\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\le\operatorname{negl}(n)$$ without an absolute value, meaning that the (distinguisher) algorithm $\mathcal A$ is not good enough to breach security, it is implicit that $\mathcal A$ outputs $1$ more likely when it has recognized something special. That something special is the condition that should be near impossible to recognize for security to hold. In the context, that special thing ideally is: for input $(g,g^a,g^b,g^c)$, the condition $g^c=g^{ab}$ holds. But an algorithm that does not exactly recognize that condition is still a valid distinguisher (breaking security) if it manages to make the overall condition false.


It is often written $$\big|\,\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\,\big|\le\operatorname{negl}(n)$$ and, thanks to the absolute value, it becomes immaterial if the special condition tends to make $\mathcal A$ output of $1$ or $0$, because $$\big|\,(1-p)-(1-p')\,\big|\ =\ \big|\,p-p'\,\big|$$ Now, the only thing that matters is that the output of $\mathcal A$ has a significantly different mean over the inputs of the form $(g,g^a,g^b,g^{ab})$ than it has over the inputs of the form $(g,g^a,g^b,g^{ab})$.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ The algorithm has recognized something special. the special thing can be a string or other number, but they must be same. Right? $\endgroup$ – Qiang Wang Dec 5 '18 at 18:17
  • 2
    $\begingroup$ @QiangWang, the algorithm $A$ has 4 arguments as an input, right? In the first case, we call $A$ with values $g, g^a, g^b, g^{ab}$. But those values are some integer numbers, so it's not obvious that they are bound with this specific relation (so that they are exponents of some values). This is exactly the problem which $A$ tries to solve: recognize if these 4 values are related in this specific way, or not. So, $A$ returns 0 (No, or False), or 1 (Yes, of True), depending on its decision. I hope this clarifies something fo you $\endgroup$ – Mikhail Koipish Dec 5 '18 at 18:37
  • $\begingroup$ so you're wrong that 1 represents "succeed". It represents the return value of the algorithm $\endgroup$ – Mikhail Koipish Dec 5 '18 at 18:39

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.