3
$\begingroup$

Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$.

Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2):

  1. He chooses a random number $r$ from $Z_p$ and calculates $a^r\;mod\;p$ and $b^r\;mod\;p$ and gives these two values to Alice
  2. He chooses two different random numbers $r$ and $r'$ from $Z_p$ and calculates $a^r\;mod\;p$ and $b^{r'}\;mod\;p$ and gives these two values to Alice

Is there any efficient algorithm Alice can use to recognize which step Bob has done?

$\endgroup$
1
  • 3
    $\begingroup$ As Manish pointed out, this appears to be a hard problem (at least, for cryptographically sized groups). If you want it to be an easy problem, you could do the same operation on a pairing-friendly curve; in that case, $r = r'$ can be tested by comparing $e( [r]a, b )$ and $e( a, [r']b )$ $\endgroup$
    – poncho
    Commented Aug 5, 2021 at 12:42

2 Answers 2

3
$\begingroup$

Little here $a$ and $b$ should be selected from $\mathbb{Z}^*_p$ and $r$ between $1$ and $p-1$ exclusive

Looking like this, it seems to relate directly to the DDH problem, at least if there exists some $w$ such that either $a = b^w$ or $b = a^w$. That is if at least one of $a$ or $b$ generates the subgroup containing the other which is a given if $p$ is a safe prime [if both are quadratic residues/non-residues either exists otherwise whichever is a non-residue is a generator], not sure about the other cases. In this case $a, b^{r'}, a^{r}$ make DDH triplet generated from $b$ or $b,a^r,b^{r'}$ make DDH triplet from $a$. In your case whether DDH problem is hard on not depends on the choice of $a$ and $b$. If both $a$ and $b$ generate the same subgroup with a large prime order then DDH problem is thought to be hard in a classical computer. So, there is no known efficient classical algorithm in that case. DDH problem can be solved with significantly higher probability than random guess in many other cases. For instance if both $a$, $b$ are non-residues modulo $p$ and among $a^r, b^{r'}$ one is a quadratic residue and another is a non residue you can tell that one of $r,r'$ is odd and another is even and thus $r \neq r'$.

In your question $a$ and $b$ are generated randomly, so I would say it is distinguishable. Not in all cases but there is advantage in the cases I mentioned earlier which in computer science is considered significant to be considered not indistinguishable

I am not sure about the case in which neither $a$ nor $b$ generates the subgroup containing the other because I cannot think of a way to relate it to DDH, at least not on top of my head. There might be some sub cases with advantage in that condition too

UPDATES: You have stated that you are trying to design a protocol. Firstly, it is not prudent to try so without a deep understanding of cryptography. Assuming that the entire security of the system relies on this, then you should use a $g$ that is used to generate $a$ and $b$ to be some generator of a large prime order subgroup $q$ and choose $r,r'$ between $1$ and $q$ to ensure that DDH problem is conjectured to be hard in classical computers. Or use known non-pairing friendly EC groups where DDH problem is conjectured to be classically hard. But still I don't know details of a protocol. And implementing it still has issues like side-channel attacks etc.

$\endgroup$
5
  • $\begingroup$ you pointed out to a good point. $a$ and $b$ aren't totally random and are generated as follow: $a = g^{xk}\;mod\;p$ and $b=g^k\;mod\;p$. $k$ and $x$ are chosen randomly. I didn't mention that to make the question shorter. I didn't have any idea it is important. $\endgroup$ Commented Aug 5, 2021 at 12:17
  • 2
    $\begingroup$ In this case we can see $b$ as a generator of the group and $a,b^{r'},a^r$ making DDH triplet. As far as I know, the problem is thought to be hard for classical computers if $b$ generates a large prime order subgroup. There are some distinguishing cases otherwise, one being if $b$ is quadratic non residue modulo $p$ and $x$ is odd and only one of $r,r'$ is even, we know that they are not equal as in answer above $\endgroup$ Commented Aug 5, 2021 at 13:46
  • $\begingroup$ Can you tell me where you got the question? Because it is against community policy to answer homework questions more than hints and guides so I might have to delete my answer. It did not seem worded like that so... $\endgroup$ Commented Aug 5, 2021 at 14:08
  • $\begingroup$ It is not my homework. It is just a question that I faced when I was trying to design a protocol. I wanna see if any information is leaked in my protocol or not $\endgroup$ Commented Aug 5, 2021 at 14:29
  • $\begingroup$ If so, read my edits above $\endgroup$ Commented Aug 7, 2021 at 4:05
0
$\begingroup$

If Bob is willing to help Alice recognizing case 1, he could run a Schnorr-like protocol as a prover. He would produce a response treating $r$ as a private key exactly as specified by the protocol. Alice would verify whether this response fits both random numbers, considered as two public keys.

$\endgroup$
4
  • $\begingroup$ No, it isn't the case. actually, Bob prefers that Alice can't recognize. but Alice is curious $\endgroup$ Commented Aug 5, 2021 at 15:09
  • $\begingroup$ It was not OP's question but I just noticed that it suffices that the prover uses Schnorr's protocol to prove that she knows DL of $a^rb^{r'}$ over $ab$ if the verifier can ensure that the prover does not know DL of $a$ over $b$ or vice versa. As a proof $a = b^x$ (according to OP's comment above). Then if the prover knows $c$ s.t. $(ab)^c = a^rb^{r'}$ i.e. $c+cx \equiv xr + r' \pmod q $. If $r \not\equiv r' \pmod q$ then $c \not\equiv r \not\equiv r' \pmod q$ and the prover can calculate $x$. $\endgroup$ Commented Aug 7, 2021 at 4:32
  • $\begingroup$ But it should be done over one prime order subgroup of order $q$ otherwise prover can cheat by using $r' = r+q$ or something if $a$ and $b$ make small order subgroups $\endgroup$ Commented Aug 7, 2021 at 4:35
  • $\begingroup$ *correction for comment above$(ab)^c \equiv a^rb^{r'} \pmod p$, I wrote $=$ instead $\endgroup$ Commented Aug 7, 2021 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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