DDH ⇒ PRE (Blaze–Bleumer–Strauss scheme)

Fully-black-box reduction · standard model · folklore · security loss: tight up to a factor 2: one run of the CPA adversary gives , the additive term from the event that is the identity

Statement

If DDH is hard in prime-order groups, the following bidirectional, multi-hop scheme of BBS98 is a CPA-secure PRE scheme with message space — folklore. outputs , a group of prime order with generator , where is the group generator for which DDH is assumed hard; user has and ; for ; ; the re-encryption key is , computed from both secret keys, and — BBS98.

Sketch

Given , the reduction keeps , gives each uncorrupted user for , so that and between uncorrupted users, samples the keys of corrupted users itself, and answers the challenge for with . If this is an encryption of with ; if is uniform, appears only in the first component, which is then uniform and independent of .

Notes

  • A delegatee holding and the proxy’s recovers , so the scheme is not collusion resistant; and , so it is bidirectional — folklore.