01:47:01 <moneromooo> If QQ is back, the current code is in https://github.com/moneromooo-monero/bitmonero/tree/clsag
01:47:26 <moneromooo> sarang: this will be what should be reviewed, it's just the CLSAG changes.
14:48:34 <sarang> Hello all
14:49:05 <SerHack> hi
15:00:31 <suraeNoether> good morning; sarang, i'm finishing up some notes on LRS security definitions to pass along to you. this is indept of the CLSAG notes, which i have *some* of but i'm going through the paper line by line before sending it along
15:01:00 <sarang> Sounds goods; thanks suraeNoether
15:01:23 <suraeNoether> sarang some previous papers have called what you call unframeability a few different things but I think non-slanderable is possibly one of the more accurate terms
15:01:40 <sarang> I'm cleaning up and testing some simplifications suggested for the CLSAG code, and chasing some performance numbers in the meantime
15:01:53 <sarang> Yeah that term has been used as well
15:01:59 <suraeNoether> was there a logic in using "unframeability"? or is there a subtle difference between non-slanderability from Tsang's 2004 separable paper and our def that i'm missing?
15:02:03 <sarang> The security games are all different for them anyway
15:02:15 <suraeNoether> that's my question... hold on let me pull this up
15:02:17 <sarang> Based on what signatures you can obtain, etc.
15:02:47 <suraeNoether> tsang's paper is annoying because it's for event-oriented threshold ring sigs, not signing-key-oriented usual ring sigs
15:02:47 <sarang> I'm happy with any definition that prohibits an adversary from choosing an honest key and linking with it, subject to suitable oracle access
15:02:56 <suraeNoether> but the security model i think is similar to what you are going for
15:03:02 <suraeNoether> ^ * gotcha
15:03:14 <suraeNoether> but let me continue probing the differences with you briefly
15:03:25 <suraeNoether> https://eprint.iacr.org/2004/267
15:04:14 <suraeNoether> okay so in that paper on page 9 we have their game-theoretic definition of non-slander
15:04:16 <sarang> The Liu version doesn't really work IMO since it assumes both the target key signature and the adversarial signature are honestly generated
15:04:30 <sarang> and doesn't make clear what other information (e.g. oracles) the adversary can see
15:04:44 <suraeNoether> agreed
15:05:48 <suraeNoether> now: here's my version of that definition for our purposes; i don't specify the orientation of key images and it's just a usual LRS, not threshold
15:05:58 <suraeNoether> https://www.irccloud.com/pastebin/z90qGrvR/
15:06:03 <suraeNoether> enjoy the latex
15:06:21 <suraeNoether> now let me dig up your definition of unframeability
15:07:29 <sarang> p 12 of the reorg overleaf version
15:07:29 <suraeNoether> here is your definition of non-frameability https://www.irccloud.com/pastebin/zL8X3cmW/
15:08:15 <suraeNoether> (in my draft i'm neglecting things like number of oracle queries and time constraints on solvers until i have the majority of the definitions down correctly)
15:08:31 <sarang> Sure
15:08:32 <suraeNoether> btw TWCALW non-slanderability is that tsang paper from iacr i just linked
15:09:42 <suraeNoether> hmm so immediate thing pops out at me
15:09:49 <suraeNoether> corruption in your definition of non-frameability
15:10:04 <sarang> How so?
15:10:48 <suraeNoether> it looks to me like corruption oracle access isn't a success condition for yours; an adversary can corrupt the target key after asking for the oracle'd signature \sigma
15:11:49 <suraeNoether> but that appears to be the only practical difference between your definition of non-frameability and my attempt at describing the twcalw non-slanderability game (which admittedly does involve translating from the tsang paper's setting to our setting, but that's not a challenge here imo)
15:12:14 <suraeNoether> which is a good thing
15:12:42 <sarang> Ah, there should be a condition on that key corruption
15:13:02 <sarang> Otherwise the adversary could just sign, of course
15:13:14 <suraeNoether> similar thing happened to me about unforgeability recently :P
15:13:27 <sarang> good catch
15:13:29 <suraeNoether> i was allowing the adversary to win by rolling their own keys and constructing a fair signature with them
15:13:44 <suraeNoether> i was up at 4am today thinking about whether we can eliminate the need for all the keys in both rings in non-slander to be challenge keys, so as to allow adversarially selected ring members...
15:13:45 <sarang> (I'll likely need to update Triptych for that as well, but it shouldn't affect its proof or validity)
15:14:27 <suraeNoether> but we would need some way of ensuring the signatures *were* computed from some challenge ring members, even if some other ring members are adversarially computed
15:15:22 <sarang> Well, as a related example, I can't think of any solid unforgeability definitions (not counting linkability at all) that don't fully restrict the ring for this reason
15:15:36 <sarang> Otherwise the challenger can't detect if the adversary rolled a keypair and used it honestly
15:15:38 <suraeNoether> so, actually, i think i have that problem solved
15:15:46 <sarang> Using linkability in particular?
15:15:48 <suraeNoether> due to our linkability
15:15:49 <suraeNoether> yep
15:15:56 <suraeNoether> it actually is something like this
15:16:02 <sarang> (I'm referring to linkability-free signatures, just as an example of restricting malicious keys)
15:16:21 <suraeNoether> "weaken your definition of unforgeability, but then tack on linkability and non-slanderability, and you get a definition of unforgeability stronger than all previous definitions."
15:17:24 <suraeNoether> so i started thinking about extractors that could rewind a signer... if the signer outputs two linked signatures with two rings with some adversarially selected members, i think an extractor exists that can: place the signer in a black box, manage and record it's oracle queries, and then rewind the signer as many times as necessary to extract a proof that the adversarially selected ring members aren't
15:17:24 <suraeNoether> being used to compute the signature
15:18:17 <suraeNoether> that *would* relax the requirements of non-slanderability, but formalizing it and proving it may be... an unnecessary rabbit hole for right now
15:19:23 <suraeNoether> okay, sarang: thanks for chatting with me about this, I think I have enough of what I need right now to provide notes to you on CLSAG real soon, and now I can de-prioritize my tech note on LRS security until that's done
15:19:26 * suraeNoether switches gears
15:24:22 <sarang> :D
15:24:42 <sarang> I shall continue with CLSAG code performance testing then
15:58:30 <suraeNoether> sarang, a thought occurred to me
15:58:38 <sarang> k
15:58:56 <suraeNoether> this is for the general LRS security paper, but it's relevant to CLSAG
15:59:22 <suraeNoether> for one thing, d-CLSAG is still a linkable ring signature scheme that satisfies some definition of linkability when linking occurs by matching *all* of the key images instead of just the first one
15:59:37 <sarang> Yep
15:59:44 <suraeNoether> our scheme can be described as using the full linkability version as a sub-scheme, and merely discarding some of the linkability criteria
16:00:19 <suraeNoether> so i think that formally we should prove first the linkability using all key images, and then show that we don't lose linkability with respect to some model by discarding some of the linkability criteria
16:00:24 <suraeNoether> the reason i think this is important is the following
16:00:45 <sarang> Yeah, it's still a bit asymmetric by using a single base across all linking tags (from the linking component)
16:01:31 <suraeNoether> that is true, but is also pretty specific to our implementation and the LRS paper i'm writing is very implementation agnostic at this point.
16:02:23 <suraeNoether> but... all of my concerns about making sure that the key image being published actually corresponds to the amounts being opened go away if 1) the LRS scheme is linkable when looking at all key images, and 2) we merely discard some of the linkability criteria. i *think*
16:03:11 <suraeNoether> moreover, there seems to be a new security definition here that is bugging me
16:04:13 <suraeNoether> which is this: in all of our real-life applications with confidential transactions, some of the keys being used are adversarially selected. That is to say, modeling everything by taking (sk, pk) <- KEYGEN doesn't capture the fact that *most* of the secret key is adversarially generated.
16:04:15 <sarang> Would that discount the possibility of an adversary unable to link using all tags, but able to link using the single tag that really matters?
16:04:29 <suraeNoether> i'm not sure yet
16:05:06 <suraeNoether> the security model here gets really delicate
16:05:59 <suraeNoether> this would have to be a lemma to be proven in the course of proving that discarding linking tags is harmless
16:06:31 <suraeNoether> i feel like our definitions of unforgeability, for example, should allow the adversary to select the non-linking keys!
16:07:16 <suraeNoether> that is, instead of generating a big space of private and public keys and sending just the public keys to A, just generate the *linking coordinates* of these keys and let A fill in the amount coordinates
16:07:22 <suraeNoether> and i feel like a lot of our definitions need to take this into account
16:07:31 <suraeNoether> but i also know that no paper has done that before
16:07:40 <suraeNoether> and that it may be unnecessary? i'm not sure
16:08:56 <suraeNoether> but it feels like our security models should assume that, other than the linking key coord, the rest of the keys could be adversarially selected
16:10:22 <suraeNoether> anwyay, back to notes
16:28:00 <sarang> If linkability accounts specifically for the single-component tag, what's wrong with just assuming that auxiliary tags are structurally no different than other signature components?
16:28:24 <sarang> They exist only for the algebra, like other signature elements
16:37:26 <sgp_> The Monero Konferenco CFP is now open. Please submit your ideas and encourage others to submit theirs! https://monerokon.com/cfp/
16:45:11 <sarang> sgp_: "preference may be given too lower-cost travel" typo
16:47:34 <midipoet> good spot
16:56:00 <sgp_> sarang: thanks, fixed :)
17:38:10 <suraeNoether> sarang: our unforgeability definition implies non-frameability, and our definition of non-frameability is *really really close* to our definition of unforgeability; if unforgeability is restricted to lose the "adversarially selected keys" property, they are equivalent.
17:39:47 <suraeNoether> sarang: If linkability accounts specifically for the single-component tag, what's wrong with just assuming that auxiliary tags are structurally no different than other signature components? <--- i'm not sure if there's anything wrong with it. but i haven't seen a proof either way, and it's not immediately obvious
17:40:15 <suraeNoether> excuse me, i'm being sloppy with my language
17:40:29 <suraeNoether> let me be a lot more precise because "our" definition of unforgeability needs to be updated
17:41:00 <suraeNoether> okay, so define unforgeability almost exactly as in reorg.tex except change the linking tag requirement to the following statement
17:44:20 <suraeNoether> there exists a challenge key \textbf{pk}_i in \textbf{\underline{pk}}^\prime such that \textbf{pk}_i has not been corrupted and for any message m^*, any ring \textbf{\underline{pk}}^*, if  this challenge key \textbf{pk}_i is in ring \textbf{\underline{pk}}^* at index l^*, then Link((m, \textbf{\underline{pk}}^\prime, \sigma), (m^*, \textbf{\underline{pk}}^*, l^*)) = 1
17:44:46 <suraeNoether> and modifying this definition so that the ring of public keys need not be a subset of the challenge keys (only the linked key needs to be a challenge key)
17:45:08 <suraeNoether> for *this* definition of unforgeability, the definition of non-slanderability follows
17:45:37 <suraeNoether> non-slanderability/non-frameability, however, does not imply unforgeability but *only because* our definition of non-frameability requires all ring members be challenge keys, but unforgeability relaxed this
17:46:18 <suraeNoether> this is of course exactly what we wanted unforgeability to capture: the inability to construct a valid non-oracle signature that links to someone else's honestly generated key
17:48:02 <suraeNoether> by the way, i didn't really believe that non-slanderability implied so much of unforgeability until i saw the proof, so if you want me to elaborate on that, it was a bit of a surprise to me.
18:56:21 <suraeNoether> sarang, i'm going to make a new rereorg.text and then share it with you.
18:56:49 <sarang> OK, or edit directly if that's cleaner
18:58:07 <suraeNoether> meh.
18:58:17 <suraeNoether> also, gotta dip out in an hour but i'll be back after
19:02:36 <sarang> OK, let me know when you're done
19:37:37 <UkoeHB_> thinking about the gamma distribution for decoy selection; in my simple brain it's a fixed distribution over [0,1], a number is selected randomly from that distribution and gets multiplied by the total number of outputs; this implies as more outputs accumulate (e.g. doubles), the age spread of chosen decoys changes (e.g. widens by ~2x); is my story accurate? I reached a dead end trying to read the code
19:39:24 <sarang> Here is some sample code showing different selection mechanisms that were under consideration: https://github.com/SarangNoether/skunkworks/tree/outputs/outputs
19:39:44 <sarang> `lineup` is the idea that was deployed
19:40:20 <sarang> It was found to be reasonably robust against different possible chain conditions, while doing a good job with weighting within blocks
19:40:47 <sarang> The tricky part is that outputs don't have a timestamp beyond the block timestamp
19:41:04 <sarang> and for extreme chain conditions that, coupled with the fact that empty blocks exist, can throw off the selection
19:48:07 <UkoeHB_> ok I think I understand that part; an example for a thousand words; say the blockchain is 1yr old, and the gamma distribution will pick ~90% of decoys from the past 10 days; 1yr from now, when the chain is 2yr old, will the gamma distribution now pick ~90% from the past _20_ days?
19:48:35 <sarang> The timing parameters for the distribution are fixed
19:49:13 <sarang> A fixed time window is used to derive an "average output time" from the output/block density and the block target times
19:49:27 <sarang> This is the time used for the exp-gamma selection
19:50:07 <sarang> after which a shuffle is performed within the block of the chosen output (to account for the fact that all outputs in the  block have the same time, and could have been adversarially packed by the miner)
19:50:28 <sarang> The distribution timing from Miller et al. was found to change very little over time
19:51:27 <sarang> So the answer to your question is "the distribution doesn't change purely based on the length of the chain"
19:51:57 <sarang> what affects it is the average output timing, which is taken over a reasonably long period to avoid short-term "feast or famine" conditions, which can throw off the selection
19:52:04 <UkoeHB_> well take a friendly assumption like constant output emission
19:52:06 <sarang> (but not as much as some other possible selection methods)
19:54:42 <sarang> The windowed average output timing is intended to smooth out the effects of non-constant output density
19:55:00 <sarang> You can model different chain conditions using that simulator, or write your own, or supply your own chain data
19:55:17 <UkoeHB_> yeah that part is clear
19:56:02 <sarang> Ok
19:59:18 <UkoeHB_> so (assuming constant output emission) decoys will have nearly the same average age no matter how long the chain gets (within human lifetime)? or more precisely, the same median age?
20:00:06 <sarang> This was found to be in line with Miller et al.'s analysis
20:00:33 <sarang> Which examined spend snapshots of chain data
20:00:51 <sarang> and compared with true-spend Monero data where available
20:01:53 <sarang> If your conclusion is "this selection method is suboptimal" then yes, it is
20:02:06 <sarang> Ideally we'd account for as many aspects of spend behavior as possible
20:02:29 <sarang> Made more challenging by the fact that true spend behavior is in general not known for the Monero chain
20:02:37 <UkoeHB_> Im more worried it wont age well
20:02:52 <sarang> All we can reasonably do is compare to known chain data, which is what Miller et al. did
20:03:08 <sarang> Revisiting the analysis at some point (I'm not saying right now) would be a good idea
20:03:50 <sarang> A user spending a very, very, very old output who is concerned about the distribution (should it never change) can always perform a self-spend to return the output to the "recent pool" first
20:12:57 <UkoeHB_> ok
20:44:48 <sarang> That's one spot where binning, if done right, could help
20:45:29 <sarang> Since even if you identify the bin containing the likely spend (due to age), you still have ambiguity (barring other information like cross-ring comparisons, etc.)
23:33:19 <suraeNoether> sarang: backe's linkability and tsang's linkability are not directly comparable. in the sense that an algo that can solve one can't always be turned into an algo that can solve the other. however, tsang's linkability, with certain ring size constraints imposed, *does* imply backe's linkability via induction. without those ring size constraints, the two notions are actually distinct, although the proofs
23:33:19 <suraeNoether> of each will be very similar.
23:33:37 <suraeNoether> so i think we'll need to prove both (not a big deal)
23:33:38 <suraeNoether> brb