Thanks a lot! Achim. I feel the same as Emil --- the time is still not practically usable for moderately sized prime like $P=2^{64}-2^{32}+1$. So the last hope is whether the special property of binary encoding makes the problem easier than subset-sum (whose lower bounded by $p^{1-\epsilon}$. Your counter-example (the primes where all elements in $Z/p$ are some powers of 2) eliminates 99% of such hope I believe. I actually care about the situation of using a mask where legal positions are below $O(\text{log}(P)$. So there is a last 1% chance for someone to exploit this (but unlikely).