Towards uncheatable benchmarks

Benchmarks have been used to test everything from the speed of a processor to the access time of a memory system. The computing community relies on them heavily to assess how fast a given hardware or software system operates. They are of fundamental importance in everyday computing. However, up until now, the study of the art of designing a good benchmark has focused on making the benchmark 'realistic' in predicting how well it will perform for the intended applications; the issue of making benchmark results trustworthy has been relegated to 'trusted' or third party agents, and little attention has been paid to the question of making benchmarks themselves 'uncheatable'. This paper studies the problem of how one can make benchmarks resistant to tampering and hence more trustworthy. We propose some schemes that are based on modern cryptography and complexity theory to make benchmarks uncheatable. The philosophy is the same as encryption-decryption schemes, namely, we want that trust in individuals and organizations be replaced by trust in the impossibility of breaking certain computational problems.