Tag Info

New answers tagged


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


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; ...


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$

Top 50 recent answers are included