Hot answers tagged

18

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


9

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


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

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

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ...


5

It's not possible because if $B$ knows $b$ and $g^{ab}$, then she can compute $\left(g^{ab}\right)^{b^{-1} \bmod N} = g^a$ (where $N$ is the order of $g$, which is normally prime so that $b^{-1} \bmod N$ exists). EDIT: As noted by poncho in the comments, this assumes we are in a typical discrete logarithm setting, where the order of the group is prime to ...


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


4

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


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

Their statistical distance is less than $\: (q\hspace{-0.04 in}-$$\phi$$(q))\hspace{.02 in}/q\:$, $\:$ since $\:$ if $a$ is relatively prime to $q$ then $(\hspace{.02 in}g^a)^b$ and $g^c$ are $\:$ each uniformly distributed and independent of $a$ $\;\;\;\;$ and $\:$ even if $a$ isn't relatively prime to $q$, $(\hspace{.02 in}g^a)^b$ and $g^c$ each $\:$ ...


3

You're right in that there's little chance you can break the logarithm in a well-chosen 512 bit group (using a home computer, in reasonable time — as pointed out by SEJPM, it is possible investing some time and a good amount of money). However, in your case, the parameters are bad: The order of $(\mathbb Z/p\mathbb Z)^\ast$, that is $p-1$, is a smooth ...


3

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is ...


3

Sure. Use the strong RSA assumption. The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base. To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$. This is secure under the strong RSA assumption, and has a discrete log "feel" to it.


3

Yes, you are correct. There are various methods for scalar multiplication on elliptic curves. Some of them are optimised for fixed base-point scalar multiplication, i.e., where you a-priori know that you will mostly/exclusively perform scalar multiplications with respect to a fixed base point on the curve. Thus, one can make (extensive) pre-computations ...


3

Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime). Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability. Then, given a value $g$ and $h$, we can find $x$ with $g^x = h$ with nontrivial probability by: Create ...


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

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


2

Yes, it is equally as difficult; if we assign: $$g' = ag$$ $$a' = a^{-1}$$ $$b' = b$$ Then the restatement of your problem is: given $g' = ag$, $a'g' = g$ and $b'g' = abg$, compute $a'b'g' = bg$, which is exactly the ECDH problem. Now, this assumes that $a$ has an inverse; this is not a problem if the curve order is a prime, and is easy to work around if ...


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

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

Diffie-Hellman operates in a cyclic group by definition: the elements $g, g^a, g^b, g^{ab}$ are in the cyclic group generated by $g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway. In your example, you operate in the cyclic group $c\mathbf{Z}$, and as you were told in the comments, ...


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


2

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


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


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


1

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for elliptic curves is approximately $2s$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until $2020$. For more detail you can see ...


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

Actually, the algorithm is distinguishable. Let us assume that the attacker has two input, output pairs $(x, fx), (y, fy)$. Then, he can test whether $fy^x = fx^y$. If $fx = g^{sk\cdot x}$ and $fy = g^{sk\cdot y}$, this test will succeed, as $fy^x = g^{sk\cdot y \cdot x} = g^{sk\cdot x \cdot y} = fx^y$. Furthermore, given $x$ and $g^{sk \cdot x}$, the ...



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