Post-quantum κ-to-1 trapdoor claw-free functions from extrapolated dihedral cosets

Noisy trapdoor claw-free function (NTCF) is a powerful post-quantum cryptographic tool that can efficiently constrain actions of untrusted quantum devices within a classical–quantum interactive cryptographic model. Although NTCF is powerful, its essence remains a 2-to-1 one-way function (NTCF₂¹), which is inefficient in some cryptographic tasks. This raises an intriguing question: Can NTCF be extended to higher dimensions based on standard cryptographic hardness assumptions? Inspired by the extrapolated dihedral cosets, this work focuses on developing many-to-one trapdoor claw-free functions with polynomially bounded preimage sizes. The main results can be summarized as follows: Firstly, we introduce the definition of κ-to-1 NTCF_κ¹ where κ is a polynomial integer, and present an efficient construction of NTCF_κ¹ assuming quantum hardness of the learning with errors (LWE) problem. Secondly, we illustrate a key application of NTCFs in establishing a reduction from the LWE problem to the dihedral coset problems (DCPs). Specifically, our approach, leveraging NTCF₂¹ (resp. NTCF_κ¹), reveals a new quantum reduction pathway from the LWE problem to the DCP (resp. an extrapolated version of DCP). This reduction is the core cryptographic analysis tool for studying the resistance of lattice problems against quantum attacks. Finally, we demonstrate that NTCF_κ¹ can be further reduced to NTCF₂¹, thus preserving its usefulness in proofs of quantumness.