Query processing over uncertain data has gained much attention recently. Due to the high computational complexity of query evaluation on uncertain data, the data owner can outsource her data to a server that provides query evaluation as a service. However, a dishonest server may return cheap (and incorrect) query answers, hoping that the client who has weak computational power cannot catch the incorrect results. To address the integrity issue, in this paper, we design AuthPDB, a framework that supports efficient authentication of query evaluation for both all-answer and top-k queries on outsourced probabilistic databases. Our empirical results on real-world datasets demonstrate the effectiveness and efficiency of AuthPDB.