26 votes
Accepted

Why was the term "discrete" used in discrete logarithm?

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group. The standard logarithmic problem is over the infinite group $\...
poncho's user avatar
  • 146k
21 votes

What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet?

A good overview on that matter can always be found on https://keylength.com, which summarises many publications with recommendations for key lengths. Especially NIST SP-800-38 yields good data for ...
mat's user avatar
  • 2,508
21 votes
Accepted

What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet?

Currently (as of 2017-05-11) 2048-bit keys are most popular for use with RSA, and 2048 bit keys should also be used with classic Diffie-Hellman. These offer about the same security as a symmetric ...
rmalayter's user avatar
  • 2,297
19 votes
Accepted

How can there be insecure elliptic curves if the discrete logarithm problem is hard?

Discrete Logarithm on elliptic curves is hard in the following sense: on an $n$-bit curve, solving DL has cost $2^{n/2}$. Thus, this is infeasible only as long as $n$ is large enough to make that cost ...
Thomas Pornin's user avatar
17 votes
Accepted

Security of Schnorr signature versus DSA and DLP

Your post was a bit confusing to me, I think you're thinking of this from the wrong perspective. Is there a scheme with security arguably equivalent to DSA (or better, the DLP or related), but with ...
CurveEnthusiast's user avatar
15 votes
Accepted

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most ...
Geoffroy Couteau's user avatar
15 votes
Accepted

Why is the discrete logarithm problem hard?

Now, I wonder if there are any better arguments. Ultimately, no, not really. We don't have any proof that computing discrete logs is hard. For that matter, we don't have any proof that any problem ...
poncho's user avatar
  • 146k
14 votes

Using Shor's algorithm to solve the discrete logarithm problem

Shor's method relies on a period finding routine on a quantum computer. A function $f: (x_1, \dots, x_n) \mapsto f(x_1, \dots, x_n)$ is periodic, of period $(\omega_1, \dots, \omega_n)$, if $f(x_1 + \...
user94293's user avatar
  • 1,779
14 votes

Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?

The main point is that the entire apparatus of calculus applies to exponentiation over the real numbers. For instance, if $a$ and $b$ are close, then $g^a$ and $g^b$ are close as well. The exponential ...
K.G.'s user avatar
  • 4,607
13 votes
Accepted

How to solve this ECDLP?

We begin with the singular curve $$ y^2 = x^3 + 17230x + 22699\,. $$ This curve is singular, as can be immediately determined by its $0$ discriminant. Furthermore, it has a singular point $(23796, 0)$,...
Samuel Neves's user avatar
  • 12.4k
13 votes

Why was the term "discrete" used in discrete logarithm?

While I agree completely with poncho's answer, this other viewpoint might be useful. Specifically, I think a better comparison isn't between $\mathbb{Z}_p^*$ and $\mathbb{R}^*$, but with $\mathbb{Z}_p^...
Mark's user avatar
  • 12.5k
12 votes
Accepted

What is the difference between discrete logarithm and natural logarithm?

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 ...
Biv's user avatar
  • 9,979
12 votes
Accepted

Is the additive discrete Logarithm problem always easy in Fields?

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-...
Thomas Pornin's user avatar
12 votes
Accepted

Small exponents and the RSA problem

Can you please give me some direction for such proof? You're looking for a proof that the RSA problem is hard? No such proof is known (even in the specific case of $e=3$). Furthermore, there is no ...
poncho's user avatar
  • 146k
11 votes
Accepted

Is it possible to generate backdoored DH parameters?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[...
Squeamish Ossifrage's user avatar
11 votes

What does "export grade" cryptography mean? And how is this related to the Logjam attack?

"Export grade" cryptography is a result of The Crypto Wars. Laws were passed in the United States that resulted in the crippling of encryption software that was distributed outside of the United ...
Ella Rose's user avatar
  • 19.6k
10 votes
Accepted

Extracting $ x $ given $ g^x, g^{x + y}, y $

Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here. Yes, it is still hard to find the discrete log, given $g, g^...
poncho's user avatar
  • 146k
10 votes
Accepted

Why do the discriminant and primality of the group order of an elliptic curve affect security?

$y^2 = x^3 + ax + b\bmod p$ is the Short Weierstrass equation. The theory behind it is here Using Bezout’s Theorem, it can be shown that every irreducible cubic has a flex (a point where the tangent ...
kelalaka's user avatar
  • 48.3k
9 votes
Accepted

Do I understand (below) why Q = dP is easy while finding d is hard

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 ...
ddddavidee's user avatar
  • 3,324
9 votes
Accepted

Discrete logarithm problem is easy in a cyclic group of order a power of two

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 $...
J.D.'s user avatar
  • 4,415
9 votes
Accepted

Using Pedersen commitment for a vector

Yes, you got the scheme essentially right - except that the group cannot be $\mathbb{Z}_p^*$, as the latter does not have prime order. It can however be many other things - like the multiplicative ...
Geoffroy Couteau's user avatar
9 votes
Accepted

Is the one-more discrete log problem hard in the Generic Group Model?

More recent work by Bauer et al. [BFP] claims that the proof in a previous answer is flawed (and that Coretti et al. confirmed this). However, Bauer et al. prove hardness of OMDL in the GGM. They show ...
nickler's user avatar
  • 271
9 votes
Accepted

Small error in security proof on the paper On the Multi-User Security of Short Schnorr Signatures with Preprocessing

Yes, you've raised a flaw, you can contact the authors, they will probably update their proof in the paper. But as you've noticed, it's not a big deal because $2q$ is much smaller than $\frac{3q^2}{2}$...
Ievgeni's user avatar
  • 2,585
9 votes
Accepted

How to prevent the solution of a discrete logarithm problem from being found in a collision way by accident

Even if all users are aware of the $h$ values of all others, avoiding collisions is not difficult, you just need to make sure the probability will be negligible. We simply need to ensure the size of ...
Meir Maor's user avatar
  • 11.8k
8 votes
Accepted

Why do the subexponential algoriths for the DLP not work for the ECDLP?

"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{...
Geoffroy Couteau's user avatar
8 votes
Accepted

What is a cyclic group of prime order $q$ such that the DLP is hard?

Cyclic group of prime order q such that the DLP is hard A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) ...
fgrieu's user avatar
  • 140k
8 votes
Accepted

ElGamal with elliptic curves II

I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen ...
poncho's user avatar
  • 146k
8 votes

Hardness assumption: Extracting $g^y$ from $g^x, g^{x+y}$?

No, this is (nearly) never hard. To recover $g^y$ from $g^x,g^{x+y}$ all you need is a fast (ie polynomial-time) group operation (which is a given, because otherwise you'd have a hard time to come up ...
SEJPM's user avatar
  • 45.9k
8 votes

Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?

For any discrete log problem where the order of the generator is even and known, then the lsbit is easy to recover. Notation I'll use: I'll be writing things in additive notation (the notation we ...
poncho's user avatar
  • 146k

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