Bsrgvty

I would like to digitally sign a message in such a way that the signature can only be verified by one specific person. Simply encrypting the signature will not work, because that person could then decrypt and publish the signature and everyone else would be able to verify it.

Does anyone know of a scheme to accomplish this? Or any other advice?

In my situation, the person verifying the signature has an incentive not to publish their private keys.

What you seem to be looking for is deniable authentication.

This is actually a somewhat stronger property than what you're asking for: it guarantees that the recipient (let's call him Bob) cannot cryptographically convince anyone else that the sender (let's call her Alice) signed the message, even if he discloses all his private keys, simply because the protocol guarantees that knowing Bob's (and/or Alice's) private key is both necessary to verify the signature and sufficient to forge it. So Bob, seeing a message with a valid signature and knowing that he didn't create it himself, can be confident that Alice must have sent it — but he cannot use the signature to convince anyone else of that, since he could've just as well created the signature himself.

The simplest way to achieve this kind of authenticated but repudiable communication between two parties is to use a symmetric-key authenticated encryption scheme (or, if message privacy is for some reason not required or desired, just a plain MAC). With these schemes, Alice and Bob know the same secret key that is used both to authenticate the messages and to verify their authenticity. Thus, trivially, anything Alice can do (such as to create a valid authenticated message claiming to be from Alice to Bob) Bob — or anyone else who knows the secret key — can do as well.

The main drawbacks of such symmetric-key schemes are that they require a separate secret key for each pair of communicating parties (which could become cumbersome if there are potentially many such parties) and that the secret keys must somehow be securely shared between each pair of parties. This would be easy if we had an encrypted and authenticated secure channel between each pair of parties, but since that's exactly what we're trying to set up here, that creates a kind of a chicken-and-egg problem.

One way around these issues is to use public-key encryption to share the secret keys. In particular, we can use the Diffie–Hellman key exchange to establish a shared secret between any two parties, as long as they know each other's public keys (and, of course, their own corresponding private keys).

The Diffie–Hellman key exchange is often illustrated as an interactive protocol, but actually the only interaction it needs is for each party to send their public key to the other (which they may do in advance, e.g. by publishing them on some semi-trusted central key server). After that, any time one party (say, again, Alice) wants to send a message to another party (say, Bob), she can just combine her private key with Bob's public key to obtain a secret value known only to her and Bob, and then use this secret (possibly after feeding it through a suitable KDF) as the symmetric secret key for an authenticated encryption scheme as described above.

Anyway, for practical use, you don't actually need to implement any of this yourself, since there are plenty of existing implementations of such schemes. For example, the NaCl library (and its various derivatives, such as libsodium) provides the crypto_secretbox function for symmetric-key authenticated encryption and the crypto_box function for repudiable authenticated public-key encryption. If you don't particularly need to roll your own encryption scheme, I would encourage you to use those, or some other similar established and well studied implementation.

(One possible reason why you might want to do that is for nonce misuse resistance. The NaCl functions described above require you to assign each message a unique nonce, and its security can be badly compromised if you ever reuse the same nonce for two distinct messages encrypted with the same secret key. There are authenticated encryption schemes based on the SIV construction that are much more resistant to such nonce misuse, such as AES-SIV, AES-GCM-SIV or even HS1-SIV, but NaCl crypto_box does not currently support them. If you wanted, you could reimplement the "hashed Diffie–Hellman" part of crypto_box using crypto_scalarmult and use the resulting key with some SIV-style symmetric encryption scheme, but that requires a lot more effort and care than just using crypto_box as it is.)

Ps. On a slight tangent, note that Diffie–Hellman alone doesn't entirely solve the key distribution problem, since it still relies on the parties being able to share their public keys without anyone tampering with them. In particular, if Alice and Bob are trying to exchange public keys over a channel controlled by a middle-man Mallory, he can just replace Alice's and Bob's public keys with his own, and thereafter intercept any messages encrypted with those keys, decrypting and re-encrypting each message before passing it on.

(Of course, if Mallory ever stops doing that, Alice and Bob will find themselves unable to communicate until and unless they re-exchange public keys. But to Alice and Bob, that just looks as if someone just started attacking their communications by intercepting their messages and replacing them with invalid forgeries. Without some alternative communications channel, there's no way for Alice or Bob to know whether an attack just started or whether one just stopped. And even if they do somehow figure it out, it may be too late.)

One way to try to solve this problem is to set up some kind of a public key infrastructure where third parties can sign Alice and Bob's public keys in order to vouch for their correctness. But setting up a reliable PKI is far from a trivial task, since at some point you still need to trust someone.

Lets say Alice wants to send Bob a sensitive message, she wants to prove to Bob that it came from her, but she doesn't want Bob to be able to prove that to anyone else.

A MAC is a good way of doing this. If Alice and Bob share a MAC key (and only they have it) then Bob will know any message authenticated with that MAC key came from Alice, since he knows he didn't make it, and she is the only other person who could have.

However, there would be no way for a third party to tell the difference between a message from Alice and a forgery from Bob, since Bob is just as capable of creating the MACs as Alice.

A ring signature would also work, and it wouldn't require them to share a secret. Here, Alice would make a signature which proves that the message came from Alice OR Bob. Bob knows he didn't sign it, but he'd have a hard time trying to convince a third party about that.

the person verifying the signature has an incentive not to publish their keys

I don't see any way around publishing a public key. Other than possession of a secret, what could differentiate the designated 'verifier' from others?

With that said I believe we can use a public/private key-pair, such that only the 'verifier' has the private key, to achieve the properties you want.

We can't simply have senders take a hash of their message and encrypt it with the well-known public key, to generate the signature. This would allow anyone to verify the signature, as anyone can hash a message and encrypt the result using the public key. This 'generate-and-compare' is a show-stopper despite that the attacker doesn't have the private key. (Indeed, the private key is of no real value at all.)

Fortunately we should be able to fix this 'reversibility' problem by introducing non-determinism, in the form of a random 'nonce' number.

When someone wants to sign a message, they first pair the input message with a random nonce, then they encrypt this pair using the public key. The resulting encrypted blob can be used as the signature. (Unfortunately the length of the signature will roughly equal the length of the original message.)

The 'verifier' can easily verify integrity: they decrypt the encrypted blob using the private key, discard the nonce component, and compare the other (message) component against the unencrypted message.

No-one else can make use of the encrypted blob, however, as without the private key they cannot decrypt it, and due to the use of nonce they cannot use the generate-and-compare approach; their random nonce will be different, meaning they will generate a completely different encrypted blob.

(Someone more knowledgeable than me might know whether this approach has a name, or perhaps a fatal flaw that I've missed.)