# Tag Info

10

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

7

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

6

The question makes a number of statements that are incorrect. It is not correct that a fixed point is guaranteed to exist. It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist. Moreover, the existence of fixed points has only an extremely tenuous connection to security. Assume $E$ is a ...

6

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

5

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

4

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

4

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

4

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

4

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

4

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

4

Your first two paragraphs made a series of statements; these statements were less than perfectly accurate, and D.W. attempted to address those. You then went on and asked What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, ...

4

The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$. There is also the Computational Linear Assumption (CLIN), which states that it is hard to ...

4

Basically, every time you choose a group where the required hard problem is not hard, then you will run into problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography. Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a ...

3

You also asked I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions. One nontrivial result is here; what this result states is that a composition of the DES round functions ...

3

U-Prove Recommended Parameters describes the groups used by U-Prove. For the subgroup variant it references Appendix A.1.1.3 of FIPS186-3 which is about groups for finite-field based DSA. AFAIK these groups are Schnorr groups, even though NIST never refers to them as such. The ECC variant uses standard NIST curves such as P-256, P-384 and P-521.

3

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

3

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

3

The multiplication operation is indeed not uniquely reversible given just the output. But we also have one of the inputs, namely, the subkey. We can use that to reverse the multiplication. Decryption for IDEA requires changing the subkeys in the key schedule. I didn't find a good description of IDEA online, so I went back to Applied Cryptography, 2nd ...

3

DrLecter gave a good answer, I just wanted to include another well-known example. The Pohlig-Hellman algorithm can be used to compute discrete logs in groups whose order is a smooth integer. If two parties executing a textbook Diffie-Hellman key exchange use as their modulus a prime $p$ such that $p-1$ has only small factors (is 'smooth') an eavesdropping ...

2

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

2

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

2

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

2

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

2

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

2

No, they aren't a group. Justification: We know that the subgroup generated by DES is very large. If (any of the variants of) 3DES formed a closed group, then the subgroup generated by 3DES would be no larger than $2^{168}$. We know the latter is not the case. Therefore, the former is not the case, either. Also, for the EDE variants of 3DES, it is easy ...

2

To answer your question: it's expected, because you're using the wrong modulus. CodesInChaos pretty much gave you the correct answer; I'll try to explain in more detail about what's actually going on. We can define an elliptic curve based on any finite field $GF(p^k)$; in the case of P=256, we have ...

2

Should '$a$' be always an integer or can it be a group element itself?? Well, $aP$ is defined to be: $aP \equiv \underbrace{P + P + \ldots + P}_\text{a times}$ From that definition, we see that this makes sense only if $a$ is an integer; it needs to be a count of the number of $P$'s to add together.

2

If a prime $q$ is large enough discrete logs and CDH in $\mathbb{Z}_q$ are traditional hard problems in cryptography. Your other example $\mathbb{Z}_{2^n}$ is typically easy to solve because it can be solved progressively modulo increasing powers of $2$. May be you intended to consider the finite field with $2^n$ elements $\mathbb{F}_{2^n}$ and not ...

2

Ok, I took a look at the paper now. Thomas described the DLIN assumption, which is, however, not the assumption used in the paper you are looking at. Furthermore, what Thomas describes is the 2-DLIN assumption, which can be generalized to the $d$-DLIN assumption in a straightforward manner: $d$-DLIN Assumption: Given a group $G$ of prime order $p$, the ...

2

Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof. To prove $QR_N$ is a cyclic group, first, you have to know the order of it. In fact, the order of $QR_N$ is $pq=\phi(N)/4$($\phi$ is Euler function ).Actually, we can show this with the help of this map:x\to ...

Only top voted, non community-wiki answers of a minimum length are eligible