PRF ⇒ OPE (BCLO09)

Fully-black-box reduction · standard model · BCLO09

Statement

Given an efficient algorithm that samples the hypergeometric distribution, used as a black box, a PRF yields a POPF-CCA-secure OPE scheme with plaintext space and ciphertext space : encryption and decryption run the lazy sampler of a uniformly random order-preserving injection , a binary search over , with the coins of each step taken from the PRF evaluated on the current search state — BCLO09, who instantiate the PRF from a blockcipher.

Sketch

At a step where the plaintexts are mapped into the ciphertexts , the search samples how many of these plaintexts land in the lower half of the ciphertext range from the hypergeometric distribution and recurses into the half that contains the queried plaintext or ciphertext. With a truly random function in place of the PRF, the scheme answers encryption and decryption queries exactly as a lazily sampled uniformly random order-preserving injection, so a POPF-CCA adversary is a PRF distinguisher.