Oblivious Key-Value Stores and Amplification for Private Set Intersection

Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping \(k_i \mapsto v_i\). When the \(v_i\) values are random, the OKVS data structure hides the \(k_i\) values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial p that is chosen using interpolation such that \(p(k_i)=v_i\).