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 $\...
- 145k
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 ...
- 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 ...
- 2,287
20
votes
Accepted
RSA & DH at risk due to math advances, will this eventually affect elliptic curves too?
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 ...
- 4,626
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 ...
- 86.6k
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 ...
- 3,459
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 ...
- 145k
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 ...
- 4,607
14
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 ...
- 19.1k
13
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 + \...
- 1,759
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)$,...
- 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^...
- 11.6k
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 ...
- 9,969
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-...
- 86.6k
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 ...
- 145k
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[...
- 47.9k
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 ...
- 19.5k
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^...
- 145k
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 ...
- 47.6k
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 ...
- 3,294
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 $...
- 4,405
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 ...
- 19.1k
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 ...
- 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}$...
- 2,565
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 ...
- 11.7k
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{...
- 19.1k
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) ...
- 138k
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 ...
- 145k
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 ...
- 45.7k
Only top scored, non community-wiki answers of a minimum length are eligible