| 22 Apr 2021 |
 István András Seres | thanks for the pointers! I definitely want to play more with the simulation you built, although I'm not fluent in Rust. I also share your cautious enthusiasm towards fuzzy message detection. I think your simulation is a really nice and important first step towards understanding the privacy leakages of the FMD scheme needs to face in a real world application/deployment. What I would like to do, if time/energy permits, is to quantify the anonymity loss of users of an FMD system in an information theoretic anonymity model (a la Claudia Díaz et al. Towards measuring anonymity). Such a formal treatment of the privacy loss would be a nice complement of the simulation. One could start the formal modelling by observing that all these social graphs follow some nice power-law degree distribution. Then we could assume a few parameter selection scenarios (e.g. 1) everyone has the very same constant false positive rate p 2) everyone defines their false positive rate proportional to their degree (number of incoming messages)) and then given an intersecting attacker we could state nice theorems like what is the anonymity loss of users (or equivalently how powerful a certain deanonymization technique might be measured in bits in each of the aforementioned scenarios). | 18:49:16 |
| István András Seres | in the linked book above and also on your twitter thread you solely focus on completely deanonymized nodes/edges. I think, it would be also interesting to quantif to what extent the server can shrink certain users anon.set. I think it would be super interesting to see such graphs and to have such upper bounds on the provided anonymity guarantees of FMD. I would expect dramatic results. the server should be able to decrease anon.sets like crazy | 18:55:23 |
|  Nano Red joined the room. | 20:19:51 |
 sarahjamielewis | Yeah quantifying the bit-level loss of anonymity would be super cool, and something that should be relatively straight forward based on the current code. | 22:15:25 |
