To my understanding, whilst the definition of zero-knowledge (zk) is the same in the non-interactive context, how one shows a non-interactive scheme is zk is very different from interactive zk protocol. This is because a Simulator cannot simply produce a valid transcript (as it does in the interactive setting) as doing so would violate the soundness property of the scheme. Soundness was provided for in the interactive setting via the challenge which comes from the verifier and therefore means the prover has no control over. NI-ZK seeks to supply this information the prover must use during the construction of their proof in a non-interactive way.

I have found two frameworks for NI-ZK: Random Oracle Model (ROM) and common random string (CRS). I believe the idea behind the ROM framework is a hash function is used to supply the information outside the control of the prover, which is then modeled by a random oracle for the Simulator who then has the superpower of being able to choose the output of the oracle. In the CRS framework, the information comes from the CRS which was chosen prior by a trusted third-party and so the Simulator gains control over the CRS too.

  1. Is this the correct idea behind these two frameworks?

  2. Are there proofs for ROM-type schemes which do not actually rely on the ROM? More specifically how can one be sure that such a NI-ZK scheme is secure and not susceptible to the theoretical issues that other ROM-dependent scheme are (i.e. security in the ROM does not guarantee security for any real hash function)?

  3. Are there any other approaches to NI-ZK?

  • $\begingroup$ What do you mean by ROM-type schemes that do not rely on the ROM? Would this type of work on instantiating the Fiat-Shamir heuristic using a concrete hash function answer question 2? $\endgroup$
    – lamontap
    Commented Mar 22 at 18:13
  • $\begingroup$ @lamontap Yes - poor wording on my part but essentially a scheme which uses a hash function to create the challenge and which doesn't use the ROM for its security proof. As for the paper you linked - I haven't read it but from the abstract it seems to somewhat contradict my understanding a bit. They seem to construct a NI-ZK scheme using CRS andclaim they didn't need Fiat-Shamir to do this. But I always thought this was the case - CRS NI-ZK schemes never used Fiat Shamir did they? $\endgroup$ Commented Mar 25 at 8:31
  • $\begingroup$ They give an "instantiation" of the Fiat-Shamir transform in the CRS model. This means that they replace the random oracle with a concrete hash function family $\{H_s\}_s$ such that when the CRS has value $s$, the function $H_s$ is used to compute the challenge. $\endgroup$
    – lamontap
    Commented Mar 25 at 15:50
  • $\begingroup$ @lamontap So it sounds like that is a CRS scheme then, right? As in the Simulator can has the power to choose the CRS in order for them to be able to provide valid proofs? If so that doesn't really answer my question 2 but it may just be that there aren't any schemes out there which can do this. for question 2 what I'd really like to see is a scheme which is built in the (exact) same way a ROM NI-ZK scheme is built, but they choose an explicit hash function and then argue it is secure with that hash function rather than using the ROM. $\endgroup$ Commented Mar 26 at 8:12
  • $\begingroup$ Then, what you are asking is most likely impossible. See eprint.iacr.org/2003/034 and eprint.iacr.org/2012/705. In general, you can't have NIZK in the plain model. This was shown by Goldreich and Oren. $\endgroup$
    – lamontap
    Commented Mar 26 at 13:05


Your Answer

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