Post-Quantum $κ$-to-1 Trapdoor Claw-free Functions from Extrapolated Dihedral Cosets

Noisy Trapdoor Claw-free functions (NTCF) as powerful post-quantum cryptographic tools can efficiently constrain actions of untrusted quantum devices. Recently, Brakerski et al. at FOCS 2018 showed a remarkable use of NTCF for a classically verifiable proof of quantumness and also derived a protocol for cryptographically certifiable quantum randomness generation. However, the original NTCF used in their work is essentially 2-to-1 one-way function, namely NTCF$^1_2$, which greatly limits the rate of randomness generation. In this work, we attempt to further extend the NTCF$^1_2$ to achieve a $\kappa$-to-1 function with poly-bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF$^1_2$ by drawing on extrapolated dihedral cosets, giving a model of NTCF$^1_{\kappa}$ with $\kappa = poly(n)$. Then, we present an efficient construction of NTCF$^1_{\kappa}$ under the well-known quantum hardness of the Learning with Errors (QLWE) assumption. As a byproduct, our work manifests an interesting connection between the NTCF$^1_2$ (resp. NTCF$^1_{\kappa}$) and the Dihedral Coset States (resp. Extrapolated Dihedral Coset States). Finally, we give a similar interactive protocol for proving quantumness from the NTCF$^1_{\kappa}$.