International Association
for Cryptologic Research

We put forth a new primitive called obliviously programmable function (OPF) to construct two random-oracle-like primitives: – Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [3], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, universal hardcore bits, etc. – Multi-bit point obfuscation with auxiliary input (MB-AIPO). It enables upgrading CPA-secure public-key encryption (PKE) into a CCA-secure one [30] and serves as a tool to instantiate the random oracles used in the Fujisaki-Okamoto transform for lossy PKEs [32]. Despite their usefulness, constructing UCEs and MB-AIPO in the standard model is challenging. The existing constructions of both primitives [15,16] use indistinguishability obfuscation (iO) plus point functions with auxiliary input (AIPO). OPF can replace the use iO in the constructions of UCE and MB-AIPO. We use OPF plus AIPO to construct – UCE with one query for strongly unpredictable sources, – MB-AIPO for strongly unpredictable distributions and – PKE scheme that is IND-CPA secure in the presence of computationally uninvertible leakage on the secret key. We then construct OPF for NC1 circuits from lattice assumptions based on the GGH15 encodings [23], without using iO. In sum, we give new constructions of the above three primitives under the following assumptions: (1) LWE with subexponential hardness; (2) private-coin evasive LWE assumption for specific samplers; (3) the existence of AIPO in NC1. As a byproduct, we construct a ‘NC1-universal AIPO’ under the assumptions (1) and (2).