for those of you wondering if a client can check if the ufo perameters are actually being used, it was discussed in the irc2p channel:
(10:09:41 PM) yoyo: gnosis: can you explain in the wiki how you generated the raw numbezrs for UFO
(10:09:41 PM) yoyo: iirc you did the SHA on some number no?
(10:09:41 PM) yoyo: someon on reddit asked you also alincoln how to generate random number in a verifiable way
(10:09:41 PM) yoyo: I still dont know how you did choose the starting number for UFO
(10:09:41 PM) yoyo: it is very important to explain clearly where those number came from before factorization
(10:10:15 PM) Gnosis: I did it using the CHashWriter class which does double SHA-256 using the standard Bitcoin serialization method
(10:11:03 PM) Gnosis: hashing the number of UFO bits (3840) and the ufoIndex (non-negative integer identifying the UFO) and a 256-bit piece index
(10:11:33 PM) yoyo: how did you choose those input number?
(10:12:01 PM) Gnosis:
https://github.com/Anoncoin/anoncoin/blob/zc/src/zerocoin/ParamGeneration.cpp#L749(10:12:30 PM) Gnosis: out of all of these, the only slightly arbitrary choice is 3840 bits
(10:12:54 PM) Gnosis: because I noticed that Zerocoin performance got much slower when the modulus was bigger than that
(10:13:29 PM) Gnosis: so I picked 3840 because it was a multiple of 256 just smaller than where performance sharply degrades
(10:13:53 PM) yoyo: so the starting number are UFOindex and numbits? numbits = 3840?
(10:14:05 PM) Gnosis: numBits
(10:14:06 PM) Gnosis: yeah
(10:14:18 PM) yoyo: and UFOindex are 1-15?
(10:14:29 PM) Gnosis: you can compile the "ufo" program by "cd src/zerocoin && cmake . && make ufo"
(10:14:39 PM) Gnosis: that will spit out the ufo when given a ufoIndex
(10:15:01 PM) Gnosis: no, UFO index starts at 0
(10:15:39 PM) Gnosis: the way the UFO project was done, we started with indices from 0 through 12
(10:15:54 PM) Gnosis: small factors were continuously found
(10:16:12 PM) yoyo: ok hence with the prog if I input 0 and 3840 it will give the starting bignum after double sha that has factor in the table you posted about UFO?
(10:16:31 PM) Gnosis: when each factor was found, it would be removed from that UFO; if the resulting bit length was less than 90% of 3840, or if it was prime, then tht UFO was abandoned, and the next was picked
(10:17:10 PM) Gnosis: so we ended up with 13 UFOs as we started, with 0 through 15 except 5, 7, and 13
(10:17:17 PM) Gnosis: see the last image:
https://imgur.com/a/288U8(10:17:38 PM) abyss: how much comuputational power would be needed to crack the rsa-ufos
(10:18:13 PM) Gnosis: a lot
(10:18:23 PM) abyss: how much is a lot
(10:18:26 PM) Gnosis: hold on, typing longer answer:
(10:18:43 PM) yoyo: you said 8 year proc time, but say a megacomputer like deepblue or better could do how many year a day?
(10:19:03 PM) yoyo: thx gnjosis, it is clever way to generate ufo
(10:19:15 PM) yoyo: we shall explain it in wiki under trustless UFO imo
(10:19:36 PM) Gnosis: if we have a powerful attacker that can find factors by ECM up to 768 bits, and can do GNFS on numbers up to 2048 bits, then that attacker would have about a 0.2 chance of factoring each of the 13 UFOs
(10:20:36 PM) Gnosis: and about a 1 in a billion chance of factoring all, which is required to break our Zerocoin implementation
(10:20:41 PM) Gnosis: factoring 12 out of 13 is not enough
(10:20:51 PM) Gnosis: but
(10:21:06 PM) Gnosis: it's very unlikely that even the NSA would be as good as the above attacker
(10:21:08 PM) Gnosis: for years
(10:21:19 PM) Gnosis: it would take probably billions of dollars
(10:21:55 PM) abyss: so in a couple years we would adjust these to larger values?
(10:21:58 PM) Gnosis: plus improvements in hardware and algorithms
(10:22:07 PM) Gnosis: no
(10:22:13 PM) Gnosis: not a couple of years
(10:22:18 PM) Gnosis: it should be good for decades at least
(10:22:47 PM) yoyo: this 0.2 proba is it from your trial using montecarlo or is it from sanders?
(10:22:59 PM) Gnosis: yeah, my montecarlo simulation
(10:23:26 PM) yoyo: how do you know it scale the same when UFO bitsize grow up?
(10:23:57 PM) yoyo: you tried with smaller one, why bigger one would be same proba?
(10:24:00 PM) Gnosis: I scale all bits proportionally, and the probability is flat
(10:24:10 PM) yoyo: ok
(10:24:30 PM) yoyo: can you put that somewhere for review one day?
(10:24:36 PM) Gnosis: I got this idea because the Sander paper proved the probability is flat for a slightly different statement
(10:24:42 PM) yoyo: I trust this montecarlo better than a proof that i cannot understand
(10:24:52 PM) Gnosis: yes, we should
(10:24:54 PM) yoyo: but i dunno if it is standard practice in math
(10:25:12 PM) Gnosis: once ANC increases a lot in value, we should pool some to make a bounty for a mathematical proof
(10:25:17 PM) Gnosis: that puts some upper and lower bounds on the probability
(10:25:39 PM) Gnosis: I'm not good enough of a number theoretician to do that, sorry
(10:26:42 PM) Gnosis: also,
(10:27:30 PM) Gnosis: the reason why the Sander paper can be improved on (but not with proof, only Monte Carlo simulation, unfortunately) is because its definition of an unfactorizable number is too narrow
(10:27:53 PM) Gnosis: for large numbers, we have two algorithms that can be used: ECM and GNFS
(10:28:07 PM) Gnosis: ECM difficulty increases with the size of the factor to find
(10:28:20 PM) Gnosis: GNFS difficulty increases with the total size of the number
(10:29:24 PM) yoyo: ECM is what we did
(10:29:25 PM) yoyo:
(10:29:38 PM) Gnosis: the Sander paper might consider a number with three 768 bit factors to be insecure, when in fact it would be secure
(10:29:44 PM) Gnosis: yeah
(10:30:17 PM) Gnosis: the optimal strategy for an attacker is to do ECM to get all factors up to 768 bits; if the result is less than 2048 bits, then they can do GNFS
(10:31:31 PM) Gnosis: but in reality, the NSA probably can't find factors by ECM more than 350 bits, and probably can't factor numbers by GNFS greater than maybe 1300 bits
(10:32:12 PM) Gnosis: alright, I have to do some ZC work
(10:32:17 PM) Gnosis: if you ask questions, I'll see them later
(10:32:45 PM) Gnosis: somebody please update the RSA UFO wiki page with what I said
(10:33:02 PM) yoyo: thank you
(10:33:22 PM) abyss: yoyo do you have a wiki account
(10:34:45 PM) Gnosis: oh, one more thing: the purpose of the factorization we did in the RSA UFO project is to reduce the gap between what we know and what a powerful attacker (such as the NSA) knows, with regards to the factorization of the RSA UFOs we will use.