# Tag Info

Actually, the algorithm is distinguishable. Let us assume that the attacker has two input, output pairs $(x, fx), (y, fy)$. Then, he can test whether $fy^x = fx^y$. If $fx = g^{sk\cdot x}$ and $fy = g^{sk\cdot y}$, this test will succeed, as $fy^x = g^{sk\cdot y \cdot x} = g^{sk\cdot x \cdot y} = fx^y$. Furthermore, given $x$ and $g^{sk \cdot x}$, the ...
The closest that I can think of is a "symmetric bilinear group" (a.k.a. Type-I pairing group) that was popular when bilinear groups were first introduced. This is actually a pair of groups $(G, G_T)$ together with an efficient non-degenerate bilinear map $\otimes: G \times G \to G_T$. Obviously DDH is easy in $G$, since one can on input $(g, U, V, W) \in ... -2 Given$p$and$p_e \equiv p^e \pmod{n}$. You need to calculate$p_e$. Propose$e$is small enough to brute-force. The simplest way would be to calcute$p^e \pmod{n}$for values$e \in \{1,2, ..., n-1\}$until you find$p_e$. So all you need would be something like this: static int findE(int n, int p, int pe) { int base = p; for(int e = 2; e < n; ... 2 It is equally difficult (within a factor of 2) for any irreducible polynomial. Suppose$g$was your 'cheap' irreducible polynomial, that is, one for which, given$g^n$, you can rederive$n$quickly. Then, given an arbitrary pair$h, h^x$, you can quickly find$a, b$, such that$h = g^a$and$h^x = g^b$, and then immediately deduce that$x = a^{-1}b\$