The impossibility of a secure "blind HMAC" scheme - an HMAC-based analogue of blind signatures - is known (as I understand it, essentially due to the user being unable to validate the signature received against a public key for the signer, and therefore being unable to be sure the signer is not using many signing keys and later "un-blinding" them by determining which of their keys is valid for a given signature).
However, from a performance and signature/MAC size perspective, HMAC is often preferable to signatures where the verifier holding the signer's symmetric key is acceptable. For instance, BLS signatures (blind or not) in minimal-signature-size mode with the BLS12-381 curve consume 384 bits with a security target of 128 bits - this is, seemingly, quite short by signature standards. In comparison, it seems that, for example, a 128-bit hash can provide 128 bits of security when using HMAC.
In such a situation, would a "semi-HMAC" blind authentication scheme work? Something like:
- User generates and blinds a message with a normal blind signature scheme, sends to signer
- Signer signs the blinded message, sends back to user
- User unblinds it and verifies against signer's public key, as with a normal blind signature - "blind HMAC", as proposed and proven insecure, is incapable of this, but it can be done here, since the blind-signing is done with a normal, assymetric blind signature scheme and hash-based authentication is only used later.
- User generates a hash of the message and the signature (rather than of the message and a key as in HMAC), and attaches it to the message.
- User sends message and hash to verifier
- Verifier receives message and, independently, signs it with the signer's private key (shared with the verifier as the symmetric keys are in HMAC schemes).
- Verifier compares the hash provided by the user against the one it generated
- If the hashes match, the user has proved the signer has signed the message, without actually needing to include a longer-than-its-hash signature
It seems like such a scheme could reduce the overhead of storing and transferring comparatively long signatures to the verifier. Additionally, it seems like the requirements on the hash function may be unusually few - a preimage attack on the hash function, for example, would not appear to pose a threat, as both parties already know the message used to generate it, nor would an attack by which either party could generate a hash collision (hashes are only used to prove that the user holds a valid signature for the message - the user would need to know the hash of their message and a valid signature for it to even search for a hash collision resulting in the same hash so that it will match the hash generated by the verifier). Really, the hash need only be secure against the user being able to successfully guess the hash of their message and a valid signature without obtaining that signature - i.e., it must be sufficiently difficult to brute-force a valid hash for a message "online", communicating with the verifier. Offline brute-force of the hash does not seem practical, as the user could not check a guess at a hash against their message offline without also being able to reverse the hash to a (much longer, by-chance-valid) signature and check the signature against the public key - they would probably do better to try to brute-force a valid signature or signing key for the underlying blind signature scheme, then generate a hash of that.
I have been unable to find references to any blind authentication scheme which works like this. Is such a scheme feasible? Are there any glaring flaws in it, security or otherwise?
TL;DR can the known security flaws of a blind HMAC scheme be avoided without some of the signature size implications of a blind signature scheme by using a blind signature scheme when signing, but having the user hash the signature and re-generating that signature and hash on the verifier's side using the signer's private key, then comparing hashes?