| sarahjamielewis | In general though I think the overall benefit of something like FMD will be in having a core set of power parties who download everything and provide a quantifiable anonymity set for all messages + a set of smaller parties who occasionally receive legitimate messages through the system, but mostly download a small amount of noise. Needs some actual quantification though :) | 22:20:18 |
| 23 Apr 2021 |
|  @visla:matrix.org left the room. | 15:27:57 |
| Nano Red left the room. | 23:03:20 |
| 25 Apr 2021 |
|  @lintro:matrix.org changed their display name from raffaem2 to raffaem. | 20:14:10 |
| 30 Apr 2021 |
| @lintro:matrix.org changed their display name from raffaem to capjack. | 09:53:14 |
| 2 May 2021 |
|  @willnix:matrix.org left the room. | 13:51:44 |
| 8 May 2021 |
| @lintro:matrix.org left the room. | 13:10:12 |
| 10 May 2021 |
| István András Seres | Hi all! In the last few days, I was working on a formal anonymity analysis of the (Fuzzy Message Detection) FMD protocol by Gabrielle Beck et al. (https://eprint.iacr.org/2021/089.pdf). I have some preliminary results, I thought it might be worth to share it here. So, it is highly non-trivial, as Sarah already showed in the simulator, how to choose your false positive detection rate. I analyzed the following classical notions of anonymity in the context of FMD and these observations can give lower bounds on the false positive rate. First, I had a look at receiver unlinkability. That means that we want that the untrusted server should not be able to link any two pairs of messages that they were sent to the same user. Consider the following adversary against receiver unlinkability: The adversary (the untrusted server) knows that the messages were sent to two different receivers if the intersection of the fuzzy tags is the empty set. Otherwise, if the intersection of the the tags is not the empty set, then it guesses that they were meant to the same receiver. A quite easy calculation shows that this easy adversarial strategy entails that the false positive rate should be much greater than 1/(square root of the number of users) IF we want receiver unlinkability! Second, I had a look at how much information can learn the untrusted server about the number of incoming messages of a user. You can imagine, that in many cases you also want to protect this information from the server. First I analyzed this in an information-theoretic setting with Shannon-entropy and then more interestingly, I analyzed this in a differential-privacy setting and if you want to achieve, say (\epsilon,\delta)-differential privacy for the number of incoming messages for \epsilon=0.1 and \delta = 10^-5 (these are classical suggested parameters in DP literature), then we need at least 10^8 messages in the system at least, otherwise we cannot hide the number of incoming messages for any false positive rate in this differentially-private sense. Third, I quantified the effects of intersection attacks, and now I will focus on relationship anonymity. If you have any more ideas, pls let me know and I will work out the details. In a few days/weeks I will plan to finish this work and then would love to get some feedback from anyone interested in this topic. Maybe Sarah, would you be interested in helping me and giving feedback before I release it as a pre-print on eprint and/or arxiv? Thanks a lot in advance for any ideas, insightful questions etc. :) | 10:29:08 |
| 13 May 2021 |
|  @tkennedy365:matrix.org left the room. | 09:13:17 |
| 19 May 2021 |
| sarahjamielewis | Hi István András Seres - sorry for the late reply - I switched over computers last week and forgot about matrix until today! | 00:32:00 |
| sarahjamielewis | Very interested in reading your analysis - feel free to send it over | 00:34:29 |
| sarahjamielewis | Regarding sender anonymity I just published niwl (https://twitter.com/SarahJamieLewis/status/1394799147199262722) which is an attempt to combine fuzzy message detection with mixing to overcome some of the issues you've outlined above. Which you might also find interesting. | 00:36:09 |
| István András Seres | Wow! Niwl looks super cool! I'll give it a closer look! Sender anonymity definitely eliminates some leaks from the untrusted server, e.g., now it cannot really estimate the number of exchanged messages between a fixed sender and recipient pair, because the sender's anonymity is ensured. But, still even if sender anonymity is achieved certain leaks will be inevitable in any FMD scheme like the number of incoming messages of a recipient given its false positive rate can be quite well approximated. Btw this info is not only to the server accessible but also to an ISP. I suppose a passive local/global adversary could easily figure out the number of fuzzy tags you download from the server. So in an FMD adversarial model one also need to consider these types of adversaries, not only the untrusted server. | 19:25:32 |
| 20 May 2021 |
| sarahjamielewis | Yeah, choosing p is still very important and non-trivial. | 18:58:48 |
| sarahjamielewis | Definitely, also need to expand the second on consideration for network adversaries. They have a window of activity they can use to guess regarding the messages downloaded (especially as activity changes) and yeah have to be assumed to know as-much as the server. | 19:05:52 |
| sarahjamielewis | On that front, I stayed up way too late last night tinkering with fuzzytag performance: https://twitter.com/SarahJamieLewis/status/1395258540764241922 | 19:06:22 |
| sarahjamielewis | 
Download Screenshot_2021-05-19_22-56-01.png | 19:07:14 |
| sarahjamielewis | The optimization actually makes both testing and tag generation faster. | 19:08:23 |
| sarahjamielewis | It also has an impact on entangled tags. And now I can generate a fully entangled tag in ~100 seconds on a consumer desktop. https://twitter.com/SarahJamieLewis/status/1395289683890819074 | 19:09:52 |
| sarahjamielewis | Which means I need to go back and think more about how that impacts the fuzzy message detection threat model a little more i.e. what strategies are possible if clients can efficiently generate a tag that matches 2 distinct parties regardless of false positive rate (and cheaply generate tags that will deliberately match a number of parties at higher false positive rates?) | 19:21:40 |
| 21 May 2021 |
| István András Seres | Entangled tags are awesome! It also opens up FMD to other applications, like ANOBE (anonymous broadcast encryption)...although not sure how efficient entangled tag generation is when you have multiple receivers. btw entangled tags are an invention of yours, right? I don't remember I've seen that idea in the FMD paper. | 07:22:46 |
|  @neobrain:matrix.org left the room. | 10:10:27 |
| sarahjamielewis | On efficiency, I remembers dalek has avx2 support, which pushes down all those figures by over 40% (https://twitter.com/SarahJamieLewis/status/1395610696847556609) | 17:37:20 |
| sarahjamielewis |
entangled tags are an invention of yours, right? I don't remember I've seen that idea in the FMD paper.
Yeah
| 17:37:54 |
| sarahjamielewis | *
entangled tags are an invention of yours, right? I don't remember I've seen that idea in the FMD paper.
Yeah
| 17:38:08 |
| sarahjamielewis | *
entangled tags are an invention of yours, right? I don't remember I've seen that idea in the FMD paper.
Yeah
| 17:38:16 |
