Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've been reading this in many places and I still don't properly understand what it means to be "sound". As an example of what I am asking for:
The Fiat-Shamir transfrom is sound in the Random Oracle Model (ROM), where hash functions are assumed to behave as Random Oracles.
I know that being in the ROM means that hash functions are thought to be trully random functions and the Fiat-Shamir is a technique to transform interactive $\Sigma$-protocols to non-interactive. So what that means?
An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof system (when $\textsf{P}$ is computationally unbounded) or an argument system (when $\textsf{P}$ is computationally bounded).
The Fiat-Shamir transform compiles an interactive protocol into a non-interactive protocol by, roughly-speaking, replacing the verifier $\textsf{V}$ with a hash function $H$. To be more precise, the prover computes -- by itself -- the $i$-th verifier message $\beta_i$ by hashing the transcript so far (which consists of the statement $I$, the prover messages $\alpha_i$s from the previous rounds and the previous values of $\beta_i$s): see the figure below (which is taken from here). In the random oracle model (ROM), the hash function $H$ is modelled as a random oracle, i.e., a random function accesible to all parties via an oracle.
The Fiat-Shamir transform is said to be "sound", if it "preserves" the soundness of the interactive protocol being applied to. That is, the non-interactive protocol $(\textsf{P}_{FS},\textsf{V}_{FS})$ that results by applying the Fiat-Shamir transform to a interactive protocol $(\textsf{P},\textsf{V})$ is also sound. We say that the Fiat-Shamir transform is sound in the ROM if the above holds when $H$ is modelled as a random oracle.
When is the Fiat-Shamir transform sound? It is known to be sound in the ROM when applied to constant-round interactive proof systems [PS00]. In particular, we end up with a non-interactive argument system. One of the most common examples of this is the Schnorr signature scheme, which is obtained by applying the Fiat-Shamir transfom to the Schnorr identification scheme.
On the other hand, we know of certain counterexamples where the transform is "unsound" even in the ROM. I'd finish by adding that there has been a lot of exciting recent works that have aimed at proving the soundness of the Fiat-Shamir transform in the standard model (i.e., without random oracles): see [C+19,PS19] and reference related to them.
[C+19]: Canetti et al. Fiat-Shamir from Simpler Assumptions, STOC'19
[PS00]: Pointcheval and Stern, Security arguments for digital signatures and blind signatures, JoC, 2000.
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE., Crypto'19
