Factoring may be easier than we think (2016) • Hacker News Board

Re: Factoring may be easier than we think (2016)

#121

Post by thechao » Sun, Jun 30, 2019, 10:24 PM UTC

scottlocklin wrote: post #99

daveFNbuck wrote: post #31

Earlier quoted context omitted.

It's basically that BPP captures all realistic polynomial-time computations. The speedup would have to be sufficient to show something like a problem in BQP that isn't in BPP. I don't think anyone has been able to show that unconditionally yet. You'd also need to accept that Quantum computers are realistic, which is why Aaronson's trilemma includes quantum computers being impossible.

This sort of statement is exactly why serious people shouldn't take "quantum complexity theory" seriously. The complexity class BQP is bullshit: there are no quantum computers, the end. Feel free to prove me wrong by building one which does useful calculations. No time limit, until you die, in which case "time's up." Edit add for downvoters: the strong Church Turing thesis is also almost certainly, and very obviously…

You’re merely goalposting Scott “Quantum Computing Fists of Fury” Aaronson’s trilemma. If you have proof that quantum computers are physically unrealizable, I’ll happily help you publish that paper. There’s no way my brother could belittle my lack of education if I had a Turing Award or Nobel Prize, or two.

Re: Factoring may be easier than we think (2016)

#122

Post by rocqua » Sun, Jun 30, 2019, 10:25 PM UTC

bobbylarrybobby wrote: post #92

shoes_for_thee wrote: post #57

Earlier quoted context omitted.

You're going to have to launder a lot of money. What's your strategy there?

Is it illegal to break encryption by brute force?

Intent matters. If you are breaking encryption to steal stuff, that is (and should be) illegal.

I think the real question here should be whether it is immoral though, because it is trivially illegal. Consider the DMCA and penalties for circumventing DRM. Heck, if you are decrypting stuff that is classified, intent might not even matter.

Re: Factoring may be easier than we think (2016)

#123

Post by lowdose » Sun, Jun 30, 2019, 10:25 PM UTC

vbezhenar wrote: post #110

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone. 2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip…

You have given this much thought care to elaborate?

Re: Factoring may be easier than we think (2016)

#124

Post by rocqua » Sun, Jun 30, 2019, 10:28 PM UTC

heimatau wrote: post #72

JD557 wrote: post #66

Earlier quoted context omitted.

I'm not very familiar with cryptocurrencies, but wouldn't you be able to also crack crypto wallets? If so, wouldn't the value of crypto go down to 0 thanks to your service?

Cracking RSA isn't cracking SHA-256. Bitcoin and other coins are based on SHA-256. If someone were able to crack SHA-256, the exploit would be better served (of the hacker) to slowly steal coins, so that value within the network is maintained and the exploit is overlooked and missed by the majority. In addition to stealing national secrets. But all you'd need to do is steal from one early adopter (it's in their finan…

The moment you have spent from an address, you have revealed the un-hashed key, which you could break. Best practice is never to re-use address, but I'd wager there are many deviuations from that. I'm not sure how much bitcoin that has moved in e.g. the last year is in addresses for which the private key is known. Would be a cool thing to check out.

Re: Factoring may be easier than we think (2016)

#125

Post by rocqua » Sun, Jun 30, 2019, 10:31 PM UTC

aewens wrote: post #45

zvrba wrote: post #37

Earlier quoted context omitted.

I think there are only two safe options if your intention is to avoid being assassinated: 1) don't tell anyone, 2) publish it anonymously. If you want to be able to prove to somebody that you're the author, sign the paper and keep the private key offline on a piece of paper. It'd be interesting if it could be used to manipulate voting results, but e-voting is still in its infancy.

Interestingly, the consequence of releasing that algorithm would make having that private key insignificant since most schemas rely on factoring primes to secure the key pair.

HMAC with sha-256 works decently. No need to involve a public key.

Re: Factoring may be easier than we think (2016)

#126

Post by rasz » Sun, Jun 30, 2019, 10:36 PM UTC

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

you might enjoy "Travelling Salesman" 2012 ‧ Thriller/Drama ‧ 1h 20m

Re: Factoring may be easier than we think (2016)

#127

Post by Ar-Curunir » Sun, Jun 30, 2019, 10:36 PM UTC

vbezhenar wrote: post #110

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone. 2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip…

Factoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.

Re: Factoring may be easier than we think (2016)

#128

Post by Ar-Curunir » Sun, Jun 30, 2019, 10:37 PM UTC

rocqua wrote: post #119

jasonhansel wrote: post #63

Earlier quoted context omitted.

But what if you find an algorithm with a low asymptotic complexity, but with such a high constant factor that it could not be put into practical use? We would still want to move away from RSA (since constant factors can often be improved), but there would be no way to actually use the algorithm in its current form.

In that case, there is no immediate threat when publishing. Unless you area afraid someone else can improve on the constant factor, this won't break crypto.

Cryptography research moves very fast =)

Re: Factoring may be easier than we think (2016)

#129

Post by tuxxy » Sun, Jun 30, 2019, 10:38 PM UTC

vbezhenar wrote: post #110

waynecochran wrote: post #7

Imagine what you would do if you discovered how to factor efficiently? Think carefully. You now how the power to decrypt much of the world's banking and internet traffic and spoof certificates. There are forces in this world that would kill you to have this power. Would you publish your findings for everlasting fame? Would you sell it to the NSA for money (remember you can prove your power without releasing your algo…

1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone. 2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip…

Solving the discrete log problem would require that your factorization algorithm have the capability of being adapted to DLP. Some factorization algorithms can do this, but, IIRC, some cannot.

Re: Factoring may be easier than we think (2016)

#130

Post by JacksonGariety » Sun, Jun 30, 2019, 10:39 PM UTC

> Of course, I have no real evidence for my views...

> On the other hand, the people who talk about the great difficulty of factoring have equally little evidence...

This is a classic antinomy (paradox): one can argue indefinitely in either direction, because the question lies along the bounds of human reason (or so says Immanuel Kant).

The two sentences above, in themselves, provide a bit of evidence of the impossibility of solving the problem, and at the same time provide evidence for the possibility of handling this problem as a significant phenomenon of pure mathematics.

:)

EDIT: I mean only that the insolubility of the problem may itself be of mathematical use: it may (insofar as it is unsolvable, and insofar as it appears to be soluble) amount to a kind of 'anchor' for mathematics, a marker that indicates the boundary of the mathematical sciences, and that such a boundary would be of tremendous import to mathematicians and philosophers. Why is _this_ problem, _this_ problem specifically, unsolvable? (Rather than some other problem that has been solved?)

tl;dr The question of "why have we have trying to solve this problem for millennia?" is perhaps more significant for mathematics than the solution to the problem.