I am seeking a mathematical construct to use as a logical coin for the purpose of making hypothetical decision theory problems slightly more aesthetically pleasing. The required features are:

• Unbiased. It gives (or can be truncated or otherwise resolved to give) a 50/50 split on a boolean outcome.
• Indexable. The coin can be used multiple times through a sequence number. eg. "The n-th digit of pi is even".
• Intractable. The problem is too hard to solve. Either because there is no polynomial time algorithm to solve it or just because it is somewhat difficult and the 'n' supplied is ridiculous. eg. "The 3^^^3 digit of pi is even".
• Provable or otherwise verifiable. When the result of the logical coin is revealed it should be possible to also supply a proof of the result that would convince a mathematician that the revealed outcome is correct.
• Simple to refer to. Either there is a common name for the problem or a link to a description is available. The more well known or straightforward the better.

NP-complete problems have many of the desired features but I don't know off the top of my head any that can be used as indexable fair coin.

Can anyone suggest some candidates?