My first idea is to use something based on cryptography. For example, using the parity of the pre-image of a particular output from a hash function.
That is, the parity of x in this equation:
f(x) = n, where n is your index variable and f is some hash function assumed to be hard to invert.
This does require assuming that the hash function is actually hard, but that both seems reasonable and is at least something that actual humans can't provide a counter example for. It's also relatively very fast to go from x to n, so this scheme is easy to verify.
If it's worth saying, but not worth its own post (even in Discussion), then it goes here.