13:59:47 <monerobull[m]> https://www.reddit.com/r/Monero/comments/134jbdt/security_advisory_new_attack_from_malicious/
13:59:55 <monerobull[m]> Is this just fud?
14:03:09 <ofrnxmr[m]> Thats from tevador
14:03:12 <ofrnxmr[m]> Not fud
17:24:02 <DiegoSalazar[m]> Ok so we looked at the updated preprint
17:24:26 <DiegoSalazar[m]> And unfortunately this is difficult to estimate how much time it will take. 
17:25:16 <DiegoSalazar[m]> On first read of the updated preprint, there appear to be areas where they generically offload parts of arguments
17:26:03 <DiegoSalazar[m]> So we have a couple of options here. 
17:26:52 <DiegoSalazar[m]> We can do a partial audit, in the sense that we assume offloaded arguments are safe and correct, and proceed with those assumptions. 
17:27:10 <DiegoSalazar[m]> Or a full one wherein we go and check each of these offloaded arguments which would be a non-trivial effort. 
17:27:40 <UkoeHB> Are the offloaded arguments unconventional/new?
17:29:36 <DiegoSalazar[m]> It is certainly possible to do such a partial audit. And while overall safety can never be guaranteed, in such a case it can _absolutely_ not be guaranteed. And there is a possibility that this nuance would be lost to most. And we predict there would be several areas in the audit whose conclusions would end up being "we are not fully confident in the correctness of this argument or line of reasoning"
17:31:50 <UkoeHB> A full audit would be necessary in the long run
17:32:15 <Rucknium[m]> What do you mean by "offload"? Maybe the full arguments are in the unreleased "full" version: https://libera.monerologs.net/monero-research-lab/20230419#c238808
17:54:56 <DiegoSalazar[m]> So maybe we wait to see the full version then?
17:57:09 <Rucknium[m]> Everyone complains about page limits with these conferences. Haven't they figured out appendices yet? 😑
18:00:03 <UkoeHB> DiegoSalazar[m]: did you mean the offloaded arguments have not been written yet?
18:22:54 <UkoeHB> yeah let's wait until the full paper is available
22:47:44 <kayabanerve[m]> What's the time complexity of the multisig?
22:48:14 <kayabanerve[m]> O(n!) ? O(n(n+1) / 2) ?
22:48:23 <kayabanerve[m]> I assume UkoeHB is the best to answer
22:48:43 <kayabanerve[m]> *where n is the amount of missing participants
22:50:54 <kayabanerve[m]> ... well, that defines each sign round as 1, where each sign round is O(n) to amount of participants... 
22:53:58 <UkoeHB> 'the multisig'?
22:59:30 <kayabanerve[m]> The multisig implementation in the Monero codebase
23:07:01 <kayabanerve[m]> It looks like O(n) sign, with key gen being the issue
23:11:19 <UkoeHB> the implemented signing is also O(n) since it's round robin
23:11:25 <UkoeHB> or O(M) I guess
23:12:03 <UkoeHB> key gen is O(N - M + 1)
23:12:57 <kayabanerve[m]> UkoeHB: I see it does t rounds, yet what's the complexity of reach round?
23:13:30 <kayabanerve[m]> *each. Is each round n**2? There's no way this is linear.
23:14:49 <UkoeHB> key gen is not time-linear per round but signing is time-linear (but not space-linear since you are accumulating partial sigs)
23:15:30 <UkoeHB> well hmm maybe not
23:16:15 <UkoeHB> it's some n choose k complexity..
23:16:35 <kayabanerve[m]> Right. I see key gen does t rounds. In each round, it does n ecdhs.
23:17:36 <kayabanerve[m]> But it can't be n**2 as that wouldn't be so inperformant. It has to be doing n**2 ecdhs, or relevant to the n choose k function which I'm still interpreting
23:20:54 <UkoeHB> are you talking about key gen or signing now?
23:21:41 <kayabanerve[m]> Key gen. Sorry for any confusion. I do believe signing is O(n), but I'll take contradictions.
23:22:47 <kayabanerve[m]> Key gen appears to do n-t+1 rounds, where each round is an ECDH involving n*round_num keys. I believe it's cubic accordingly.
23:22:49 <UkoeHB> key gen requires an n choose k pyramid
23:23:19 <UkoeHB> the most complex round is round N - N/2
23:23:56 <kayabanerve[m]> Overtly simplified, it's n**3, right?
23:25:10 <UkoeHB> well N-of-N requires no ecdh, N-1 of N requires N-1 ecdh, N-2 of N requires.. something
23:25:36 <kayabanerve[m]> Where it's actually
23:25:36 <kayabanerve[m]> N-T rounds
23:25:36 <kayabanerve[m]> round_num * n pieces of data
23:25:36 <kayabanerve[m]> For an actual run time of (n-t+1) * ((n-t/2)+1) * n, I think
23:25:54 <kayabanerve[m]> For n-of-n, that evaluates to 1 * 1 * n
23:26:52 <UkoeHB> https://github.com/monero-project/monero/blob/a2e8d1d4271df1591786b8d92516455488ee82fd/src/multisig/multisig_account_kex_impl.cpp#L513
23:28:01 <kayabanerve[m]> I'm just looking for a rough complexity to include in a list of details. I'm not going for an academic publication :p If that formula looks right, I'm fine handwaving it as cubic.
23:28:06 <kayabanerve[m]> ... ` n! / (k!(n-k)!)`
23:28:07 <kayabanerve[m]> Oh god
23:28:17 <kayabanerve[m]> That's what the boost function returns
23:28:41 <kayabanerve[m]> Signers! / (round!(signers-round)!)
23:28:52 <UkoeHB> boost function?
23:29:20 <kayabanerve[m]> The lambda internally calls boost::math
23:29:39 <kayabanerve[m]> boost::math documents its binomial coefficient function as following the above formula
23:29:58 <UkoeHB> well that's the standard formula yep
23:31:12 <kayabanerve[m]> Tens of thousands of elements 0_o
23:31:20 <kayabanerve[m]> Thanks for helping me piece it together
23:31:22 <UkoeHB> I guess complexity would be the largest round
23:32:30 <UkoeHB> that's why I hardcoded a limit of 16 group members
23:32:44 <kayabanerve[m]> Yep. I get that
23:32:59 <kayabanerve[m]> Thanks again for the help :)
23:33:05 <UkoeHB> sure :)