The British Computer Society 2017. All rights reserved. We present a new type of public-key encryption called Criteria-based Encryption (or CE, for short). Different from Attribute-based Encryption, in CE, we consider the access policies as criteria carrying different weights. A user must hold some cases (or answers) satisfying the criteria and have sufficient weights in order to successfully decrypt a message. We then propose two CE Schemes under different settings: the first scheme requires a user to have at least one case for a criterion specified by the encryptor in the access structure, while the second scheme requires a user to have all the cases for each criterion. We prove that both schemes are secure under the Decisional q-Bilinear Diffie Hellman Exponent assumption without random oracles. In addition, we also present two special CE schemes for the above two settings without considering the weight requirement. We show that under this special case CE schemes can be constructed much more efficiently.