4
$\begingroup$

Suppose there is a cyclic group $\mathbb{G}$ of prime order $q$ of elements in $Z^{∗}_p$ with a generator $g$ and values $a,b,c,d \in Z_q$.

There is also an equation $g^{ab} = g^{cd}$, where $a,b,c$ are known, so we can compute $d$. Also we know, that $a$ and $c$ are $x$-bits and $b$ is $y$-bits (or alternatively less than some value $v$).

Can it be claimed that $d$ is indistinguishable form $b$ if both $a,c$ are outputs of some secure $PRF$? By indistinguishable, I mean you can't say whether $b$ or $d$ were computed in this equation based on values $(a,b,c,d)$.

I've thought sure it's indistinguishable but on second thoughts $b$ has the fixed bit-length. A smaller $d$ can be padded, but what to do with a bigger one? So I'm lost. I would really appreciate any ideas or hints.

UPDATE: I found this answer and tried to mimic the logic. If we apply this bit-size definition for primes to values $a,b,c$, then we have $2^{x-1} \leq a < 2^x$, also $2^{x-1} \leq c < 2^x$ and $2^{y-1} \leq b < 2^y$. Thus, $ 2^{x-1 + y-1 - (x-1)} \leq \frac{ab}{c} < 2^{x + y - x}$, which means $2^{y-1} \leq d < 2^y$. So $d$ is also $y$-bits number. However, a) I'm not sure the def is appliacble here and b) $d$ destribution doesn't reveal that it has been computed and not selected.

$\endgroup$
  • 1
    $\begingroup$ Indistinguishability usually means negligible advantage in the game of deciding $d$ vs. a random. Should we start with a definition? $\endgroup$ – Vadym Fedyukovych Jul 27 '18 at 11:37
  • $\begingroup$ @VadymFedyukovych, well the game is quite simple: upon each adversarial request, the challenger returns new tuple $(a,b,c,d)$, where one of the values $b$ or $d$ (based on the challenger's coin) is selected at random and the other is computed based on the formula above. The goal of the adversary is to guess the coin. The challenger flips the coin once at the beginning of the interaction, the adversary can ask as many queries as he likes. It's not exactly an interactive game you probably have in mind. $\endgroup$ – pintor Jul 27 '18 at 12:19
  • $\begingroup$ so, if $g^{ab}=g^{cd}$, then $d=ac^{-1}b$, right? If $a$ and $c$ are produced by a secure PRF, then the distribution of possible values of $a$ and $c$ are indistiguishable from random, right? So wouldn't $ac^{-1}$ and $ac^{-1}b$ also have a distribution indistinguishable from random? Clearly the distribution of $b$ is distinguishable from random. Shouldn't therefore $b$ be distinguishable from $d$? $\endgroup$ – jadb Jul 27 '18 at 14:58
  • $\begingroup$ @jadb What if $b$ is selected at random too? Intuitively it seems that in such case values are indistinguishable. $\endgroup$ – pintor Aug 13 '18 at 9:34
  • $\begingroup$ @pintor, looking back at my response I did make an assumption in my mind that $|2^x| \approx |p|$ and I generally took indistiguishable to mean indistinguishable within $Z_p$. So let me try again... $a$ and $c$ are indistiguishable from random within the range $(0, 2^x)$, however the value of $ac^{-1}$ could span the entirety of $(0, Z_p)$ (though its inverse is constrained to the smaller of $p$ and $2^{2x}$). $b$ is within the range $(0, 2^y)$. $d$, like $ac^{-1}$ is within the range $(0, p-1)$. If $2^x << p$ then you would have a high probability of distiguishing $b$ from $d$. $\endgroup$ – jadb Aug 13 '18 at 12:02

Your Answer

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

Browse other questions tagged or ask your own question.