2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Is the goal you're trying to achieve is for the user to have a large number of public keys for the same private key (all unlinkable)? If so, one issue is that, with a single (message, signature) pair, they become linkable (because anyone can verify the signature will the two public keys, and see that the signature verifies with both public keys) $\endgroup$
    – poncho
    Jun 6, 2023 at 16:29
  • $\begingroup$ @poncho Yes, that's the idea. Good point that a single signature would allow two public keys to be linked. Thinking about it, maybe that means that this sort of construction is actually impossible. $\endgroup$ Jun 6, 2023 at 16:38

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ Awesome, that's exactly what I was looking for. Thank you very much! $\endgroup$ Jun 8, 2023 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.