[tor-dev] [RFC] Proposal: "Res tokens: Anonymous Credentials for Onion Service DoS Resilience"

[Mike Perry]

On 2/11/21 5:36 PM, George Kadianakis wrote:
> We are particularly looking forward to feedback about:
> - Token issuance services
> - The anonymous credential scheme chosen
> - The XXXs and design decisions of the proposal
> 
> Hope you have a pleasant read!

> # 9. Acknowledgements
> 
>   Thanks to Jeff Burdges for all the information about Blind RSA and anonymous
>   credentials.
> 
>   Thanks to Michele Orrù for the help with the unlinkability proof and for the
>   discussions about anonymous credentials.
> 
>   Thanks to Chelsea Komlo for pointing towards anonymous credentials in
>   the context of DoS defenses for onion services.

Yooo, duuude! We need to give a public shoutout to OG Chaum! Almost 40
years later, and still the best properties we could find for our use
case. Oldest *AND* best! Fine 1983 vintage crypto, well aged, and
post-quantum unlinkable!

If you know anything about the history of this token, you will know with
certainty that Murs wrote this song about Chaum, referring to when
someone once asked Chaum how to link his tokens to track users:
https://open.spotify.com/track/0RdiYSv0mUfqYXN5WwYXjl

(Ok, so the Murs part may be apocryphal, but the rest is true!)

The One True Anonymity OG was even in talks with credit card companies:
https://decrypt.co/resources/digicash-what-is-cryptocurrency-explainer
https://www.satoshiwatch.com/hall-of-fame/dr-david-chaum/in-depth/digicash-blew-everything-david-chaums/

> ---
> 
> # Appendix A: RSA Blinding Security Proof [BLIND_RSA_PROOF]
> 
>   This proof sketch was provided by Michele Orrù:
> 
>   ```
>   RSA Blind Sigs: https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_signatures
> 
>   As you say, blind RSA should be perfectly blind.
> 
>   I tried to look at Boneh-Shoup, Katz-Lindell, and Bellare-Goldwasser for a proof, but didn't find any :(
> 
>   The basic idea is proving that:
>   for any  message "m0" that is blinded with "r0^e" to obtain "b" (that is sent to the server), it is possible to freely choose another message "m1" that blinded with another opening "r1^e" to obtain the same "b".
> 
>   As long as r1, r0 are chosen uniformly at random, you have no way of telling if what message was picked and therefore it is *perfectly* blind.
> 
>   To do so:
>   Assume the messages ("m0" and "m1") are invertible mod N=pq (this happens at most with overwhelming probability phi(N)/N if m is uniformly distributed as a result of a hash, or you can enforce it at signing time).
> 
>   Blinding happens by computing:
>      b = m0 * (r0^e).
> 
>   However, I can also write:
>      b = m0 * r0^e = (m1/m1) * m0 * r0^e = m1 * (m0/m1*r0^e).
> 
>   This means that r1 = (m0/m1)^d * r0 is another valid blinding factor for b, and it's distributed exactly as r0 in the group of invertibles (it's unif at random, because r0 is so).
>   ```
> 
> ---
> 
> [REF_TOKEN_ZOO]: https://tokenzoo.github.io/
> [REF_INTRO_SPACE]: https://gitlab.torproject.org/legacy/trac/-/issues/33650#note_2350910
> [REF_CHAUM]: https://eprint.iacr.org/2001/002.pdf
> [REF_PRIMO]: https://repo.getmonero.org/selene/primo
>              https://www.monerooutreach.org/stories/RPC-Pay.html
> [REF_POW_PERF]: https://gitlab.torproject.org/tpo/core/torspec/-/blob/master/proposals/327-pow-over-intro.txt#L1050
> [REF_RES_BENCH]: https://github.com/asn-d6/res_tokens_benchmark


-- 
Mike Perry