Scholarlink

We put forth a new primitive called obliviously programmable function (OPF) to construct two random-oracle-like primitives: 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 We then construct OPF for \(\textsf{NC}^1\) 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 \(\textsf{NC}^1\) . As a byproduct, we construct an ‘ \(\textsf{NC}^1\) -universal AIPO’ under the assumptions (1) and (2).

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Universal Computational Extractors and Multi-Bit AIPO from Lattice Assumptions

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yilei Chen,
  • Xinyu Mao

摘要

We put forth a new primitive called obliviously programmable function (OPF) to construct two random-oracle-like primitives: 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 We then construct OPF for \(\textsf{NC}^1\) 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 \(\textsf{NC}^1\) . As a byproduct, we construct an ‘ \(\textsf{NC}^1\) -universal AIPO’ under the assumptions (1) and (2).