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:
You derive two keys, $S$ and $V$.
$S$ cannot be derived from $V$, nor can $V$ be derived from $S$.
A signature can be made with only $S$ and verified with only $V$.
$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.