DDH ⇒ Key-hiding PKE (ElGamal)

Fully-black-box reduction · standard model · BBDP01, TY98

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