Signature scheme with two private keys, neither derivable from the other

Question

Is there any scheme, ideally one widely used or at least widely available, where you can treat both the signing and verifying keys as secret?

Basically, the functionality I'm looking for is this:

1. You derive two keys, $S$ and $V$.

2. $S$ cannot be derived from $V$, nor can $V$ be derived from $S$.

3. A signature can be made with only $S$ and verified with only $V$.

4. $S$ has no special structure. That is, it is not easy to tell if a given string is a valid $S$ or not.

The intended application is authentication. The idea is that either the user or the server would generate the two keys. The server would store $V$, and either the user or the server would store $S$ encrypted with a passphrase. An attacker with only the encrypted $S$ would not be able to launch an offline attack to decrypt it because he'd have no way to tell if his decryption was valid other than asking the server. And, if the server was compromised, an attacker still couldn't impersonate a client because he can't derive $S$ without breaking the passphrase.

Answer 1

Well, one obvious way to do this would be using RSA with a large 'public' exponent. That is, it is the traditional RSA sign/verify operation except that, instead of the usual optimization of having a small 'e' value, you would have a large one (a bit smaller than the modulus); and then derive d from e, p and q in the usual manner.

As for the requirement that it has no special structure, the only special structure that either exponent has is that they are odd; any odd value is a potential exponent (note: to avoid biases, it may be advisable to, when generating the p and q values, you exclude values where p-1 (and q-1) have small odd factors).

So, the signing key S would be the value (d-1)/2, and the verification key would be the value (e-1)/2, with the modulus being treated as public data (that is, there is no need to encrypt it). That this is secure (and you can't derive one from the other) follows directly from the standard RSA assumptions. That it meets requirement 4 follows from the idea that (d-1)/2 can take on any integer value.