ElGamal加密方案的KDM安全性  

KDM Security of ElGamal Encryption Scheme

作　　者：常金勇[1,2] 薛锐[1] 史涛 

机构地区：[1]中国科学院信息工程研究所 信息安全国家重点实验室,北京100093 [2]长治学院数学系,长治046011 [3]北京信息科学技术研究院,北京100878

出　　处：《密码学报》2014年第3期235-243,共9页Journal of Cryptologic Research

基　　金：国家重点基础研究发展项目(973计划)(2013CB338003);中国科学院战略性科技先导专项(XDA06010701);国家自然科学基金项目(61170280)

摘　　要：一个公钥加密方案的KDM(Key-Dependent Message)安全性要求:即使敌手可以得到一些可能依赖于私钥的消息加密后的密文,它仍然是安全的.这一场景经常会出现在如:硬盘加密、形式化密码学或者一些特殊的协议中.迄今为止,已经有一些具体的方法可以达到这类安全性.但是,大多数情形中,都限制消息作为用户私钥的函数为仿射函数.本文定义了一类新的函数族,并且证明了在公钥密码学中起着非常重要作用的ElGamal加密方案关于这类函数族具有相应的KDM安全性.从技术角度来说,由于ElGamal加密方案的明文空间与私钥空间不太"匹配",因此,我们需要将原始的ElGamal加密方案进行适当的"裁剪"以证明它的KDM安全性.更为重要的是,本文定义的新的函数族自然地包含一些不属于仿射函数族的函数.另外,也证明了该方案关于Qin等人在2013年ACISP上提出的函数族也满足相应的KDM安全性.最后,我们指出,在这两种情形下,都可以将本文所得到的"裁剪的"ElGamal加密方案应用到匿名证书系统中.The KDM(key-dependent message) security of a public key encryption scheme requires that it remains secure, even if an adversary has access to encryptions of messages that depend on the secret key. Such situations naturally occur in scenarios such as hard disk encryption, formal cryptography, or some specific protocols. To date, KDM security can be achieved by a few constructions. But most of them are limited to affine functions of the secret keys. In this paper, we define a new function ensemble, and show that the ElGamal-scheme, which plays an important role in public key encryption, achieves KDM security with respect to this new ensemble. From a technical point of view, we have to 'tailor' the original ElGamal-scheme so that it is 'compatible' with the message space and the secret key space. Most importantly, the new ensemble we propose naturally contains some functions that do not belong to affine function family. Moreover, we also show that this scheme achieves KDM security with respect to the ensemble proposed by Qin et.al. at ACISP 2013. Finally, we point out that, in two cases, one can find immediate application of the 'tailored' ElGamal-scheme to anonymous credential systems.

关 键 词：KDM安全性 ElGamal方案 选择明文攻击 判定性Diffie-Hellman假设 

分 类 号：TN918.4[电子电信—通信与信息系统]