We prove an ( d lg n ( lg lg n ) 2 ) lower bound on the dynamic cell-probe complexity of statistically obliviou s approximate-near-neighbor search (ANN) over the d -dimensional Hamming cube. For the natural setting of d = ( log n ) , our result implies an ( lg 2 n ) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic unconditiona l lower bound for ANN against general (non black-box) data structures. We also show that any oblivious stati c data structure for decomposable search problems (like ANN) can be obliviously dynamized with O ( log n ) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).