Security Intuition. As intuition for why the VC scheme is sound, note that it seems hard for an adversary who does not know α to construct any pair of group elements h,hα except in the obvious way: by taking pairs (g1,g α 1 ),(g2,g α 2 ),... that he is given, and applying the same linear combination (in the exponent) to the left and right elements of the pairs. This hardness is formalized in the d-PKE assumption, a sort of “knowledge-of-exponent” assumption that says that the adversary must “...