# Computational Assumption For the extended discrete logarithm

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.

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.

• How about using $G$ as additive group of order $q$? Can I use same assumption? – myat Nov 7 '16 at 5:25
• @myat: I added a description with additive notation. – user94293 Nov 7 '16 at 5:32
• 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? – myat Nov 7 '16 at 5:32
• 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 ? – myat Nov 7 '16 at 5:42
• @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)$. – user94293 Nov 7 '16 at 5:48