4 ms·
No, there are complexity classes for random algorithms. And randomness is also crucial for some cryptographic protocols, typically you want to show that the pro
by pca006132 3y ago
No, there are complexity classes for random algorithms. And randomness is also crucial for some cryptographic protocols, typically you want to show that the probability the adversary can do what they want is very slim, e.g. 2^-n for some large n.
- hinkley 3y agoIn crypto we are worried about the best case scenario (from the attacker’s perspective). Randomization in algorithms, to avoid worst case behavior, would be things like shuffling input, XORing hashes for query parameters per run or per hash table, or using random tiebreakers.
- pca006132 3y agoYeah randomization in algorithms and crypto serve different purpose. But overall introducing randomness can allow you to do amazing things that deterministic algorithm/schemes cannot do.
- kadoban 3y ago> In crypto we are worried about the best case scenario (from the attacker’s perspective). That seems mistaken to me. The best case in most crypto, from an attacker's perspective, is "I tried one key and just happened to get it right". Aren't we more interested in expected outcomes?
- hinkley 3y agoIn the sense of big O you’re right and I misspoke. When we are deciding to retire an algorithm it’s often down to how many unaddressed weaknesses there are and assuming that they compose. That’s the best case I was referring to.
- wbl 3y agoThat's completely untrue. For example there's an easy randomized algorithm to determine a quadratic nonresidue modulo a prime with success probability 1/2 per Legendre symbol evaluation. In expectation this is 2 iterations, and that's independent of the prime. The best known deterministic algorithm takes log(p)^2 such evaluations in the worst case, even assuming generalized Riemann hypothesis.