This week I spent a lot of time exploring the existing literature, and trying to understand what is possible to accomplish in the domain of uniformity testing. So far, it’s not looking the best. We’re trying to test uniformity of random sources, but all the directions I’m looking at pose issues.
- If we have a very large domain (say bit strings of length ), nothing can be said about uniformity unless we have an samples.
- If we do not care about pure uniformity and only require statistical assurance of some properties about the sequence, existing test suites do a pretty good job already (TestU01, NIST).
- Say a program only requires some conditions of the randomness in order to run properly. I don’t think this can be analyzed generally, as deriving such properties of automata would probably be equivalent to the Halting problem. The best we can do here would likely fall under formal verification (quite a departure from the current topic).
Although I’m feeling more lost than ever, I did read quite a lot of literature. I am also convinced of two truths. Spot the lie!
- Randomness is hard.
- I know what I am doing.
- There are no standards in complexity theory.
Hopefully next meeting will give more insights.
Papers:
- NIST Test Suite https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf
- PCG https://www.pcg-random.org/paper.html
- Distribution Testing (in progress) https://ccanonne.github.io/files/misc/main-survey-fnt.pdf
Skimmed:
- Trapdoor Functions https://www.di.ens.fr/users/phan/secuproofs/yao82.pdf
- Generalized Uniformity Testing https://arxiv.org/pdf/1708.04696
- Properties of tests for uniformity https://ieeexplore.ieee.org/document/7040743