Paper 2024/225

Universal Computational Extractors from Lattice Assumptions

Yilei Chen, Tsinghua University
Xinyu Mao, University of Southern California

Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [BHK13], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, etc. Despite its usefulness, constructing UCE in the standard model is challenging. The only known positive result is given by Brzuska and Mittelbach [BM14], who construct UCE with strongly computationally unpredictable one-query source assuming indistinguishability obfuscation (iO) and the existence of point obfuscators with auxiliary input (AIPO); they also construct UCE with $q$-query sources assuming iO and composable AIPO. On the other hand, Brzuska, Farshim, and Mittelbach [BFM14] show that the most potent version of UCE does not exist, assuming the existence of iO. In this paper, we construct UCE with strongly computationally unpredictable one-query sources from lattice assumptions based on the GGH15 encodings [GGH15], without using iO. Security is proven under the following assumptions: (1) LWE with subexponential hardness; (2) evasive LWE, which is a new assumption proposed by Wee [Wee22]; (3) the existence of AIPO in NC1. Our UCE directly implies a universal hardcore function that outputs a polynomial number of bits, giving the first lattice-based universal hardcore function without using iO. We also put forth a new primitive called obliviously programmable function as an intermediate abstraction; it makes our analysis more modularized and could be of independent interest

Available format(s)
Publication info
UCEsHardcore FunctionPoint Obfuscation
Contact author(s)
chenyilei ra @ gmail com
xinyumao @ usc edu
2024-02-16: approved
2024-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yilei Chen and Xinyu Mao},
      title = {Universal Computational Extractors from Lattice Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/225},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.