DDH ⇒ Universal-2 HPS
Statement
Let output groups of prime order , with membership in decidable in polynomial time, for which DDH is hard, and let the instance be with a uniformly random generator of . The subset membership problem with , and witness is hard, and it has a universal-2 hash proof system — CS02:
- smooth: , , , so ;
- extended universal-2 for tags : a hash proof system for the same language whose hash takes as input; it handles tags of any length with more key components, so no hash function is needed.
The instance, subset and key approximation errors are : is sampled exactly, makes uniform on , and keys are uniform vectors over , so the properties hold for the families themselves — standard.
Sketch
Hardness: with , a DDH challenge gives the element , which lies in when and is uniform in when is uniform conditioned on , which is -close to uniform. Smoothness: for with , the exponents of and in base are and , linearly independent functions of , so is uniform given .
Notes
- The Cramer–Shoup cryptosystem, with in place of and decryption by , is a variant of the generic CCA construction (Universal-2 HPS ⇒ CCA-secure PKE) over this language, with the input of the universal-2 component compressed to by a universal one-way hash function and the validity tag for the universal-2 key — CS02.
- NS09 give a DDH- and -Linear-based hash proof system whose IND-CPA-secure encryption scheme tolerates leakage of a fraction of the bits of its secret key: DDH ⇒ LR-PKE, d-Linear ⇒ LR-PKE.