Originally published at: http://boingboing.net/2017/07/18/i-know-nothink.html
…
2 Likes
Nope. Couldn’t even hack page 1.
Yeah. I’m confused. It would seem that knowing two arbitrary numbers p and q, and multiplying them together to produce x (a 2048 bit number) merely demonstrates that you can multiply two specific numbers (of the correct magnitude) together to produce x.
whereas the problem eventually needs to demonstrate that x is arbitrary, n is 2048, and p and q are unknowns. But since i don’t know about zero knowledge, I can’t evaluate whether the first step (merely the first) is a step in the right direction.
Because of the Lewis Carroll allusion, I was expecting the puzzles to be whimsically written. I guess not every mathematical puzzler wants to follow Raymond Smullyan’s example. Too bad.
1 Like
No, I think the trick is factoring. (I get this much, at least.) Any transistor can multiply. But you can only factor a large number if you already have one of the factors. That’s the proof.
You can answer anything you want to advance onto the next stage. So I already know that my assertion is correct.
Perhaps I should explain.
The claim is that “a secret algorithm exists that can factor 2048 bit numbers.”
The proposed proof is
Alice will provide a 2048 bit number, and Alice will factor it, thus demonstrating that the algorithm works.
But there are many 2048 bit semiprimes whose factors are already known (my addled brain says ‘multiply two 1024 bit prime numbers together’, discard if they overflow). If Alice multiplies two numbers together to produce a 2048 bit number, and then provides the factors, all Alice has proven is that she remembers the original factors. To truly demonstrate that her algorithm works, Bob must provide the semiprime, and Alice must provide the original factors. If Alice does so, she will have proven that her algorithm works; without necessarily disclosing the nature of that algorithm to the world.
1 Like
This topic was automatically closed after 5 days. New replies are no longer allowed.
