Digital signature scheme with blinded public key

Question

I need a digital signature scheme with the following characteristics, but I don't know what it's called, so I'm having trouble searching for publications about it. It seems likely that something like it already exists. Could you please help me identify what it's called?

The scheme I need consists of four algorithms:

1. $\mathsf{Gen}(1^\lambda) = (pk, sk)$ takes a security parameter and returns a pair of public key and private key;
2. $\mathsf{Blind}(pk) = pk'$ takes a public key and returns an obfuscated public key;
3. $\mathsf{Sign}(sk, m) = \sigma$ takes a private key and a message, and returns a signature $\sigma$;
4. $\mathsf{Verify}(pk', m, \sigma)$ takes an obfuscated public key, a message, and a signature, and returns 1 iff the signature is valid, or 0 otherwise.

The required security properties are:

• Existential unforgeability under adaptive chosen-message attack, as usual for a signature scheme;
• Public key hiding: Adversary chooses $pk$; challenger chooses a random bit $b \in \{0,1\}$; challenger computes $pk_0 = \mathsf{Blind}(pk)$ and picks $pk_1$ uniformly at random; challenger returns $pk_b$ to the adversary. The (polynomially bounded) adversary should have negligible advantage over a random guess in determining $b$. In other words, the $\mathsf{Blind}$ function should not allow its output to be linked with its input.

This isn't a blind signature scheme (which is about hiding the message from the signer, whereas I want to hide the public key from the verifier). It has some similarities to threshold signatures or anonymous credentials, but is not quite the same. Anyone know whether a construction like this exists?

Answer 1

There is a concept called key blinding that is very similar to what you describe. If I am not mistaken, this was originally invented for the Tor network as a way to anonymize the IP addresses of servers. They call this Onion Services (formelly known as "hidden services"). Basically, there is a table where blinded public-keys of onion services are published along with the routing information necessary to reach those services. A client wishing to reach an onion services does so using the real public-key (called identity public-key in the documentation).

The only formal analysis of this primitive I am aware of is this paper and this paper. A blinded public-key signature scheme is slightly different than what you describe in that a signature is not valid for all blinded keys, but only for a specific one (as poncho mentioned in his comment, this is essential for unlinkability). The difference is

• $\mathsf{Blind}(pk, \tau) = pk_\tau$ takes an additional parameter $\tau$ they call the "epoch".
• $\mathsf{Sign}(sk, m, \tau) = \sigma$ also takes $\tau$ as input.
• $\mathsf{Verify}(pk_\tau, m, \sigma)$ only needs to accept the signature $\sigma$ if $pk_\tau=\mathsf{Blind}(pk, \tau)$.

The hiding property (which is called unlinkability in the papers) is as follows:

• The challenger samples keys $(sk,pk)$.
• The adversary has oracle query access to $\tau\mapsto \mathsf{Blind}(pk, \tau)$ and to $(m,\tau)\mapsto \mathsf{Sign}(sk, m, \tau)$.
• The adversary sends $\tau^*$ not previously queried to the blinding oracle to the challenger.
• The challenger either sends back $\mathsf{Blind}(pk, \tau^*)$ or $\mathsf{Blind}(pk', \tau^*)$ where $pk'$ is a freshly sampled public key.