# Hamiltonicity proof of knowledge

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?

-
What is $\:\kappa \hspace{-0.05 in}>\hspace{-0.06 in}(|x|)\;$? $\;\;\;$ – Ricky Demer Jun 3 '14 at 20:37
@RickyDemer, it's a typo - fixed – Bush Jun 4 '14 at 20:49
Does that book define $L_R$ to be the set of $x$ values that $R$ "makes sense" for? $\:$ By the standard definition of $L_R$, the Validity condition would be trivial. $\;\;\;\;$ – Ricky Demer Jun 5 '14 at 2:48
$L_R$ is the set of all $x$s s.t. there exists $y$ s.t. $(x,y)\in R$. The construction of the knowledge extractor is trivial bur what can you say about the running time requirement, which related to the knowledge error? (As I wrote in the 'question' part) – Bush Jun 5 '14 at 4:24
Actually looking a little close at the definitions it should be "... there exists a $K$ s.t. for every $P^*$ and every $x \in L_R ...$, you should really have a look at www-cse.ucsd.edu/~mihir/papers/pok.ps for a nice discussion of the definition. – Guut Boy Dec 8 '14 at 21:22

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.

-
@RickeyDemer 1.Why did you assigned 0 to $\kappa (|x|)$? 2.Why do you need a minimum-length witness? 3.$K_w$ cannot output a witness with certainity, if $P^*$ is lying then $K_w$ wouldn't be able to output a witness. 4. I don't understand your conclusion (where is it stems from?). – Bush Jun 6 '14 at 8:20
1. I didn't; I used the fact that $\kappa(|x|)$ is non-negative. $\:$ 2. I probably don't; I put that in to help with $K$'s efficiency. $\:$ 3. My just-elaborated-on proof shows otherwise. $\:$ 4. My conclusion stems from the fact that my proof of validity doesn't use anything at all about the protocol. $\;\;\;\;$ – Ricky Demer Jun 6 '14 at 8:47

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.

-
*definition is copied word for word.. – Bush Dec 9 '14 at 6:12
@Bush here I am really not talking about the (possible) errors in the definition. Just the relationship between $p$ an $\kappa$. – Guut Boy Dec 9 '14 at 6:57