1
$\begingroup$

I try to wrap my head around calculating of complexity lower bound using Corollary 1 from The Uber-Assumption Family by X.Boyen (http://www.academia.edu/download/30698012/Steven_Galbraith_PairingBased_Cryptography_Pair.pdf#page=48), but I have some questions:

  • Do I understand correctly that bound is the same when we add more elements to problem instance as long as we don't increase maximal degree of polynomial? I mean

    given $g^{ab}, g^b, g^c$ calculate $z$

    and

    given $g^{ab}, g^b, g^c, g^{bc}, g^{ac}$ calculate $z$

    have the same bound in uber-assuption framework as they have the same maximal degree of $2$?

  • How do you calculate degrees when there are rational exponents? Let's say I try to calculate bound of problem:

    Given $g^\alpha, v \in G_1$ check if $v=g^{1/\alpha^2}$

    We have $R=<1, \alpha>, S=<1>, T=<1>$ and $f=1/\alpha^2$. $d_R=1, d_S=0, d_T=0$ but what is $d_f$? Should we use $\pi_i=1$ here for degree calculation or $\pi_i\Delta=\alpha^2$? In first case we have $d_f=0$, in second $d_f=2$

  • Can this calculated lower bound be used to draw any security conclusions about real world usage? It's defined asymptotically when $\kappa \rightarrow\infty$ so I think it tells you nothing about security of concrete implementation at any fixed $\kappa$. Am I correct?

  • Can uber-assumption framework be used as only support when defining new assumptions? I mean is it valid to claim that assumption holds based only on proof based on Theorem 1 or Corollary 1 from the paper?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.