Say hello to zkMAC. 
TL;DR: do HMAC in a zkSTARK. It’s literally two hashes, smallest circuit ever, and once you build future Ethereum on a recursive zkSTARK framework you can aggregate as many signed transactions as you want and prove an entire block with a single proof.