Concise Multi-Challenge CCA-Secure Encryption and Signatures with Almost Tight Security

Abstract. To gain strong confidence in the security of a public-key scheme, it is most desirable for the security proof to feature a tight re-duction between the adversary and the algorithm solving the underlying hard problem. Recently, Chen and Wee (Crypto ’13) described the first Identity-Based Encryption scheme with almost tight security under a standard assumption. Here, “almost tight ” means that the security re-duction only loses a factor O(λ) —where λ is the security parameter— instead of a factor proportional to the number of adversarial queries. Chen and Wee also gave the shortest signatures whose security almost tightly relates to a simple assumption in the standard model. Also re-cently, Hofheinz and Jager (Crypto ’12) constructed the first CCA-secure public-key encryption scheme in the multi-user setting with tight secu-rity. These constructions give schemes that are significantly less efficient in length (and thus, processing) when compared with the earlier schemes with loose reductions in their proof of security. Hofheinz and Jager’