28

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...


25

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


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


20

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


20

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


19

The generic discrete logarithm problem is this: Given a group $(G, ·)$ with generator $g$ and $y \in G$, find $x \in \mathbb N$ such that $y = g^x$. The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e. $(\mathbb Z/p \mathbb Z)^*$: Given a ...


17

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ...


17

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


16

The misunderstanding you have is with the sentence "the sender is able to compute an $r'$..." Actually, that's not true, and the "information theoretically hiding" bullet point does not state that. What it does state is that, for every $m'$, there exists an $r'$ that satisfies the relation; however it does not imply that a real sender can find such a value....


15

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


14

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


13

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...


13

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


13

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


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

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


11

I'm not sure how to answer the question about "trust" in the assumption. I suppose that is a matter of personal belief more than science. We don't know the truthfulness about any cryptographic assumptions, although obviously some have received more scrutiny than others. I'd say that the KEA assumptions have received relatively little attention, and so should ...


11

Well, yes, that is generally good advice about DH. Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps. If we have as our ...


11

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups. In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ...


11

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


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


10

Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP. Here's what's going ...


10

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


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

Here's the deal. The discrete log problem is feasible in the special case where the exponent is known to come from a small range of possibilities (e.g., the exponent is not too large). Suppose we are given $y=g^m$, and we want to find $m$. Suppose moreover we know that $m$ is small: $0 \le m < 2^{30}$, say. Then it turns out it is easy to recover $m$, ...


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

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


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


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