PRF ⇒ ORE leaking the first differing bit (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.