DDH ⇒ Universal-2 HPS

Fully-black-box reduction · standard model · CS02 · security loss: the subset-membership advantage is at most the DDH advantage plus 1/q; the smooth component is perfectly smooth

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