Hamiltonicity proof of knowledge

Question

I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$.

So the question will be self-contained, I provide here the slide describing the protocol (credits to Moni Naor, Weizmann institute).

And the definition as copied from Goldreich's book (Foundation of Cryptography):

Definition 4.7.3 (system for POK): Let $R$ be a binary relation and $\kappa :N\rightarrow [0,1]$. We say that an interactive function $V$ is a knowledge verifier for the relation $R$ with knowledge error $\kappa$ if the following two condition holds:

• Non triviality: There exist an interactive machine $P$ s.t. for every $(x,y)\in R$, all possible interactions of $V$ with $P$ on common input $x$ and auxilary input $y$ are accepting.
• Validity: $V$ satisfies the Validity requirement with knowledge error $\kappa$ if there exist a polynimial $q(\cdot )$ s.t. for every $P^*$, every $x\in L_R$, there exists a probabilistic oracle machine $K$ with oracle access to $P^*$, that run in expected polynomial time ad outputs a witness with probability at least $\frac{p-\kappa(|x|)}{q(|x|)}$ where $p$ is the probability that $P^*$ succeeds to convince $V$ to accept on common input $x$.

My Intuition:

First, it is known that if the commitment scheme is perfectly binding then the above protocol is a IZK proof system with soundness $1/2$.

• Non-triviality requirement is trivial to satisfy (specifically, $P$ from the protocol itself satisfies it).
• In regard to the Validity requirement, it is easy to construct a Knowledge Extractor

My question:

We know that the soundness of this protocol is $1/2$, so $p\leq 1/2$. Now, it required that there exists a poly $q$ s.t. $K$ succeeds to extract a witness with probability at least $\frac{p-\kappa (|x|)}{q(|x|)}$. If we assigne $p\leq 1/2$ and $\kappa =1/2$, how can such a $q$ exist?

Answer 1

Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$,
$\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$.


For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$:

Since $\: x\in L_R \:$, $\:$ there exists $y$ such that $\; (x\hspace{.02 in},\hspace{-0.02 in}y)\in R \:\:$. $\;\;\;\;$ Let $w$ be a minimum-length
example of that, and let $K_w$ be the oracle machine that immediately outputs $w$ and then halts.
Since $K_w$ ignores its input and halts, $K_w$ runs in expected polynomial time.
Since $K_w$ outputs $w$ with certainty and $w$ is a witness, $K_w$ outputs a witness with certainty.
In particular, its probability of outputting a witness is at least $\frac{p-\kappa(|x|)}{q(|x|)}$.


Therefore the given Validity condition holds.

Conclusion: $\:$ That book's Validity condition is trivial.

Answer 2

To answer your question (ignoring for a moment the inaccuracy of the definition), if am understanding you correctly you are wondering if $p \leq \kappa(|x|)$ how can there exist a $q(|x|)$ so that $K$ outputs a witness with probability $\frac{p - \kappa(|x|)}{q(|x|)}$ (because in this case the probability might be negative). I will try to explain this.

First of all, it is not possible that $p < \kappa(|x|)$. I think you might be confused about this because you are misinterpreting your definition. You say that the soundness is 1/2 and therefore $p \leq 1/2$. However, this is not true.

Soundness in a ZK-proof relates to the probability that a prover can convince a verifier of a false statement. I.e., make $V$ accept when $x \not\in L_R$. In your definition (even after being corrected) $p$ is the probability that a prover $P^*$ can make $V$ accept an $x \in L_R$. So you see $p$ is not bounded by the soundness because it relates to $x \in L_R$, and soundness relates to $x\not\in L_R$.

On the other hand the knowledge error $\kappa(|x|)$ describes how likely a $V$ is to accept an $x \in L_R$ when interacting with a $P^*$ that does not know a witness for $x$. So you see, by definition of $p$ you will always have $p \geq \kappa(|x|)$.

Now for $p = \kappa(|x|)$, this is really simple. In this case the probability that $K$ outputs a witness must be at least $0$, and such a $K$ should be quite easy to construct.