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)