PRF ⇒ ORE leaking the first differing bit (CLWW16)

Fully-black-box reduction · standard model · CLWW16

Statement

Let be a PRF with range on inputs with and . The ORE scheme on with

  • : a key for ;
  • with ;
  • : for the least with , output if and otherwise; output if there is no such

is correct and secure with leakage of the order and the first differing bit — CLWW16.

Sketch

Two encryptions agree up to the first differing bit of their plaintexts and differ there by , the sign giving the order. With a truly random function in place of , the simulator copies, for each new query, the first components of an earlier ciphertext that shares the longest prefix, sets the -th component to that ciphertext’s -th component plus or minus as the order dictates, and samples the remaining components uniformly; all of this is computable from the leakage.

Notes

  • A ciphertext has elements of , about bits, and encryption takes PRF evaluations — CLWW16.