DDH ⇒ Key-hiding PKE (ElGamal)
Statement
Let all users share common parameters , and let the ElGamal scheme of ElGamal85 over have , , and for in the message space , which the common parameters fix for every key, and . If DDH is hard for , ElGamal is IK-CPA-secure — BBDP01 — and CPA-secure — TY98 — so it is a key-hiding PKE.
Sketch
On a DDH challenge , the reduction sets , samples the other key pair itself, and answers the challenge query with . For this is the IK-CPA game with that ; for uniform the challenge is a uniform pair independent of both keys. Two such hybrids, one for each , bound the IK-CPA advantage by twice the DDH advantage — standard.
Notes
- BBDP01 also prove that the Cramer–Shoup scheme over a common group is IK-CCA-secure under the assumptions under which it is IND-CCA2-secure — BBDP01.