Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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). enter image description here

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?

share|improve this question
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

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

share|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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