3
$\begingroup$

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$ of his knowledge of 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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ $|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. $\;\;$ $\endgroup$
    – user991
    Apr 28, 2013 at 18:51
  • 1
    $\begingroup$ $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.'' $\endgroup$
    – Mikero
    Apr 28, 2013 at 20:56
  • 1
    $\begingroup$ 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$)? $\endgroup$
    – user4811
    Apr 28, 2013 at 21:38
  • $\begingroup$ 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. $\endgroup$
    – minar
    Jul 10, 2013 at 20:33

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.