# Tag Info

13

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$ $= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] ...

12

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

12

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation $$\varphi^2-t\varphi+q = 0 ... 11 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. ... 11 It depends. If the order m of g's group is known and a has an inverse modulo m (which is the case if and only if a is coprime to m), then it is easy: Calculate the inverse b:=a^{-1}\bmod m (for instance, using the Euclidean algorithm), and compute the power (g^a)^b. By Lagrange's theorem, this equals g. However, there are cases for which ... 11 A safe prime is a prime number p for which (p-1)/2 is also prime. The order of an element g of the group \mathbf{Z}^*_p (the integers modulo p, excluding 0) is the smallest integer n such that g^n\equiv 1\pmod{p}; this is always a factor of p-1. The orders of the subgroups of the group generated by g are the factors of the order of g; ... 9 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 ... 8 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 ... 8 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 ... 8 Question: Given n values v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p for a large n can the adversary learn the value \alpha? Answer: assuming that the r_i values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about \alpha (other than whether or not it's 0). We can ... 7 Basically, every time you choose a group where the required hard problem is not hard, then you will run into a 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 ... 7 Note that you do not have an efficiently computable homomorphism from G_1 to G_2, but in Type-2 you have an efficiently computable homomorphism \psi: G_2 \rightarrow G_1 and in Type-3 you do not have one. But what I don't understand is what is the use of the homomorphism in cryptography? Well, if you have a tuple (aP',bP',cP')\in G_2^3 with ... 7 Ok, I will start with a cryptographic bilinear map. Cryptographic Bilinear Map A cryptographic bilinear map e: G_1\times G_2 \rightarrow G_T as the name says is a map that is linear in both components, i.e., it holds that for all g\in G_1 and h\in G_2 and all a,b\in Z_p (where p is the order of all groups) we have that e(g^a,h^b)=e(g,h)^{ab}. ... 6 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 ... 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 ... 6 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 ... 6 You may find it useful to play around with a toy example, such as the integers modulo a Fermat prime, like p = 257. Since g is a generator of the Group, h \equiv g^x for some unknown exponent x. In other words, \log_gh = x, and for Groups of order 2^k, this discrete log is easily computed like so: Interpret x as a k bit number, i.e. x = ... 5 I'll use these common definitions and notations: a\equiv b\pmod c means that c>0 and c divides b-a a\equiv b^{-1}\pmod c means that a\cdot b\equiv 1\bmod c a=b\bmod c means that a\equiv b\pmod c and 0\le a<c a=b^{-1}\bmod c means that a\equiv b^{-1}\pmod c and 0\le a<c \varphi is the Euler totient function (also noted ... 5 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 ... 5 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 ... 5 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, ... 5 With addition and \mathbb{Z}_n, each party chooses a secret x and sends xg \pmod n over the wire, for an agreed upon generator g. Division by g modulo n is easily computable, and reveals x. In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With \mathbb{Z}_n and ... 5 This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain. For prime p, we know that g^{p-1} \equiv 1 \pmod{p}. Therefore, y = g^{p-2} \equiv 1/g \pmod {p}. Therefore, (xg).y \equiv x \pmod{p}, revealing the secret key. If modulus is not ... 5 There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in ... 5 I'll add something to the previous answer. The first way to construct multilinear maps is pretty recent and was introduced by Sanjam Garg, Craig Gentry and Shai Halevi. What we want is given groups G_1,\ldots,G_n and G_T a map:$$e:G_1\times\cdots\times G_n\to G_T that satisfies the linearity property in DrLecter's answer. It's worth nothing here, ...

5

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$. ...

5

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction. Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three ...

5

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

4

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

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

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