Randomization of quantum states is the quantum analogue of the classical one-time pad. In earlier work, we noted an improved, efficient construction of an approximately randomizing map that uses O(d/epsilon2) Pauli operators to map any d-dimensional state to a state that is within epsilon (in trace distance) of the completely mixed state. This bound is a log d factor smaller than that of Hayden, Leung, Shor, and Winter (2004), and Ambainis and Smith (2004). In this talk, we will discuss the optimality of the above scheme via its connection to a new notion of pseudorandomness.