Hello all; research meeting today is at 17:00 UTC

suraeNoether: check Wire after the meeting

Everyone reading into this - no, not a security issue :)

Meeting begins in about 5 minutes

ping suraeNoether

The usual agenda: monero-project/meta #417

howdy everyone

Hi

Let's go ahead and get started with GREETINGS

o/

hello

That's long enough!

Let's move to ROUNDTABLE

suraeNoether: what up with you

i'm terribly ill this morning, so my update will be very brief. my work in this past week has involved three incomplete tasks:

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?

suraeNoether: I have a writeup for LA in my notebook that I'm transcribing to TeX

and proof* not just the definition

it works just fine

On that note

Do you have any thoughts on linkability (not LA)

I don't particularly like the Backes definition

uh one sec

Triptych has a version of linkability+non-frameability that I like better

is there soemthing wrong with the definition we proposed initially?

iirc that one's from bender

It's not formalized quite enough, in the apparent opinion of the reviewer

I think it needs just minor work

Triptych formalizes it a tad more IMO

I can add that to the writeup if you like

well

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'

Backes requires the following for an LRS: completeness, linkable anonymity, linkability, non-frameability

Right now we combine linkability and non-frameability with non-standard terminology

Backes uses a particular linkability definition: can the adversary use `q` keys to generate `q+1` non-linking signatures?

Where `q` is scaled via the security parameter

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

Our current method does this very informally

I propose a combined linkability definition in my Triptych writeup that's a slight formalization of what CLSAG has now

(it could easily be split into linkability and non-frameability)

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"

Yeah, which is why I don't really like it

didn't sit well with me

and we want the property with q=1 anyway to prevent double-spending

So I am proposing not using the Backes definition, but simply formalizing what we have now, a la Triptych

then it's more clear what the linkability player has access to in terms of keys etc.

okay, i'm going to read more deeply into that this afternoon

IMO it's a pretty straightforward formalization

doesn't affect much in practice

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

That definition doesn't make assumptions about linking tags being equal AFAICT

Whereas ours does

I think that's part of it

Anyway, you were talking about work you'd been doing, before I barged in =p

moving along, my next incomplete task is reviewing triptych's security proofs more deeply, which dovetails with this :P

Yeah, a nice tie-in

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

Nice!

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

word

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

We can pretend otherwise

I have completed a draft of the Triptych preprint, which is now in suraeNoether's hands

suraeNoether: I'm really looking forward to that chart

it includes my proposed linkability+non-frameability definition

Figured out the CLSAG linkable anonymity definition, which is not as strong as Backes, but does the job IMO

I've also been working with Aram from Zcoin on some related Groth proving system stuff

what's the shortfall on the linkable anonymity definition, even if there's no practical difference?

There will be a neat paper coming out from them on that shortly, which they graciously provided to me in advance

sgp_: Backes permits key corruption, which doesn't work with our DDH hardness assumption

Instead, we assume the adversary can obtain key images

And that the adversary can pack rings with their own malicious keys

sarang: thanks

(which you can assume are trivially corrupted)

This is already stronger than the existing definition that was used

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

So overall, a lot of tedious (but still interesting) stuff involving formal definitions and proofs

When suraeNoether finishes his review of the Triptych preprint, it'll go to the IACR archive

and presumably any CLSAG/DLSAG updates as well

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*

The adversary picks which keys IIRC, right?

yeah, adversary can use KeyGen or any other way of selecting the verification keys

may not even know the secret key, so it's genuinely adversarial

ya

The adversarial generation isn't really a big deal, since soundness implies the adversary's choice of keys satisfy the verification equations

and then you rely on the one-way mapping

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

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

Backes even notes that generating `q` such signatures is trivial, since you simply use separate keys

Fake pubkeys should be acceptable

since the adversary does all this offline, or otherwise generates the pubkeys in its own (seemingly) valid transactions

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

suraeNoether: thoughts?

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.

Yeah, and I haven't seen it anywhere else

Again, I don't feel any particular need to use it

But getting the existing definition more formalized in a challenger-player sense seems wise

agreed

roger

OK, that's my update

Does anyone else have interesting (or uninteresting) research to share?

ok, dude, i think i know the problem here

with that definition

or at least my problem with it

Ooh, go on

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

you called this positive and negative linkability at some point

i feel like this definition is mashing the two together

or attempting to

anyway, my thoughts don't go deeper than that yet

Backes uses non-frameability to show that you can't make signatures that _appear_ to link without knowing/using the same key

and linkability to mean that you can't make sigs with the same key(s) but different tag(s)

The reviewer didn't like the CLSAG paper's use of positive/negative/soundness in linkability

hmm

okay, that's going to require more thought

anywya, now i'm done. :P

A lot of this is simply getting the right terminology for the definition(s) of choice

I happen to like using linkability to refer to both

since that's typically what you want

but it's two different concepts

OK, we can move on to any other research

or to the next topic, QUESTIONS

i have a pretty general observation

which may be relevant in terms of independent interest

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.

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

i bring this up so that the next version of snarks has an L floating around

There's a related-ish property in sigma protocols, quasi-unique responses

But that relates to responses to the verifier challenge

more reading to do :\

There's probably a subtle relationship to (SHV)ZK

and therefore witness indistinguishability

(which follows from SHVZK)

anyway

Normally, providing two proofs should not reveal distinguishing information about the witnesses

right

Hopefully you will enjoy the Triptych paper, which builds a linkable construction on top of a sigma protocol :)

i enjoyed it the last time i read it, and the tiem before that. it takes awhile to digest :P

ok, i gotta bounce, i'm not feeling well; my list of 3 unfinished tasks is also my list of action items today

roger

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

Any other final thoughts, comments, or questions before this meeting ends?

I have an unrelated question.

?

I was wondering whether atomic swaps between two cryptonotes with hte same curve etc (ie, not the general case) is possible now.

Well, assuming the tooling was there of course, which it isn't.

In theory I mean.

I don't know of a good way that retains indistinguishability as well as DLSAG does, and that still has the tracing issue

If you were willing to accept and mitigate the tracing issue, then its method could do it

its = DLSAG's

What is the tracing issue already ?

The fixed basepoint used for dual-address key images allows determination of unwanted signature linking

It isn't clear how to do a DLSAG-type construction with the variable-basepoint key images used currently

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)

Oh, suraeNoether: do you think it's useful in the LA definition to include the linking tag oracle separately from the signature oracle?

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)

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

(although in this security model, it can do both)

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...

Seems to be only about clarity, really

Having only tag access is a weaker adversary, for sure

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

Er, yes, sorry

No no I'm not surr

Sure*

It's not clear.

the alternative with key image oracle access is neither modeling a weaker nor stronger adversary, I think. I think they are equivalent.

Right, signature-only and signature-plus-tag are the same

Adding the tag oracle serves only to separate the player's modeled abilities

e.g. to present a public key to some entity and receive the linking tag, which could be used to identify signatures

This is mainly a "cosmetic" question about the definition

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

So in that case I think that giving the linkable anonymity player only access to the signature oracle is the way to go

Yes, each signature query contains a key image presented by the master algorithm in the same way

(purported key image, rather)

The player can only "check" the key image by seeing its consistent use in signatures