1
$\begingroup$

Choose randomly $P\in G_1, (s,a \in Z_q)$.

let the attackers know $a,P$ and keep $s$ as secret. Also the following is given. $$sP,(a+s)^{-1}P$$

Individually,

From $sP$, trying to reveal ($s$) will be discrete logarithm problem.

However, I don't know (computational assumption) how to prove $s$ value cannot be revealed from $(a+s)^{-1}P$.

Moreover, are there any computation assumption to prove the secrecy of $s$ value from both $sP,(a+s)^{-1}P$ instead of individually.

As there is no pairing operation, BDH, xBDH, wBDH cannot be used here.

| improve this question | | | | |
$\endgroup$
1
$\begingroup$

Let $\mathbb{G}$ be a (multiplicatively written) group of order $q$ and let $g$ be a generator of $\mathbb{G}$. The $r$-SDH assumption (Strong Diffie-Hellman) [BB08] states that given $$ g,g^x, g^{x^2}, \dots, g^{x^r} $$ as input, it is hard to compute a pair $(a, g^{1/(x+a)})$ for some $a \in \mathbb{Z}_q$.

Writing group $\mathbb{G}$ additively and letting $P$ be a generator of $\mathbb{G}$, the $r$-SDH assumption is: Given $$ P, sP, s^2P, \dots, s^rP $$ as input, it is hard to compute a pair $(a, 1/(s+a)P)$ for some $a \in \mathbb{Z}_q$.

Your assumption is related to the $1$-SDH assumption in a cyclic subgroup of points on an elliptic curve over a finite field. It is however weaker as the attacker is given the value of $a$ (in the SDH assumption, the attacker is free to choose the value of $a$).


[BB08] D. Boneh and X. Boyen, Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups, Journal of Cryptology, 21(2), pp. 149-177, 2008.

| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ How about using $G$ as additive group of order $q$? Can I use same assumption? $\endgroup$ – myat Nov 7 '16 at 5:25
  • $\begingroup$ @myat: I added a description with additive notation. $\endgroup$ – user94293 Nov 7 '16 at 5:32
  • $\begingroup$ it is hard to compute a pair $(a, g^{1/(x+a)})$ for some $a \in \mathbb{Z}_q$. In my case, as $a $ is known, can I use it? $\endgroup$ – myat Nov 7 '16 at 5:32
  • $\begingroup$ In your recommended paper, $1/(x+a)$ value is computed using modulo p. But, here, no modulo value is used. Will this affect the security ? $\endgroup$ – myat Nov 7 '16 at 5:42
  • $\begingroup$ @myat: In my answer, since $\mathbb{G}$ has order $q$, the value of $1/(x+a)$ is defined modulo $q$. The $r$-SDH problem is to find a pair $(a, [(s+a)^{-1} \bmod q]P)$. $\endgroup$ – user94293 Nov 7 '16 at 5:48

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.