Tag Info

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a ...

As far as I understand, the HSP is a hard problem such that: some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built); many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key. In particular, integer ...

Almost all cryptographic algorithms which use groups actually work in subgroups generated by a conventional element; even if the group as a whole is non-abelian, the subgroup is cyclic, thus abelian. The Anshel-Anshel-Goldfeld protocol tries to use non-commutativity itself, and relies on "how much non-abelian" the group is. All asymmetric cryptographic ...

The answer comes from Euler's Theorem. Note: math below is done modulo $N$ unless otherwise specified and draws heavily from group theory. That theorem says that any element of a group (say $m$) raised to the order of the group, in this case $\phi(N)$ is congruent to $1$ (i.e., $m^{\phi(N)}\equiv 1\bmod{N}$). Furthermore, this holds for multiples of ...

The cornerstone of the argument is the following: If the cycle attack works, then you can factor $n$ (see details below). The attacker can choose $e$. I.e., when trying to factor $n$, the attacker is not constrained to use the specific $e$ which you selected for your public key; he can invent his own $e$, since he will do all the computations himself. ...

There is a reduction from DL to RSA if the DL oracle accepts composite modulus. For prime modulus, a reduction is not known. I copied the following from this wikipedia page with minor edits. Let $n = pq$ be RSA modulus. Generate random number $a$ co-prime to $n$ and random number $x < n$ but very close to $n$. Compute $b = a^x \text{ mod } n$ but ...

If $\mathcal{G}$ is of order $N$ (who doesn't look like a prime number btw) and $g$ is a generator of $\mathcal{G}$ then $g$ has order N. Since $(g^{nq})^p=1$ and $\forall 1\le k <p, (g^{nq})^k\neq 1$ (g has order $N$ and $knq<N$) then $g^{nq}$ generates a subgroup of $\mathcal{G}$ of order $p$ and there's only one such subgroup : $\mathcal{G_p}$. The ...

As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus". Here's is a demonstration that the discrete log problem is not drastically easier than factoring the ...

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup. One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in ...

Every element $g$ in a group $G$ generates a subgroup of $G$ of order $r$, where $r$ is the smallest (non-zero) integer such that $g^r = 1$. Moreover, if $g^s = 1$ for some positive value $s$, then $s$ is a multiple of $r$. Finally, $r$ necessarily divides the order of $G$ (i.e. the number of elements in $G$). Therefore, if your group order is $N = ab$ for ...

In cryptography, you care not merely that some problem is hard but that hard instances are readily producible. Why don't people use NP-complete problems for cryptography, for example? An NP-complete problem would give you greater confidence asymptoticly speaking for two reasons : If any NP-complete problem were collapsed to P, then factoring becomes P ...

One of the biggest problems you'll have is to ascertain that $m^{e^k} = m$ for some $k$. You need to have a way of knowing that particular value is genuine. Given the typical use-case of RSA applies padding and is used for small data sizes for things such as keys to symmetric algorithms, it isn't always likely that this check will be easy to compute. The ...

In my experience, I never have found that cryptographers base their opinion of a cryptosystem on the properties of the underlying group. If its a braid group, abelian group, or finite field: that does not really matter. What matters is, as @Thomas notes, how hard do we think the problem is in a particular setting? Cryptography in braid groups usually has ...

According to this: To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes. So, given your question "Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?" the answer would be yes. Furthermore, if you can solve DLP for composite ...

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA ...

You need to refine your definition of discrete logarithm to get a precise answer, as the discrete logarithm problem can be defined for any group, Being able to compute the discrete logarithm on the group of points of a degenerate elliptic curves defined over the ring $Z_n$ also yields the factorization of $n$ (see Silverman's xedni calculus).

The security claim on page 5 of the Linear Cramer-Shoup paper is that their modified scheme is CCA secure, which is weaker than the IND-CCA2 security of the original DDH based Cramer-Shoup scheme. However, from the outline of the security proof, it seems the author actually means the LCS scheme is CCA2 secure. Also note the first sentence on page 6: ...

Generally speaking, this problem is computationally easy. It is easy to tell whether a solution exists and, if so, to find at least one. If you want to find one solution (one $x$ that satisfies the equation), assuming a solution exists, this is easy. @CodesInChaos explains how. If you want to find all solutions, then it's easy to enumerate all solutions. ...

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can ...

I'll give a sketch of the solution to a quite similar problem (that makes more sense to me). The purpose of this modified problem is to show that it is essential to take $g$ of order exactly $q$ in the given setup, as one otherwise gets an oracle returning $u^x$ given $u$ as in your problem. (I'll show the connection between both problems (yours and mine) at ...

The hidden subgroup problem is very useful for developing an understanding of pairing-based non-interactive zero-knowledge proofs. You would need a suitable elliptic curve of large composite order in order to use the hidden subgroup problem securely so in practice, you probably wouldn't bother as the implementation would be very slow. However, the ...