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).

copy of slide

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?

  • $\begingroup$ What is $\:\kappa \hspace{-0.05 in}>\hspace{-0.06 in}(|x|)\;$? $\;\;\;$ $\endgroup$
    – user991
    Commented Jun 3, 2014 at 20:37
  • $\begingroup$ @RickyDemer, it's a typo - fixed $\endgroup$
    – Bush
    Commented Jun 4, 2014 at 20:49
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 5, 2014 at 2:48
  • $\begingroup$ $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) $\endgroup$
    – Bush
    Commented Jun 5, 2014 at 4:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Guut Boy
    Commented Dec 8, 2014 at 21:22

2 Answers 2


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.

  • $\begingroup$ @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?). $\endgroup$
    – Bush
    Commented Jun 6, 2014 at 8:20
  • $\begingroup$ 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. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 6, 2014 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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.