NIZK

NIZK

daniel (guest) 25 Jun 2019 15:16

I have some questions regarding lecture 10 and NIZK.
1. We proved that the Hamiltonicity protocl is HVZK, and it is mentioned on the first page that it is not hard to show that it is also malicious verifier ZK.

Corollary 4.3 states that If there exists a hash function H such that the Fiat-Shamir transform of, say, the Hamiltonicity protocol sound, the Hamiltonicity protocol cannot be ZK against malicious verifiers
and then you say that Fiat-Shamir hash functions are believed to exist.

So I don't understsnd how is this possible?

2. I'm not sure I understand claim 4.1, from the claim "make the verifier accept with probability at most (Q + 1)s"
Do you actually mean "make the verifier accept with probability at most (Q + 1)s for x not in L"
because if x is in L we want to make the verifier exist with probability 1, right?

Thanks.

Re: NIZK

eliadtsf 26 Jun 2019 06:41

1. "Fiat-Shamir hash functions are believed to exists" means that we believe there exists a family of hash functions that if the hash is sampled at random from it, then the Fiat-Shamir version of any protocol remains sound. But if this is the case, then zero-knowledge against malicious verifiers cannot be preserved. In other words, Fiat-Shamir cannot preserve both soundness and malicious ZK.

2. Yes, the meaning is for x not in L.

Re: NIZK

nbitansky 26 Jun 2019 13:58

Re Hamiltonicity, the basic, non-repeated protocol, is malicious ZK (in particular, it cannot have an FS function).
The repeated protocol is not known to be ZK, and in fact it is believed (and proved under reasonable assumptions) that it does have FS functions, and thus cannot be malicious ZK.

daniel (guest) 26 Jun 2019 14:49

When you say the repeated protocol, do you mean the basic protocol repeated in a sequential order?
I thought we said in class it is malicious ZK, but the version where you try to parallelize it, it is no longer malicious ZK.

If you do mean that the repeated protocol sequential protocol is not malicious ZK, then the basic protocol only gives us soundness error of 1/2, are there other known ways to reduce this error to be negligible and still preserving malicious ZK?

nbitansky 27 Jun 2019 13:34

- $3$-message protocols (without any repetition) has soundness $1/2$. Doesn't have FS. (This is what I call the basic protocol)
- $n$-sequential repetitions have soundness error $2^{-n}$ and is malicious ZK. Doesn't have FS.
- $3$-parallel repetition also has soundness error $2^{-n}$ but is not known to be malicious ZK, and is believed not to be. has FS under reasonable assumptions.

Last edited on 27 Jun 2019 13:35 by nbitansky Show more