Sketches, using ideal hash functions I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.).  They use hash functions that are required to be 2-independent or 4-independent or $k$-independent for some small $k$.

However from cryptography we have fast hash functions that are very good candidates to essentially perfect: $k$-independent for every value of $k$ you could ever wish for, and so on.  We can essentially treat them as uniformly chosen from the set of all functions: as far as we know, no polynomial-time computation can tell that this is not the case.  I suspect many practitioners might be happy to use these cryptographic hash functions, if it led to improved performance or better parameters for the sketches.

Does it change anything about the design and analysis of sketches, if we assume we have perfect hash functions like this?  Can we get asymptotically better parameters if we assumed our hash function was perfect?  Or, can we get simpler sketch constructions?

(For instance, I've noticed that the analysis of existing sketches is often somewhat conservative: e.g., it uses the Markov bound or Chebyshev bound.  If we had a perfect hash function we could use a Chernoff-style bound.  Are there any sketches where this makes a significant difference, or is it just a small constant factor in the bound?)
The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of space, then what you need from your PRNG is that its output cannot be distinguished from a stream of random bits by a small space algorithm. Such a PRNG was constructed by Nisan, and the proof of pseudorandomness is unconditional. 

A seminal paper in streaming algorithms that used Nisan's generator is Indyk's work on sketches of $L_1$. Since the sketch uses Cauchy random variables for which the mean and the variance do not exist, the usual moment calculations do not work, so it is hard to imagine how to use $k$-wise independence. That's why the heavy hammer of Nisan's generator comes handy.

A problem with these heavy hammers is that they come at a cost in space. The seed needs to be stored in memory, and for Nisan's generator the seed length is roughly $S\log R$ where $R$ is the number of random bits and $S$ is the space complexity of the algorithm. So you end up multiplying the space complexity by roughly the logarithm of the stream length $n$. If you can use $k$-wise independence you usually add a term like $O(k\log n)$ to the space complexity.