Consider the following system involving a message authentication code like HMAC-SHA256:
- Alice generates a key and shares it with Bob, and Bob alone.
- Alice authenticates a message with the key.
- Bob acts on the message only if it can be verified with the key.
Of course, Alice can verify messages too, and Bob can forge messages too. Indeed, anyone who has the key can verify or forge messages: the key necessarily grants the power to do both. Consequently, Alice can't present a cryptographic proof to a third party that a message came from Bob, because Alice could have forged the message; and vice versa. Thus this system has ‘deniability’, or lacks third-party verifiability.
Consider the following system involving a digital signature scheme like RSASSA-PSS or Ed25519:
- Alice generates a key pair and shares the public key with Bob, and Bob alone.
- Alice signs a message with her private key.
- Bob acts on the message only if it can be verified with Alice's public key.
Only Alice can sign messages; anyone with the public key can verify them but not sign them. You asked that only Bob be able to verify messages. Can the public key be kept secret so that Bob alone can verify them?
The standard for signature security is existential unforgeability under adaptive chosen-message attack, or EUF-CMA, which means that an adversary who can query an oracle for the signature of any message of their choice nevertheless can't forge a signature for any message they didn't query the oracle for. Nothing prevents an EUF-CMA signature scheme from simply including a copy of the public key in the signature itself, so that won't keep Alice's public key secret.
There's a nonstandard property of some public-key cryptosystems called key privacy—formalized for public-key encryption schemes, it means that given two public keys and a ciphertext the adversary can't tell which public key the ciphertext corresponds to. Of course, this doesn't carry over naturally to signatures because if you had the public keys and message you could just verify the signature.
There's a related notion of anonymous signature schemes, where an adversary presented with two public keys and a signature but not the message can't tell which public key made it, which typical RSA-based signature schemes fail by the German tank problem to the chagrin of the Australian Department of Human Services who hoped it provided privacy it didn't. Schnorr-type signature schemes in a standard group like Ed25519 do tend to provide anonymity in this sense.
There's another related notion of key indistinguishability (paywall-free) where an adversary presented with two public keys and a signing oracle can't tell whether the public keys have the same private key, but this is in an exotic context where a set of many users can sign messages with their respective private keys, but only one party can distinguish signatures made by the users.
Which of these do you want? I don't know—it's not clear to me what you're trying to accomplish at a higher level, so it's hard to give more specific advice.