Certain applications of fully homomorphic encryption (such as transciphering, universal thresholdizers, and PIR) require randomness while operating over encrypted data. This randomness has to be obliviously generated in the encrypted domain and remain encrypted throughout the computation. Moreover, it should be guaranteed that independent-looking random coins can be obliviously generated for different computations.