Abstract: To improve the decryption efficiency of the Baek-Zheng scheme, a new threshold scheme was proposed based on pairing. In the new scheme, the dot product operation in the Baek-Zheng scheme is replaced by an inversion operation to design the verifying process. Because the verifying process needs only one pairing operation, the efficiency of threshold decryption is increased nearly one time, and the new scheme has the same encryption efficiency and the sizes of the ciphertext or the decryption shares, comparedwith that in the Baek-Zheng scheme. The new schemewas proved secure against chosen ciphertext attacks under theOracle-Diffie-Hellman assumption.