# Tag Info

## Hot answers tagged discrete-logarithm

19

A couple things: This article is two years old, so take its predictions with a grain of salt. In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon. The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those ...

8

Computing $d$ given $P$ and $Q$, with $Q = dP$ is known as the "elliptic curve discrete logarithm problem" and is considered to be infeasible under some hypothesis. The security of Elliptic Curves Cryptography is based exactly on the ability to compute the point multiplication and the intractability of the inverse operation: given two points find out the ...

6

"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime. The intuitive reason why the DLP is harder to solve over (well chosen) elliptic curves is that they are our best ...

6

I just want to highlight: The new advancement need to be realized and validated. ECC and DH are quite similar although ECC discrete logarithm problem is harder. In other words, whatever effects the security of DH might not affect ECC with the same magnitude.

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 And we know that knowing of$Q$and$P$is sufficient to be able to compute$d$efficiently. I think you meant "knowing$P$and$d$we can compute$Q$efficiently. That's the DLP as stated in your previous answer. I think it's more intuitive to work in$\mathbb{Z}_p^*$and in this group you might reframe the DLP question as this: "given some generator$g$... 5 I will assume you understand modulo operation and the exponentiation. First let's consider logarithm in$\mathbb{R}$. You know that if we have$e^x = y$then$x = \ln y$. The Napierian logarithm return values in$\mathbb{R}$. You can have the same thing with another base. For example :$2^3 = 8$and$\log_2 8 = 3$. The simplified idea of the discrete ... 5 I will assume for simplicity that you're talking about the full multiplicative group of$F_p$instead of a proper subgroup, thus there are no problems with$g^a+1$(except when$g^a=p-1$which can be trivially ruled out by comparing to$p$). The quantity$\log_g(g^a+1)$is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for ... 4 The complexity of Pollard-Rho is indeed$O(\sqrt{\text{ord}(g)})$, but even though$n$refers to the modulus, their statement might be correct depending of the context. If the modulus considered in your situation is a "classical" modulus in crypto (e.g.$n = (2q+1)^k$for a prime$q$and a small$k$, etc), as the modulus will be in general chosen so that ord$...

4

In this case, the base does not matter as the $\log$ terms are wrapped in an $O$ expression. The $O$ expression lets you throw away constant factors and to convert something base $X$ to base $Y$ is simply $\log_X Z = \frac{\log_Y Z}{\log_Y X}$, well, $\log_Y X$ is a constant, so it can be thrown out in the $O$ expression. The reason the second reference ...

4

The difference is purely conceptual. That is, when Diffie-Hellman published their paper, they equated between public-key encryption and trapdoor functions. Thus, they did not think that they had constructed a public-key encryption scheme, and this invention came only a year later with RSA. In fact, Diffie and Hellman even explicitly talk about publishing one ...

3

It can affect several classes of Elliptic curves. In particular, if this curves have pairings or any other way to translate the problem to a finite field (or extension finite field). The tricky part about ECC is that if you do not pick your Elliptic curve properly, you might end up with a weak implementation. Or, with an implementation in which the problem ...

3

The answer depends on the factorization of $p-1$; for any factor $q$ of $p-1$, the attacker can derive $x \bmod q$ in $\sqrt{q}$ steps (by first computing $(g^x)^q = g^{xq}$, and then searching for the value $y$ with $(g^{xq})^y = 1$ using, say, Pollard Rho. Hence, if the attacker has a computation budget of $n$, and $p-1 = q \cdot r$, where $q$ is $n^2$ ...

3

In the introduction of the Logjam paper, it is stated that After a week-long precomputation for a specified 512-bit group, we can compute arbitrary discrete logs in that group in about a minute. So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should ...

3

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants. We come up with: $$a \cdot b^x = y$$ where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$. If it is sufficient for an attacker to find a ...

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$

2

As a add on to the above answer, it would be insecure to use $g^{x+y}$ as key , because both $g^x$ and $g^y$ will be transmitted publicly and by simply eavesdropping one can easily find the required key i.e $g^{x+y}$.

2

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 For computing$Q=dP$we have a "NAF" methods that are more faster than logarithmic methods. Fore more detail you can see "guide to elliptic curve". Also for computing$d$from$Q=dP$, the method that commonly use is pollard-rho method. This method is based on birthday paradox attack and be-able to solve discrete logarithm in$O(\sqrt p)$which$p$is a ... 2 I've read in several places that somehow the largest prime factor$q$of$|g|$(order of$g$) is assumed to be large enough without actually knowing$q$. How do they do that? Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite. The server proposes$p$and$g$as a part of the exchange, and hence the ... 2 I think the problem is that you are trying to recompute the result in$(p-1)(q-1)$instead of$n$and that is why you don't find the exact$x$. Your question is: I can compute the discrete logarithm of$y=g^x \mod n$by computing the discrete logarithm of$y$modulo$p$and$q$. But then how to recompute it? As I understand, you want to find the ... 2 Yes, this logic works. You have shown that given the discrete log$x$lets you easily find collisions. Now you need to show that any collision lets you extract the discrete log$x$and then you are done (then you have shown the equivalence). 2 It should be$\;\; O\Big(\hspace{-0.07 in}\sqrt{\text{order of g}}\hspace{-0.02 in}\Big) \:$group exponentiations$\;\;$. When$q$is the order of$g$, that will be$\;\; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{q}\hspace{-0.02 in}\right) \:$group exponentiations$\;\;$. When$n$is the order of$g$, that will be$\;\; O\hspace{-0.04 in}\left(\...

2

For arbitrary positive integer $n$ we have: $$\gcd(n,n+1)=1$$ So $q-1$ and $q$ haven't any nontrivial common factor.

2

I am really not sure about what you are trying to do. If you simply want to prove that $Ans = e(g,h)^k \times e(g,h)^r$ is hidden given only $(g,h,e(g,h)^k)$, then this is trivial and does not require any hypothesis at all (in particular, no discrete logarithm problem is involved). Indeed, this is perfectly equivalent to the problem of finding $e(g,h)^r$ ...

2

I'll assume R is secret, and is the key; and the ciphertext is given as a list of values x in decimal, as in the example given x = 0.559425856. This is totally insecure: even without knowledge of R, it is trivial to reduce candidate plaintext letters to almost nothing, just by knowing the corresponding x. e.g. if we assume R is an integer in range [2..127],...

1

It probably divides $q-1$ (composite) not $q$.

1

There is 3 kind of discrete log problem as you explained : Diffie-Hellman problem (Dlog): Pick $a \in \{1,\ldots,q\}$. Compute $A = g^a \mod\ p$ Given $(p,q,g,A)$ find $a$. Assumed hard. Computational Diffie-Hellman problem (CDH) : Pick $a,b \in \{1,\ldots,q\}$. Compute $A = g^a \mod\ p$ and $B = g^b \mod\ p$ Given $(p,q,g,A,B)$ find $g^{ab}$. Note that ...

1

Usually the point of working with a Type 3 pairing is exactly to have such a tuple, and use the pairing to decide if the fourth element indeed equals $zQ$ or some other element. So if this problem is not hard and $z$ is private, then you're in trouble. From your explanation, I don't think you require a Discrete Log-like assumption. You are saying ...

1

For the curves used in cryptography today, the order of the group of points is typically 256 bits, sometimes 512. Such numbers are within the range of current factoring algorithms (indeed, this is why you don't use 512-bit RSA keys), and so typically the order of the group can be factored and it is easy to see whether it has a large prime factor. Moreover, ...

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