Efficiently show/prove knowledge of third party secret without leaking information

Question

Say Alice publishes (i.e. all parties in the universe) a key or certificate $x$ and sends a secret $s$ to Bob. Bob then publishes some data $d$ (his identity or a message or smt.) and an authentication of the data using the secret, $auth = mac(d,s)$. Dave can now verify the authenticity of $d$, $verify(auth,x)$, and must not be able to extract substantial information about $s$, even when Bob reuses $s$ for different messages. Furthermore, Alice may produce many $(x_i,s_i)$ pairs and all parties have limited computing resources. Finally, the identities of all parties are known and private sidechannels are possible (so $s$ can safely be transmitted to Bob).

This can be implemented using public-key cryptography with $x$ being the public key and $s$ the private key. However, the (public key) algorithms I know of rely on large prime generation (or other costly operations), which I presume is too costly when in practice Alice produces lots of unused key pairs.

Is there a cheap solution to the scenario above?

(the title may be a bit off — if only I knew what I was looking for)

Answer 1

Public-key cryptography is not sufficiently computationally burdensome to where other approaches must be used for authentication protocols. Note though that what you describe is not actually public-key based. The verification of the MAC requires Dave and Bob to both have a shared key. Also, note that a random component must be included in some manner in all authentication protocols, else an attacker will be able to mount a man-in-the-middle attack and/or reuse the authentication string in the future. However, similar schemes that are based purely on public-key algorithms do exist, and are more commonly used. Either way, Alice is acting as a $TA$, verifying Bob's identity through some secondary channel and publishing a mechanism by which Dave can confirm that the owner of Bob's private signature algorithm (presumably Bob) is in fact Bob.

In this case, the computationally burdensome process, generating public-private key pairs, occurs not every time authentication takes place, but only when Bob asks Alice for a certificate. Also note that generating public-private key pairs is not particularly expensive, provided access to either an efficient cryptographically secure random number generator or a large pool of entropy, both of which are relatively easy to have.

Beyond that, public-key algorithms are designed so that the encryption and decryption processes can be computed efficiently. For instance, RSA and other Discrete Logarithm based problems have square-and-multiply or some variant. As such, the actual signing and verification step for Bob and Dave is quite simple and efficient, and there are a number of schemes which require only the limited computing power of say, smart cards.