# 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 such a $q$ can be exists?

-
What is $\:\kappa \hspace{-0.05 in}>\hspace{-0.06 in}(|x|)\;$? $\;\;\;$ –  Ricky Demer Jun 3 at 20:37
@RickyDemer, it's a typo - fixed –  Bush Jun 4 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 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 at 4:24
I can say that the running time requirement does not fix that definition's problems. $\hspace{1.45 in}$ –  Ricky Demer Jun 5 at 4:43

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 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 at 8:47