2
$\begingroup$

I am reading about the Fiat-Shamir heuristic to take a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). I am now wondering whether there is a relationship between a NIZK proof and a digital signature scheme?

Specifically, can we take a NIZK proof obtained from applying Fiat-Shamir to a $\Sigma$-protocol and turn it into a digitial signature scheme? (Are there specific requirements for the underlying $\Sigma$-protocol?)

$\endgroup$
2
$\begingroup$

Recall that in strong existential unforgeability for digital signatures, we want it to be the case that even after seeing many signatures under different instances, it should still not be possible to create a new signature unless you know the secret key (equivalently witness in a NIZK).

So, one can use a NIZK to design a digital signature (of knowledge), but the underlying NIZK needs to provide a more stronger version of soundness (a standard NIZK only provides soundness) that technically is known as simulation-sound extractability. Intuitively, simulation-sound extractability in NIZKs is equivalent to concept of strong existential unforgeability. More precisely, simulation-sound extractability implies that it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs (signatures).

To sum up, a digital signature of knowledge can be designed using a NIZK that guarantees simulation-sound extractability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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