Space bounded adversaries

Space-bounded Adversaries

  • Suppose an adversary is space bounded by \(S \ll q\), where \(q\) is the number of queries
  • It can still distinguish between real/ideal world using adaptive queries with advantage \(O(q^{2}/2^{\lambda})\) and space \(2\lambda\)
  • Adaptive queries means that an adversary can query any point any time
  • The matching algorithm is as follows:
    • Adversary keeps two pointers \(y_1=F(x_0)\) and \(y_2=F(x_0)\).
    • It updates \(y_1 = F(y_1)\), \(y_2 = F(F(y_2))\)
    • Eventually, they will meet if the function is a random function