I'd review the setup here. You're missing the critical distinction that the cryptography supports - separating entirely (in time and space) the issuance of the cred to the user and the use of that cred with a website.
Unless you're getting the device logs from the users device (in which case... All of this is moot) there is no timing attack. Six months ago you got your mobile drivers license. And then today you used it to validate your age to a website anonymously. What's the timing attack there.
If the driver's license can generate new anonymous tokens itself then anyone can hook up a driver's license to a computer and set up a service to sign for everybody. If it can't, whenever you want to prove your age to a service you need to get a new token from a third party, and then there is a timing correlation because you're asking for the token right before you use the service.
The article proposes a hypothetical solution where you get some finite number of tokens at once, but then the obvious problem is, what happens when you run out? First, it brings back the timing correlation when you ask for more just before you use one, and the number of times you have to correlate in order to be unique is so small it could still be a problem. Second, there are legitimate reasons to use an arbitrarily large number of tokens (e.g. building a search index of the web, content filters that want to scan the contents of links), but "finite number of tokens" was the thing preventing someone from setting up the service to provide tokens to anyone.
Blocking said search indexes is probably a good thing.
I'm thinking perhaps a system where you feed it a credential, a small program runs and maintains a pool of tokens that has some reasonably finite lifespan. The server that issues the tokens restricts the number of uses of the credential. Timing attacks are impossible because your token requests are normally not associated with your uses of the tokens.
And when you use a token the site gives back a session key, further access just replays the session key (so long as it's HTTPS the key is encrypted, hard to do a replay attack) up to whatever time and rate limits the website permits.
> Blocking said search indexes is probably a good thing.
I feel like "we should ban all search engines" is going to be pretty unpopular.
> And when you use a token the site gives back a session key
And then you have a session key, until you don't, because you signed out of that account to sign into another one, or signed into it on a different browser or device etc.
> The server that issues the tokens restricts the number of uses of the credential.
Suppose I have a device on my home or corporate network that scans email links. It's only trying to filter malware and scams, but if a link goes to an adult content barrier then it needs tokens so it can scan the contents of the link to make sure there isn't malware behind the adult content barrier.
If I only have a finite number of tokens then the malware spammer can just send messages with more links than I have tokens until I run out, then start sending links to malware that bypass the scanner because it's out of tokens.
Search engines should not be using website search capabilities. That's putting an undue load on the systems. A board I'm involved with recently had to block search for guests because we were getting bombarded with guest searches that looked like some bot was taking a web query and tossing it around to a bunch of sites. Many of them not even in English.
Unless you're getting the device logs from the users device (in which case... All of this is moot) there is no timing attack. Six months ago you got your mobile drivers license. And then today you used it to validate your age to a website anonymously. What's the timing attack there.