For proof of work to be fair, you need a robust & secure job that produces results with a uniform distribution of zeros and ones. FHE gives you that, while performing useful computation.