Is there a signature scheme in which private keys can't be linked to their signatures?

Question

Normally in a signature system, the private key can be used to derive the public key, and therefore verify any given signature signed by that private key. Can we create a system without this property?

Namely, I'm looking for a signature scheme in which given a signed message and a private key, you can't tell whether the private key was used to sign the message; only the public key (or rather verifier key) can.

A corollary is that public/verifier key is not derivable from the private key. In addition, the signing process must be stochastic, as otherwise you could sign the message and see if it produces the same signature.

The use case I have in mind is that Alice would have 100 private keys, with one key be the distinguished "true" key, and then send these 100 public/verifier keys to Bob (and then Alice would delete the 100 private public keys from her computer). She would always sign messages with "true" key. Then, if Alice is captured, the adversary can not know which private key is the "true" key even after applying Rubber-hose cryptanalysis (since they can't tell whether Alice is lying or not). If one of the bad keys is used, Bob will know that either Alice's computer was compromised, or she signed it under duress.

Answer 1

The use case I have in mind is that Alice would have 100 private keys, with one key be the distinguished "true" key, and then send these 100 public/verifier keys to Bob (and then Alice would delete the 100 private keys from her computer). She would always sign messages with "true" key.

If she deleted all private keys, how can she then always sign with the true key? She has to keep all private keys, because in a rubberhose attack, the adversary would demand access to check what kind of private keys Alice has stored. Obviously she could only sign messages with a key she didn't delete again.

But for your scenario, you actually don't need an unusual signature scheme, here are two ways to achieve what you want:

• Alice uses common signature schemes (they don't have to be the same, as long as the signatures have equal length), with all verification keys being public. And when she sends a message to Bob, she always uses the same signing key. And now she always encrypts the signature with Bob's public key. As long as Bob isn't compromised, no one knows which key was used.
• as fgrieu pointed out, the randomized signatures can be used to get covert channels. Basically you agree with Bob on at the setup on a function over a bit array. Examples would be lowest (few) bit, parity of bits, 1st bit xor 5th bit, etc.
  In RSA-PSS you can put that information directly in the padding. In DSA (or ElGamal signatures) you would have to put it in the signature itself or an intermediate result of the verification, because the verifier can't extract $k$ from the signature. Instead, you would have to try multiple values of $k$.

But coming back to a previous part of your question:

Namely, I'm looking for a signature scheme in which given a signed message and a private key, you can't tell whether the private key was used to sign the message; only the public key (or rather verifier key) can.

A corollary is that public/verifier key is not derivable from the private key. In addition, the signing process must be stochastic, as otherwise you could sign the message and see if it produces the same signature.

ElGamal and DSA signatures don't fit this: From $x,r,s$ you can calculate $k$, and then check if $r=g^k$ holds. If you consider the RSA setting, there is a really interesting property, which Ilmari Karonen pointed out in his comment: Assume that there are two keys, with each one consisting of the modulus $n$ and one exponent, s.t. we get the usual RSA relation. If you have random values for the exponents, e.g. both have to be in a certain range, then both exponents are actually drawn from the same distribution, and knowing one does not reveal the other - under the RSA assumption.

However, there is one problem: Verification keys are public. As soon as the attacker gets hold of a signing key, they can calculate the product of the exponents. And with this the modulus can be factorized efficiently, so basically everything is out in the open.

At this point I am not sure what the adversary actually knows exactly. In general, (basic) signature schemes are built from oneway-trapdoor functions and there has to be a efficiently computable equation for the verification. In order to achieve this, the public key is always derived from the private key with the trapdoor in mind, so that you can't calculate "backwards" to the private key. But if you want that this computation is infeasable, then this might imply that the key generation can't be done efficiently.

However, group signatures or ring signatures might be of interest to you, because they have following properties:

• There are different signing keys (derived from a master key) and just one verification key
• In ring signatures it is not possible to determine which signing key created a signature
• In group signatures, the master key is required to determine which key signed a message.

In your case you could give Alice multiple keys, but there is a problem: If you require Bob to be able to tell which key signed a message, then you need group signatures and Bob has to have the master key. Because otherwise he won't be able to tell the difference either.

Answer 2

We usually assume that public keys are public. The system is only considered secure if it is not required that attackers don't know the public key.

But I think the property you desire can be achieved without any unusual types of public/private keys. Instead it just requires a signature scheme be agreed in advance (which should be no more onerous than agreeing to use the special kind of keys in advance). Something as simple as this may work:

1. When setting up the signature scheme, Alice and Bob exchange public keys and agree on a secret number $s$.
2. When signing a message, Alice augments her signature by appending both the secret number $s$ and a newly-generated random number $n$.
3. Alice then encrypts the augmented signature with Bob's public key, attaching the encrypted augmented signature to the message before sending it.

Now only Bob is the trusted verifier who can say whether the message came from Alice. Nobody without Bob's private key can even read the signature to check it.

Furthermore, Bob can always check that the secret $s$ is included in the augmented signature (and that after removing $s$ and $n$ the signature can be validated with Alice's public key).

And even if we assume the attackers are able to obtain (and validate as true) complete knowledge of this general algorithm, and Alice's private key, she can still lie to the attackers about what the secret $s$ is. They have no way of checking, even with Alice's private key and a previous message. They can't decrypt the message's signature without Bob's private key, so they can't see by inspection what $s$ is. And they can't re-sign a message they already have a signed copy of and check whether the signature matches, because the random number $n$ means the signature is different every time, even for identical messages. The sizes of $s$ and $n$ can be increased to provide any desired degree of resistance to brute forcing (since if the attacker tries every possibility for $s$ and $n$ they will eventually get a match with an existing message's signature).

Essentially you just need an additional secret (which in my scheme above was a simple shared key), and to include a random number to make the signatures stochastic as you noted, and to make the whole thing only readable by your trusted verifiers.

The scheme imagined in the question where there are 100 private keys but only one of them is the real one is just a way of providing the "additional secret" part; the agreed and secret choice of which key is the real one is essentially just a complicated way of secretly agreeing on a number between 1 and 100.

Answer 3

Cute puzzle! I think it really depends on how you formally define "you can't tell whether the private key was used to sign the message". I believe what you're asking for can go from almost trivial to a research question depending on the exact properties you ask.

Would the following partial solution work in your example?

• Let $(ek,dk)$ be an encryption/decryption key pair of some key-indistinguishable/anonymous public-key encryption scheme (for instance, ElGamal).
• Let $(sk,vk)$ be the signing key and verification key of any signature scheme.
• Let $(SK,VK)$ be the signing key and verification key of the scheme we are building.
• Let $SK=ek,sk$ and $VK=dk,vk$
• To sign with $SK$, first sign with $sk$ then encrypt with $ek$.
• To verify, first decrypt with $dk$ and then verify with $vk$.

Analysis: Since a signature is now an "encrypted signature" (using a key indistinguishable public key encryption scheme) knowing $SK$ doesn't help you learn anything about the signature, in particular you cannot learn its content (a signature made with $sk$) nor whether the encryption was done for key $ek$.