# Tag Info

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 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$1 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 ...