12:37:06 <sarang> Hello all; research meeting today is at 17:00 UTC
16:30:00 <sgp_> suraeNoether: check Wire after the meeting
16:32:10 <sgp_> Everyone reading into this - no, not a security issue :)
16:56:09 <sarang> Meeting begins in about 5 minutes
16:58:28 <sarang> ping suraeNoether
16:58:45 <sarang> The usual agenda: https://github.com/monero-project/meta/issues/417
16:59:02 <suraeNoether> howdy everyone
16:59:53 <sarang> Hi
17:00:03 <sarang> Let's go ahead and get started with GREETINGS
17:01:00 <kinghat> o/
17:01:02 * suraeNoether waves
17:01:05 <sgp_> hello
17:02:25 * sarang waits a few minutes for others
17:05:08 <sarang> That's long enough!
17:05:24 <sarang> Let's move to ROUNDTABLE
17:05:28 <sarang> suraeNoether: what up with you
17:06:09 <suraeNoether> i'm terribly ill this morning, so my update will be very brief.  my work in this past week has involved three incomplete tasks:
17:06:38 <suraeNoether> 1) CLSAG linkable anonymity proof required some thought. sarang and i have thought about it and we have a strategy to finish writing the proof. sarang: do you want to make the changes to our LA definition or do you want i should?
17:07:03 <sarang> suraeNoether: I have a writeup for LA in my notebook that I'm transcribing to TeX
17:07:06 <suraeNoether> and proof* not just the definition
17:07:09 <sarang> it works just fine
17:07:14 <sarang> On that note
17:07:24 <sarang> Do you have any thoughts on linkability (not LA)
17:07:32 <sarang> I don't particularly like the Backes definition
17:07:44 <suraeNoether> uh one sec
17:07:56 <sarang> Triptych has a version of linkability+non-frameability that I like better
17:08:00 <suraeNoether> is there soemthing wrong with the definition we proposed initially?
17:08:17 <suraeNoether> iirc that one's from bender
17:08:28 <sarang> It's not formalized quite enough, in the apparent opinion of the reviewer
17:08:34 <sarang> I think it needs just minor work
17:08:41 <sarang> Triptych formalizes it a tad more IMO
17:09:07 <sarang> I can add that to the writeup if you like
17:10:01 <suraeNoether> well
17:10:25 <suraeNoether> for the sake of the audience, can you describe the 3 different definitions you want to consider? or 2, assuming you want to bail on backes'
17:11:05 <sarang> Backes requires the following for an LRS: completeness, linkable anonymity, linkability, non-frameability
17:11:20 <sarang> Right now we combine linkability and non-frameability with non-standard terminology
17:11:44 <sarang> Backes uses a particular linkability definition: can the adversary use `q` keys to generate `q+1` non-linking signatures?
17:11:56 <sarang> Where `q` is scaled via the security parameter
17:12:40 <sarang> I don't particularly like this definition over the "usual" one about producing two linking signatures, but I think it's important to frame the definition as a challenger-player interaction
17:12:46 <sarang> Our current method does this very informally
17:13:41 <sarang> I propose a combined linkability definition in my Triptych writeup that's a slight formalization of what CLSAG has now
17:13:59 <sarang> (it could easily be split into linkability and non-frameability)
17:14:08 <suraeNoether> hmmmm q scaling with the security parameter is the weird part to me: if the security parameter goes up, so does q... and so this means, for example, the adversary can't produce 3 signatures using 2 keys without some linking occurring. this feels *weaker* than the statement "can't produce two signatures using the same key without them being linked"
17:14:19 <sarang> Yeah, which is why I don't really like it
17:14:29 <sarang> didn't sit well with me
17:14:36 <suraeNoether> and we want the property with q=1 anyway to prevent double-spending
17:14:48 <sarang> So I am proposing not using the Backes definition, but simply formalizing what we have now, a la Triptych
17:14:59 <sarang> then it's more clear what the linkability player has access to in terms of keys etc.
17:15:09 <suraeNoether> okay, i'm going to read more deeply into that this afternoon
17:15:20 <sarang> IMO it's a pretty straightforward formalization
17:15:28 <sarang> doesn't affect much in practice
17:16:03 <suraeNoether> backes' definition with q=1 seems to me to imply backes' definition with greater q, but it's possible that it doesn't technically reduce the way it seems. i'll think more about it
17:16:25 <sarang> That definition doesn't make assumptions about linking tags being equal AFAICT
17:16:33 <sarang> Whereas ours does
17:16:38 <sarang> I think that's part of it
17:17:10 <sarang> Anyway, you were talking about work you'd been doing, before I barged in =p
17:17:32 <suraeNoether> moving along, my next incomplete task is reviewing triptych's security proofs more deeply, which dovetails with this :P
17:17:40 <sarang> Yeah, a nice tie-in
17:18:11 <suraeNoether> finally, i'm working on matching simulations today. i'm experiencing a data management and presentation issue, but i hope for the end of the day a nice graph displaying performance of Eve as a function of ring size and churn length
17:18:20 <sarang> Nice!
17:18:27 <suraeNoether> this will come along with a push to my repo with all the code used to generate that, and explanations so people can replicate it
17:19:20 <sarang> word
17:19:45 <suraeNoether> that's it, if i had presented in the other order then your "barging" would have been a great segue into *your* work for the week :P
17:20:01 <sarang> We can pretend otherwise
17:20:16 <sarang> I have completed a draft of the Triptych preprint, which is now in suraeNoether's hands
17:20:17 <sgp_> suraeNoether: I'm really looking forward to that chart
17:20:29 <sarang> it includes my proposed linkability+non-frameability definition
17:20:54 <sarang> Figured out the CLSAG linkable anonymity definition, which is not as strong as Backes, but does the job IMO
17:21:26 <sarang> I've also been working with Aram from Zcoin on some related Groth proving system stuff
17:21:44 <sgp_> what's the shortfall on the linkable anonymity definition, even if there's no practical difference?
17:21:45 <sarang> There will be a neat paper coming out from them on that shortly, which they graciously provided to me in advance
17:22:02 <sarang> sgp_: Backes permits key corruption, which doesn't work with our DDH hardness assumption
17:22:10 <sarang> Instead, we assume the adversary can obtain key images
17:22:22 <sarang> And that the adversary can pack rings with their own malicious keys
17:22:24 <sgp_> sarang: thanks
17:22:31 <sarang> (which you can assume are trivially corrupted)
17:23:01 <sarang> This is already stronger than the existing definition that was used
17:23:42 <sarang> Otherwise, I also wish to update the DLSAG paper (which will appear next year in conference proceedings) with the CLSAG security model, since they are structurally extremely similar
17:24:22 <sarang> So overall, a lot of tedious (but still interesting) stuff involving formal definitions and proofs
17:24:42 <sarang> When suraeNoether finishes his review of the Triptych preprint, it'll go to the IACR archive
17:24:50 <sarang> and presumably any CLSAG/DLSAG updates as well
17:25:28 <suraeNoether> hmm Backes' linkability definition is a puzzle i have very little intuition about: should it be harder or easier to present 2 signatures from the same key without linking the signatures than it should be to present 201 signatures from 200 different keys without any of them linking? *taps chin*
17:25:52 <sarang> The adversary picks which keys IIRC, right?
17:26:12 <suraeNoether> yeah, adversary can use KeyGen or any other way of selecting the verification keys
17:26:24 <suraeNoether> may not even know the secret key, so it's genuinely adversarial
17:26:28 <sarang> ya
17:27:00 <sarang> The adversarial generation isn't really a big deal, since soundness implies the adversary's choice of keys satisfy the verification equations
17:27:16 <sarang> and then you rely on the one-way mapping
17:27:28 <suraeNoether> actually, it's not clear; each verification key needs to be in \mathcal{VK}, and it's not specified where that comes from, i'm assuming from the challenger
17:28:03 <suraeNoether> in which case the adversary has to pick challenge keys to break linkability, it's not enough for the adversary to pack all rings with fake pubkeys
17:28:06 <sarang> Backes even notes that generating `q` such signatures is trivial, since you simply use separate keys
17:28:21 <sarang> Fake pubkeys should be acceptable
17:28:42 <sarang> since the adversary does all this offline, or otherwise generates the pubkeys in its own (seemingly) valid transactions
17:29:40 <sarang> The `q=1` case feels like some kind of targeted linking attack, where the general `q` case seems like a broader "hope for a collision somewhere" attack
17:30:25 <sarang> suraeNoether: thoughts?
17:31:47 <suraeNoether> nothing concrete. the way this definition is written feels very very counter-intuitive to the way you and i have discussed linkability in the past.
17:32:18 <sarang> Yeah, and I haven't seen it anywhere else
17:32:30 <sarang> Again, I don't feel any particular need to use it
17:32:45 <sarang> But getting the existing definition more formalized in a challenger-player sense seems wise
17:33:00 <suraeNoether> agreed
17:33:03 <sarang> roger
17:33:10 <sarang> OK, that's my update
17:33:23 <sarang> Does anyone else have interesting (or uninteresting) research to share?
17:33:23 <suraeNoether> ok, dude, i think i know the problem here
17:33:27 <suraeNoether> with that definition
17:33:31 <suraeNoether> or at least my problem with it
17:33:31 <sarang> Ooh, go on
17:33:35 * sarang takes a step back
17:34:03 <suraeNoether> linkability is a property that has a "correctness" component and a "soundness" component. to correctly link two things means to link them when they should be linked. to soundly link two things is to *only* link them when they should be linked
17:34:18 <suraeNoether> you called this positive and negative linkability at some point
17:34:31 <suraeNoether> i feel like this definition is mashing the two together
17:34:37 <suraeNoether> or attempting to
17:34:46 <suraeNoether> anyway, my thoughts don't go deeper than that yet
17:34:59 <sarang> Backes uses non-frameability to show that you can't make signatures that _appear_ to link without knowing/using the same key
17:35:17 <sarang> and linkability to mean that you can't make sigs with the same key(s) but different tag(s)
17:35:32 <sarang> The reviewer didn't like the CLSAG paper's use of positive/negative/soundness in linkability
17:36:12 <suraeNoether> hmm
17:36:16 <suraeNoether> okay, that's going to require more thought
17:36:18 <suraeNoether> anywya, now i'm done. :P
17:36:33 <sarang> A lot of this is simply getting the right terminology for the definition(s) of choice
17:36:45 <sarang> I happen to like using linkability to refer to both
17:36:53 <sarang> since that's typically what you want
17:36:59 <sarang> but it's two different concepts
17:37:11 <sarang> OK, we can move on to any other research
17:37:16 <sarang> or to the next topic, QUESTIONS
17:37:26 * sarang waits patiently
17:39:30 * sarang waits impatiently
17:39:32 <suraeNoether> i have a pretty general observation
17:39:47 <suraeNoether> which may be relevant in terms of independent interest
17:40:01 <suraeNoether> a property like linkability applies to all ZK proofs. for example, our ring signatures are ZK proofs of knowledge of a secret key. but they are *linkable* proofs of knowledge, so that if the same witness data (keys) are used for two different proofs (signatures), then an observer can link them.
17:40:17 <suraeNoether> so just like ZK proofs have a property of correctness (if you know a witness, the proof is valid) and a property of soundness (if you don't know a witness, your proof is invalid), a linkable ZK proof is going to have a dual pair of notions for linkability
17:40:43 <suraeNoether> i bring this up so that the next version of snarks has an L floating around
17:40:53 <sarang> There's a related-ish property in sigma protocols, quasi-unique responses
17:41:02 <sarang> But that relates to responses to the verifier challenge
17:41:32 <suraeNoether> more reading to do :\
17:42:07 <sarang> There's probably a subtle relationship to (SHV)ZK
17:42:13 <sarang> and therefore witness indistinguishability
17:42:17 <sarang> (which follows from SHVZK)
17:42:39 <suraeNoether> anyway
17:42:40 <sarang> Normally, providing two proofs should not reveal distinguishing information about the witnesses
17:42:50 <suraeNoether> right
17:43:42 <sarang> Hopefully you will enjoy the Triptych paper, which builds a linkable construction on top of a sigma protocol :)
17:44:31 <suraeNoether> i enjoyed it the last time i read it, and the tiem before that. it takes awhile to digest :P
17:45:46 <suraeNoether> ok, i gotta bounce, i'm not feeling well; my list of 3 unfinished tasks is also my list of action items today
17:46:17 <sarang> roger
17:47:29 <sarang> My ACTION ITEMS are getting these new definitions and proofs typeset and finalized, determining their DLSAG applicability, a few other organizational issues on the CLSAG paper to prepare it for resubmission, and getting Triptych submitted on review
17:47:49 <sarang> Any other final thoughts, comments, or questions before this meeting ends?
17:48:34 <moneromooo> I have an unrelated question.
17:48:43 <sarang> ?
17:49:10 <moneromooo> I was wondering whether atomic swaps between two cryptonotes with hte same curve etc (ie, not the general case) is possible now.
17:49:37 <moneromooo> Well, assuming the tooling was there of course, which it isn't.
17:49:50 <moneromooo> In theory I mean.
17:50:01 <sarang> I don't know of a good way that retains indistinguishability as well as DLSAG does, and that still has the tracing issue
17:51:13 <sarang> If you were willing to accept and mitigate the tracing issue, then its method could do it
17:51:18 <sarang> its = DLSAG's
17:51:46 <moneromooo> What is the tracing issue already ?
17:53:28 <sarang> The fixed basepoint used for dual-address key images allows determination of unwanted signature linking
17:54:22 <sarang> It isn't clear how to do a DLSAG-type construction with the variable-basepoint key images used currently
17:55:40 <sarang> I should more precisely say, the use of a fixed basepoint and having output private keys used as the corresponding key image discrete log (this doesn't exist in more recent constructions that use a fixed basepoint but in a different way)
17:56:49 <sarang> Oh, suraeNoether: do you think it's useful in the LA definition to include the linking tag oracle separately from the signature oracle?
17:57:31 <sarang> The player can get the linking tag oracle result simply by querying the signature oracle on a public key by using a random ring and message (and ignoring everything but the returned linking tag)
17:58:40 <sarang> Having a separate oracle only really serves to make it clear that the player doesn't necessarily need to convince a user to sign messages, but can obtain linking tags otherwise
17:58:47 <sarang> (although in this security model, it can do both)
18:01:03 <suraeNoether> Hmmm an algo given access only to the signing oracle can still play the other game and win so the games are nested for sure...
18:01:44 <sarang> Seems to be only about clarity, really
18:01:55 <sarang> Having only tag access is a weaker adversary, for sure
18:03:00 <suraeNoether> Is it? If you get all the same signing oracle queries but also can reveal some key images without seeing a full signature, that seems stronger! Hmmm
18:03:17 <sarang> Er, yes, sorry
18:03:30 <suraeNoether> No no I'm not surr
18:03:33 <suraeNoether> Sure*
18:03:38 <suraeNoether> It's not clear.
18:03:47 <suraeNoether> the alternative with key image oracle access is neither modeling a weaker nor stronger adversary, I think. I think they are equivalent.
18:04:06 <sarang> Right, signature-only and signature-plus-tag are the same
18:04:32 <sarang> Adding the tag oracle serves only to separate the player's modeled abilities
18:04:50 <sarang> e.g. to present a public key to some entity and receive the linking tag, which could be used to identify signatures
18:05:07 <sarang> This is mainly a "cosmetic" question about the definition
18:06:39 <suraeNoether> yeah, I think that all of the information that you get out of one transcript should be in theory obtainable in the other transcript and vice versa
18:07:21 <suraeNoether> So in that case I think that giving the linkable anonymity player only access to the signature oracle is the way to go
18:07:24 <sarang> Yes, each signature query contains a key image presented by the master algorithm in the same way
18:07:29 <sarang> (purported key image, rather)
18:07:41 <sarang> The player can only "check" the key image by seeing its consistent use in signatures