I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is also my private key, and the public key is $h = H(k)$. As a signature for the message is $(mac = MAC_k(m),\pi)$ where $\pi$ refers to a proof using SNARK circuit which takes public input $m,h,mac$ and private input (witness) $k$ and calculates $mac' = MAC_k (m), h' =H(k)$ and outputs $1$ iff $mac=mac'$ and $h'=h$ .

Looks like we need to be extra careful if the MAC above is an HMAC with the same hash function $H$ since it uses actual $Key' = H(Key)$ if the $Key$ longer than block size,other than that are there other issues with it? Is it secure?

If it is not secure can anyone give a reason why? Way to recover key or forge a signature would be even better.


1 Answer 1


This is a valid paradigm for building a signature scheme, although a secure commitment scheme should be used to commit to $k$ instead of just using $H(k)$ as the public key. This type of construction was published by Bellare and Goldwasser at CRYPTO'89; see New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs. Formally, they use a NIZK, as you stated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.