26

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 $\mathbb{R}^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it. The discrete logarithmic ...


21

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 your question. For 112 bit security (which is about the minimum you should use for not extremely important things) you currently (2016) have to use RSA-2048 keys, ...


21

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 encryption algorithm with 112 bits of security. Also in common use as of this date are 256 bit Elliptic Curve keys (mostly NIST P-256 and Curve25519) for ECDH/...


20

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


18

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 prohibitive. A 256-bit curve is large enough; a 60-bit curve is not. Also, some curves have a special structure which can be leveraged to compute DL faster. ...


17

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 the compactness of the original Schnorr signature scheme? Yes, Schnorr signatures. They are really what you should be doing. It is theoretically and ...


16

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$ A discrete log in some other group; that is, given a group $G$, a ...


15

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$. In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but ...


14

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 function and its inverse are nice, so you can use infinite series for your computation, and some partial sum will be close enough to the correct answer. Or ...


13

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^*$ and $S^1$. We can view $S^1 \cong \{z\in\mathbb{C} \mid |z| = 1\}$. It's not hard to show that any $z\in S^1$ is able to be written as $z = \exp(2\pi i t)$ ...


12

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


12

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...


12

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 known reduction to a 'more fundamental' problem, such as factorization or discrete log. The closest we can get is a proof that if you can find the 'decryption ...


11

While $O(n)$ is linear in the order of the group, what matters is actually the computational difference between the exponentiation and the discrete logarithm. The exponentiation is not in $O(n)$ but instead in $O(\log(n)) = O(|n|)$ (e.g. expoentiation with square and multiply has $|n|$ multiplications and at most $|n|$ squaring operations). Therefore, the ...


11

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


11

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-and-add algorithm (which will be reasonably efficient), and, similarly, raise a point to some integer power with a square-and-multiply algorithm. Your additive ...


11

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)$, where both partial derivatives vanish. We translate the curve to have this singular point at $(0, 0)$ by changing variables $(x, y) \mapsto (x - 23796, y - 0)$...


11

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 situations. The soundness of the protocol is not based on the Diffie-Hellman problem. This is probably the most important point to address. What does it mean for ...


10

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[2] including an objection to the now-infamous random generation of the per-signature secret). Though the computational cost was too high for an academic ...


10

"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 States. This section from wikipedia explains it well enough: The longest key size allowed for export without individual license proceedings was 40 bits, so ...


10

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^x, g^{x+y}, y$. The reasoning is simple; if that were an easy problem, that is, if we had an oracle that, given $g, g^x, g^{x+y}, y$, recover $x$, we could ...


9

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however the ...


9

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


9

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 that the probability that an adversary solves OMDL (without pre-computation) in a generic group of prime order $N$ and making at most $T$ oracle queries is at ...


9

$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 intersects the curve with multiplicity three) or a singular point (a point where there is no tangent because both partial derivatives are zero). [Reducible ...


9

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}$ asymptotically. Then both expressions are indeed $\mathcal{O}(\sqrt q)$.


8

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$: If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time. Use the Number Field Sieve algorithm to attack the discrete log problem in $Z^*/...


8

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


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