Rate-Limited Tokens: Preventing attester from learning rate limit

[tfpauly]

From https://github.com/tfpauly/privacy-proxy/issues/219

In the current proposal, the attester learns the rate limit specific to the origin. This reduces the anonymity set to origins that share a common rate. Below, I describe an idea that prevents the attester from learning this rate.

Simplified summary of current proposal:

(as I understand it so far; for sake of comparison)

client sends BlindSigReq to attester attester forwards BlindSigReq to issuer issuer responds with BlindSigResponse and the origin's RateLimit attester enforces RateLimit based on H(client,origin) pair if rate limit OK, attester forwards BlindSigResponse to client client unpacks to learn its desired blind signature token Main idea

The main idea is to let the client request its entire quota of tokens in a single interaction, instead of requesting them one at a time. For this, I must make a distinction between an interaction and a token.

Let's say that all rate limits are expressed in the units of tokens / hour. Then the attester will simply check that there is at most 1 interaction, per (client,origin) pair, per hour. The attester's check is the same for all origins (1 interaction per hour), regardless of their true rate limit. But each "interaction" results in the client learning many tokens. The issuer already knows the rate limit (expressed in tokens per hour) so it enforces the rate limit by only giving out the correct # of tokens in a single interaction.

Simplified summary of new proposal:

For the sake of simplicity, I will assume that both client and issuer know the origin's desired rate limit. I will extend the notation so that BlindSigReq(n) <--> BlindSigResponse(n) is a blind signature protocol where the client learns n distinct signatures.

client sends BlindSigReq(RateLimit) to attester, where RateLimit is the origin's limit attester forwards BlindSigReq(RateLimit) to issuer issuer responds with BlindSigResponse(RateLimit) attester checks: was there a prior request on this (client,origin) pair in the last hour? if no such prior request, then attester forwards BlindSigResponse(RateLimit) to client client unpacks to learn RateLimit number of blind signature token In order to hide the rate limit from the attester, the BlindSig{Req,Response} protocol messages must hide the rate limit. I'm not sure if there are blind signatures or [V]OPRFs where the client can get several distinct tokens, in a protocol messages of constant size. However, I have some hope because the client mostly cares about the number of tokens learned, and is less concerned about what message is being signed. I.e., the client could learn signatures on a collection of random messages.

If such a blind signature or OPRF is not possible/feasible, then a trivial way to hide the rate limit is to pad the size of the protocol message to some maximum limit. One could also consider leaking only partial information about the rate limit -- e.g., round the rate limit up to the nearest power of two and pad the protocol messages to that size. A downside to this simple padding strategy is that it is wasteful of bandwidth by design.

[tfpauly]

As discussed at IETF 115, this is probably better as a new token type / extension.