Abstract
\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¹₂). In this work, we attempt to further extend the NTCF¹₂ to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF¹₂ by drawing on extrapolated dihedral cosets, thereby giving a model of NTCF¹_κ where κ is a polynomial integer. Then, we present an efficient construction of NTCF¹_κ 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¹₂ (resp. NTCF¹_κ), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCF¹_κ can naturally be reduced to the NTCF¹₂, thereby achieving the same application for proving the quantumness.