Is the following a correct formulation for the assumed worst-case hardness of $SIVP_\gamma$?

  • For every PPT algorithm $A$
  • for every $n\in\mathbb{N}$ there exists a basis $B_{n,A}=\{v_1,\dots,v_n\} \in \mathbb{Z}^n$ such that
  • Pr[A produces an answer for $SIVP_\gamma$ on $B_{n,A}$]$\to 0$ faster than any 1/poly(n).

Specifically, is that what one assumes when proving that Ajtai's family of functions is a one-way family of functions?



Your Answer

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

Browse other questions tagged or ask your own question.