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

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

#151

Post by RyanAF7 » Mon, Jul 01, 2019, 3:44 AM 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…

This comment encapsulates the plot, events and a monologue of the movie Sneakers made in the early 90s.

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

#152

Post by alfiedotwtf » Mon, Jul 01, 2019, 3:58 AM UTC

macintux wrote: post #149

cgriswald wrote: post #24

Earlier quoted context omitted.

I doubt it, too; but using methods you've broken, but know others haven't, is a great way to convince people you haven't broken it either. And if you suspect they have, it's a great channel for misinformation.

You could also embed content with stronger security inside the wrapper you’ve broken, so even if someone else has figured it out, they can’t decrypt your real messages. Hopefully.

Nice

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

#153

Post by alfiedotwtf » Mon, Jul 01, 2019, 4:00 AM UTC

johndough wrote: post #137

est31 wrote: post #65

Earlier quoted context omitted.

https://eprint.iacr.org/2013/635.pdf > Boiling all water on the planet (including all starfish) amounts to about 2^24 lakes of Geneva and leads to global security: 114-bit symmetric cryptosystems, 228-bit cryptographic hashes, 2380-bit RSA. This needs to be done 16 thousand times to break AES-128, SHA-256, or 3064-bit RSA. I think this paper isn't using Landauer's bounds though, but conventional computers. So maybe m…

But why the starfish.

Because if you're already boiling the oceans, you probably won't have enough left over in the budget for marine conservation.

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

#154

Post by baby » Mon, Jul 01, 2019, 5:22 AM UTC

dvdkhlng wrote: post #148

phkahler wrote: post #146

Earlier quoted context omitted.

It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP. I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]). The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up fac…

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...

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

#155

Post by doubleunplussed » Mon, Jul 01, 2019, 5:45 AM UTC

scottlocklin wrote: post #116

daveFNbuck wrote: post #109

Earlier quoted context omitted.

Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?

BQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."

The qbits and unitaries don't have to be perfect - it's about how things scale when you add qbits. Quantum error correction shows that you can add more qbits to make up for imperfection, and still be left with a quantum computer, i. e. the imperfection hasn't demoted the thing to a classical computer.

Of course they haven't built one yet, but none of the difficulties encountered so far have involved discovering new physics, which is what you would need to do to rule out quantum computers since the laws of physics as currently understood permit them.

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

#156

Post by Ar-Curunir » Mon, Jul 01, 2019, 7:20 AM UTC

baby wrote: post #154

dvdkhlng wrote: post #148

Earlier quoted context omitted.

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP. I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]). The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up fac…

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...

That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.

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

#157

Post by Ar-Curunir » Mon, Jul 01, 2019, 7:22 AM UTC

phkahler wrote: post #146

Ar-Curunir wrote: post #127

Earlier quoted context omitted.

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

It's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.

They are equivalent (with some caveats) when considering the multiplicative subgroup Z_N where N is a composite. Bitcoin relies on DLP over elliptic curve groups.

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

#158

Post by dvdkhlng » Mon, Jul 01, 2019, 8:15 AM UTC

baby wrote: post #154

dvdkhlng wrote: post #148

Earlier quoted context omitted.

It's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP. I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]). The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up fac…

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...

I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength.

The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor:

* fastest known method for DLP is O(exp(c sqrt(log n log log n)))

* 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n"

Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply.

See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered".

[1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...

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

#159

Post by nabla9 » Mon, Jul 01, 2019, 9:50 AM UTC

scottlocklin wrote: post #116

daveFNbuck wrote: post #109

Earlier quoted context omitted.

Which statement are you saying demonstrates why people shouldn't take quantum complexity theory seriously?

BQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."

The problem here is that you just state something that looks like strong personal opinion. You vaguely refer to serious people.

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

#160

Post by scottlocklin » Mon, Jul 01, 2019, 1:49 PM UTC

daveFNbuck wrote: post #142

scottlocklin wrote: post #116

Earlier quoted context omitted.

BQP doesn't exist: there are no quantum computers. Saying BQP is like saying "magic fairy dust perfect unitary transformers that effectively encode a perfect complex number in the same sense a protractor theoretically can solve NP-complete problems by encoding real numbers."

So we shouldn't take research into things that don't exist yet seriously?

Designing algorithms for a computer architecture that assumes matter behaves in a fairly trivially unphysical way sure seems like a glass bead game to me. Especially considering the hype and baloney around this particular one. There are zero actual quantum computer designs (aka error corrected and capable of factoring large or even small integers into primes) under construction: but everyone runs around like chicken little declaring the sky is falling.

I went to a Gordon conference on this subject in the 1990s; as far as I can tell, there has been zero progress in the topic since then. Sure are a lot of press releases though!