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 am just reading the "soundness"-definition for proofs of knowledge by Bellare / Goldreich. A proof of knowledge is a proof between a prover $P$ and a verifier $V$. $P$ convinces $V$ to know a secret value. The idea is to define a knowledge extractor $K$, which can calculate the secret. They write

There exists a constant $c > 0$ and a propabilistic oracle machine $K$ such that for every interactive function $P$ and every (public) $x$, machine $K$ satisfies the following condition:

If $p(x) > \kappa(x)$ then, on input $x$ and access to oracle $P_x$, machine $K$ outputs a string from the set $R(x)$ (i.e. the secret) within an expected number of steps bounded by $\frac{|x|^c}{p(x) - \kappa(x)}$

  • $p(x)$ is the probability that prover $P$ convince $V$ to accept on input $x$.
  • $\kappa(x)$ is the probability that prover $P$ convince $V$ to accept on input $x$ but $P$ doesn't know the secret.

I don't understand why they write $\frac{|x|^c}{p(x) - \kappa(x)}$?

1.) Ok, $p(x)-\kappa(x)$ is the probability that $V$ accepts and $P$ really knows the secret, but what does $|x|^c$ mean? It is a polynomial relationship, right, but e.g. why they use the absolute value of $x$.

2.) What it the "result" of the term? They write it bounds the number of steps but $p(x)$ and $\kappa(x)$ are probabilities.

Can someone please give my some hints on how to "read" this term?

share|improve this question
$|x|^c$ means $(\text{len}(x))^c$, and the "result" of the term is a real number. $\:$ The only way I can $\hspace{1.2 in}$ think of to define $\kappa(x)$ is $p(x)$ minus the probability that $K$ succeeds, but that would end $\hspace{1.2 in}$ up making their defintion of a proof of knowledge trivial. $\;\;$ –  Ricky Demer Apr 28 '13 at 18:51
$p(x)$ and $\kappa(x)$ are probabilities, but they are in the denominator. Think of $1/(p(x)-\kappa(x))$ as the expected number of trials to get a success, when the probability of success is $p(x) - \kappa(x)$; In this case, that quantity corresponds to the probability that "$P$ convinces $V$ and $P$ knows the secret.'' –  Mikero Apr 28 '13 at 20:56
thanks for your answer, but I don't get why the number of trials is important. The term says that $K$ returns the secret in polynomial time ($|x|^c$), right? Do you know, why the factor $1/..$ is important (why not write just $|x|^c$)? –  user4811 Apr 28 '13 at 21:38
The factor $1/(p(x)-\kappa(x))$ is important, because if the probabilities $p(x)$ and $\kappa(x)$ are equal, you can't expect that the extractor will succeed. More generally, when the difference of the probabilities gets larger, you expect to be able to perform extraction with fewer queries. –  minar Jul 10 '13 at 20:33

Your Answer


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

Browse other questions tagged or ask your own question.