News for hackers. Stuff that matters.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by brohee on Monday April 03, 2017 @02:36PM (#14025687)
Interesting, but no more.

The commonly used curve P-256 has the prime order 115792089210356248762697446949407573529996955224135760342422259061068512044369.

From the paper "The largest group of elliptic group of prime order that we tested is 129159847, in which a discrete logarithm problem was solved.".

Re:A Las Vegas algorithm to solve the elliptic curve discret... by dvdkhlng on Wednesday April 05, 2017 @07:59AM (#14041402)
The paper closes with

> However, we felt that computing the determinant for all possible sub matrices is a bottleneck for this algorithm and ways should be found to make this more efficient.

That last step is obviously of exponential complexity in the parameters r and t. I wonder whether the algorithm's total run-time becomes more acceptable when that last step is replaced by a polynomial-complexity computation.

To me it looks like an O(log(n)*n³) algorithm should be feasible, by replacing the submatrix-determinants with operations on determinants on large matrices that are generated in a way that ensures det=0 when any of the sub-matrices has det=0.

Unfortunately I don't really understand enough about the remainder of the paper to actually see how the useful the algorithm would be with that "bottleneck" removed.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by dvdkhlng on Wednesday April 05, 2017 @10:59PM (#14047583)
Too late to edit my comment, but for correctness' sake: the algorithm as described is exponential in k (and thus n), not r and t.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by PaulAJ on Monday April 03, 2017 @02:47PM (#14025816)
Thanks. I was just about to ask.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by hpsineqepsi on Monday April 03, 2017 @06:04PM (#14027644)
This algorithm is slower than existing approaches (Pollard's rho); the ridiculously small "largest group" that the author considered can be easily tackled in a split second with even inefficient general algorithms such as Shank's. It's surprising that such a boring non-result made it to the front page of HN.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by brohee on Monday April 03, 2017 @07:23PM (#14028182)
As I understand it, their implementation is in Sage, which can't really be considered optimized. Is their method inherently slower than Pollard's rho, or is it an implementation issue?
Re:A Las Vegas algorithm to solve the elliptic curve discret... by kafkaesq on Tuesday April 04, 2017 @03:35PM (#14036402)
It's surprising that such a boring non-result

Just because it (currently) only works on a small modulus doesn't make it a "boring non-result". It's the concept that matters.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by 19eightyfour on Monday April 03, 2017 @12:46PM (#14024424)
I think in general the technique of introducing some slack in the form of partitions and then constraining those using some property of the specific problem space, in this case linear relations of whether those points lie on some curve, is very strong and has general applicability. Sort of like branch and bound. It's nice to see that this author started with a general idea that wasn't that fast, and then used a lot of clever details to improve the implementation of that same idea over a number of years.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by eximius on Monday April 03, 2017 @02:53PM (#14025897)
What is the estimated complexity of this attack? It is not clear to me how to use the probability of success formula for an arbitrary keysize.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by ecdh on Monday April 03, 2017 @12:52PM (#14024506)
Uh, wait a second. Is Elliptic Curve Diffie Hellman broken now? Does this work on curves used in TLS?
Re:A Las Vegas algorithm to solve the elliptic curve discret... by brohee on Monday April 03, 2017 @07:24PM (#14028190)
Not remotely practical against curves in actual use...
Re:A Las Vegas algorithm to solve the elliptic curve discret... by sokoloff on Monday April 03, 2017 @12:21PM (#14024122)
We don't have to (and shouldn't, IMO) American-ize "Monte Carlo"

Edit: TIL that they are different. (Thanks for the explanations below! esp: gmfawcett and 1001101)

Re:A Las Vegas algorithm to solve the elliptic curve discret... by teraflop on Monday April 03, 2017 @12:28PM (#14024194)
It's not just an Americanization. "Las Vegas" and "Monte Carlo" are technical terms with specific, different meanings.

A Monte Carlo algorithm runs in a deterministic amount of time, and computes a probabilistic (approximate) result. For example: Monte Carlo numerical integration, or Miller-Rabin primality testing.

A Las Vegas algorithm takes a non-deterministic amount of time, but is guaranteed to return a correct result. For example: quicksort with a random choice of pivot.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by rawnlq on Monday April 03, 2017 @04:19PM (#14026754)
There's a popular interview question that has a las vegas algorithm as a solution. It's a more illustrative example since it takes an unbounded amount of time.

Let's say you want to simulate a 1/3-biased coin with a fair coin.

One solution is to flip the fair coin twice, then output heads if you get HH, output tails if you get TH or HT, otherwise retry (if TT).

Then this process is guaranteed to always output heads with 1/3 probability and tails with 2/3 probability if it ever ends. The runtime complexity is unbounded since you can keep getting TT forever but the expected runtime is constant.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by curuinor on Monday April 03, 2017 @05:33PM (#14027389)
Similary to St. Petersburg paradox (https://en.wikipedia.org/wiki/St._Petersburg_paradox).

The expectation is a stranger and more dangerous beast than would be easily expected.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by tgb on Monday April 03, 2017 @12:42PM (#14024372)
I don't see why quick sort with a random pivot takes a non deterministic amount of time.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by rdtsc on Monday April 03, 2017 @12:48PM (#14024450)
> I don't see why quick sort with a random pivot takes a non deterministic amount of time.

Because it might sort faster or slower depending on how the pivot gets picked. But you'd get the sorted list in the end. A Monte Carlo solution might run for 5 seconds but you might get a partially sorted list only.

Re:A Las Vegas algorithm to solve the elliptic curve discret... by tgb on Monday April 03, 2017 @01:21PM (#14024887)
Ah I see thanks. I was thinking the claim was that it might take an unbounded amount of time.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by 1001101 on Monday April 03, 2017 @12:25PM (#14024164)
Las Vegas = Always Correct, Probably Fast

Monte Carlo = Probably Correct, Always Fast

Re:A Las Vegas algorithm to solve the elliptic curve discret... by funkaster on Monday April 03, 2017 @04:36PM (#14026894)
Adding speed to the classification is misleading. It might be better to state:

  - Las Vegas: Correct, Time unbounded
  - Monte Carlo: Not always correct, Time bounded
edit: format
Re:A Las Vegas algorithm to solve the elliptic curve discret... by kccqzy on Monday April 03, 2017 @04:41PM (#14026934)
As pointed out already, a Las Vegas algorithm might have bounded but non-deterministic time.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by thomasahle on Monday April 03, 2017 @03:04PM (#14026003)
I think people would probably call an algorithm that is "Probably Correct, Probably Fast" Monte Carlo as well.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by hyperbovine on Monday April 03, 2017 @01:20PM (#14024873)
Since when is Monte Carlo fast :-)
Re:A Las Vegas algorithm to solve the elliptic curve discret... by snovv_crash on Monday April 03, 2017 @01:59PM (#14025298)
More often than not, it is faster than figuring out the exact solution, if an exact solution exists. Things like having a piecewise distribution somewhere in your problem make Monte Carlo several orders of magnitude easier to implement.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by hyperbovine on Monday April 03, 2017 @05:37PM (#14027418)
The depends a lot of the dimension of the space you're trying to integrate over, and in any case, (vanilla) Monte Carlo is trivial to implement. I was more poking fun at the very different way theorists and practitioners view classes certain algorithms. "Deterministic running time" is not a particularly strong guarantee, in practice.
Re:A Las Vegas algorithm to solve the elliptic curve discret... by gmfawcett on Monday April 03, 2017 @12:26PM (#14024173)
I had the same initial reaction, but it seems that they are not the same thing:

https://en.wikipedia.org/wiki/Las_Vegas_algorithm

Re:A Las Vegas algorithm to solve the elliptic curve discret... by protonfish on Monday April 03, 2017 @12:25PM (#14024162)
I guess you could use "stochastic" but that isn't nearly as clear and descriptive as "Monte Carlo"