Chosen Ciphertext Security on Hard Membership Decision Groups: The Case of Semi-smooth Subgroups of Quadratic Residues
Chosen Ciphertext Security on Hard Membership Decision Groups: The Case of Semi-smooth Subgroups of Quadratic Residues
复制标题
DOI：
10.1007/978-3-319-10879-7_32
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Takashi Yamakawa;Shota Yamada;K. Nuida;Goichiro Hanaoka;N. Kunihiro
中科院分区：
文献类型：
--
作者：
Takashi Yamakawa;Shota Yamada;K. Nuida;Goichiro Hanaoka;N. Kunihiro
如今，选择密文（CCA）安全性被认为是公钥加密（PKE）事实上的标准安全概念。 CCA 安全 PKE 方案通常构建在可有效识别的组上，即相应的成员决策问题很容易的组。另一方面，当我们在不可有效识别的群体上证明 PKE 方案的 CCA 安全性时，需要非常小心。例如，即使解密查询涉及组外的意外元素并导致问题，挑战者也无法检测到它，因为组成员资格决策的难度。然而，这种可能性经常被忽视。作为这种群的一个例子，在本文中，我们考虑 Groth (TCC 2005) 提出的半光滑子群，用于提高基于因式分解的密码原语的效率。具体来说，我们提出了一种通用技术来保证半光滑子群上 PKE 方案的 CCA 安全性。粗略地说，我们证明，对于几乎所有自然的“验证方程”，如果因式分解问题很困难，则不可能生成不包含组中元素且满足方程的查询。因此，即使模拟器无法识别这些组件是否在组中，组件不在组中的查询也会被自动拒绝。通过同样的技术，我们还证明了在因式分解假设下，强 Diffie-Hellman 假设在“有符号”半光滑子群上成立，并通过在半光滑子群上实例化，提高了基于因式分解的非交互式密钥交换方案的效率。
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 thesemi-smooth subgroupwhich 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 non-interactive key exchange scheme by instantiating it on the semi-smooth subgroup.