ElGamal加密方案的KDM安全性

KDM Security of ElGamal Encryption Scheme

一个公钥加密方案的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.