Chosen ciphertext security on hard membership decision groups: The case of semi-smooth subgroups of quadratic residues

Nowadays, the chosen ciphertext (CCA) security is considered as the de facto standard security notion for public key encryption (PKE). CCA secure PKE schemes are often constructed on efficiently recognizable groups i.e., groups where the corresponding membership decision problem is easy. On the other hand, when we prove the CCA security of PKE schemes on not efficiently recognizable groups, much care are required. For example, even if a decryption query involves an unexpected element out of the group which causes a problem, the challenger cannot detect it due to the hardness of the membership decision for the group. However, such a possibility is often overlooked. As an example of such a group, in this paper, we consider the semi-smooth subgroup which was proposed by Groth (TCC 2005) for enhancing efficiency of factoring-based cryptographic primitives. Specifically, we propose a general technique to guarantee the CCA security of PKE schemes on the semi-smooth subgroup. Roughly speaking, we prove that for almost all natural “verification equations,” it is impossible to generate a query which does not consist of elements in the group and satisfies the equation if the factoring problem is hard. Hence, queries whose components are not in the group will be automatically rejected even though the simulator cannot recognize whether these components are in the group or not. By the same technique, we also prove that the strong Diffie-Hellman assumption holds on the “signed” semi-smooth subgroup under the factoring assumption, and improve the efficiency of a factoring-based noninteractive key exchange scheme by instantiating it on the semi-smooth subgroup.