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$


    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?


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.