Surae 2018 August updates:

Greetings all,

In the month of August, I met a lot of you in person in Las Vegas at DefCon. This was fun, but I was sick most of the time, so I didn't get to spend as much time with you guys as I wanted.

I also posted the multisig paper on IACR, available here. I have posted it on my github here, and I have a meta-thread going to collect all review and copy-editing changes as they come up, see here. After we select a journal and send it out for peer review, I'll post any information from that process that I can in that issue, or in a similar issue.

I also continued my churn analysis; under a certain null hypothesis, it looks like ring sizes around 19 or 20 are unnecessarily large for transction histories to be concretely indistinguishable with only 3 churns. The write-up for this is in-progress (not quite ready for sharing). Under this hypothesis, using Chebyshev's inequality, we obtain a rough bound: for d churns and ring size r, with a probability of q of "de-fungible-izing" a transaction spending a tagged or poison output, with the attacker being the true spender or knowing the identity of the true spender of proportion p of the blockchain, transactions are (approximately) concretely indistinguishable up to this probability q if p*q*r^d > 1. The Chebyshev inequality is notoriously a *very weak bound.* For example, if the attacker controls half the blockchain and we want the probability of q to be smaller than 10^-6 (i.e.\ one in a million tagged transactions are identified) then Chebyshev's says we need r^d > 2*10^6. For a ring size of 20, this means d = 5 churns. However, as I mentioned above, the practical number for d is closer to 3 for a ring size of 20.

My churn analysis ended up extending to a game-theoretic formalization of the fungibility of a digital currency, which informally goes like this. Alice and Bob are two PPT algorithms with access to some non-empty wallets. Alice sends Bob a single transaction, whose outputs are "tagged." Bob selects a random bit b and is granted full access to the digital currency network for up to q blocks. Bob then sends Alice m new transactions, whose outputs are "deposits." Alice then outputs a bit b'. The bit b indicates whether Bob shall try to include at least one tagged output in at least one deposit, and the bit b' indicates Alice's guess at the value of b. Alice wins if b = b'. If for any ppt Alice, for any ppt Bob, Alice has a probability of success at most negligibly greater than 1/2, we say the protocol is (q, m)-fungible.

I also got horribly sick in the middle of the month, and I've been sort of inactive as a consequence. I hope that getting the IACR paper out the door and developing some concrete approaches to churn and fungibility is satisfactory for the community. I have been reviewing the DLSAG paper by Sarang and I have started writing up a paper whose title is already known: "Spender-ambiguous cross-chain atomic swaps of confidential assets." This involves formalizing threshold ring confidential transactions (thring confidential transactions?) using dual output ring signatures being described by Sarang.

I want to once again express my gratitude to the Monero community. My work so far at MRL has been extremely rewarding to me, both personally and professionally; I hope my work on multisignature can bring confidence to the community about the security of their funds, and I hope I can continue to contribute valuably to the Monero community.

Surae