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.