logoalt Hacker News

hxtk • today at 3:11 AM • 0 replies • view on HN

You could certainly use zero knowledge proofs to prove some statements about the secret key, like requiring it to be roughly a 1:1 ratio of 0s and 1s and the longest run of the same bit is not significantly larger than the typical cake you’d expect in a random string that size. I think if I were trying to enforce a minimum level of security then I might take that route, requiring that the key passes zero-knowledge proofs of various statistical tests of randomness.

By pigeonhole principle, nearly all numbers have to have a Kolmogrov complexity within some constant of their own length, meaning they are algorithmically random and will by definition pass every statistical test of randomness, so you lose surprisingly few bits entropy per assertion this way.