论文标题
Quantum $κ$ -to-1陷阱的陷阱夹具的功能
Post-Quantum $κ$-to-1 Trapdoor Claw-free Functions from Extrapolated Dihedral Cosets
论文作者
论文摘要
\ emph {嘈杂的陷阱门无爪功能}（NTCF）作为功能强大的量子后加密工具可以有效地约束不受信任的量子设备的动作。但是，原始的NTCF本质上是\ emph {2-to-1}单向函数（NTCF $^1_2 $）。在这项工作中，我们尝试进一步扩展NTCF $^1_2 $，以实现具有多项式界限的预映率大小的陷阱{多到ONE}陷阱爪功能。具体而言，我们通过绘制外推二面壳的方式专注于NTCF $^1_2 $的显着外推，从而给出了NTCF $^1_κ$的模型，其中$κ$是多项式整数。然后，我们提出了一个有效的NTCF $^1_κ$的构造，假设\ emph {学习错误（LWE）}问题的量子硬度。我们指出，NTCF可以用来桥接LWE和二面框问题（DCP）。通过利用NTCF $^1_2 $（分别为ntcf $^1_κ$），我们的工作揭示了从LWE问题到DCP的新量子减少路径（分别推断的DCP）。最后，我们证明了NTCF $^1_κ$自然可以减少到NTCF $^1_2 $，从而实现了证明量子性的相同应用。
\emph{Noisy trapdoor claw-free function} (NTCF) as a powerful post-quantum cryptographic tool can efficiently constrain actions of untrusted quantum devices. However, the original NTCF is essentially \emph{2-to-1} one-way function (NTCF$^1_2$). In this work, we attempt to further extend the NTCF$^1_2$ to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF$^1_2$ by drawing on extrapolated dihedral cosets, thereby giving a model of NTCF$^1_κ$ where $κ$ is a polynomial integer. Then, we present an efficient construction of NTCF$^1_κ$ assuming \emph{quantum hardness of the learning with errors (LWE)} problem. We point out that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP). By leveraging NTCF$^1_2$ (resp. NTCF$^1_κ$), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCF$^1_κ$ can naturally be reduced to the NTCF$^1_2$, thereby achieving the same application for proving the quantumness.
