Trapdoor claw-free functions (TCFs) underpin much of classical-quantum cryptographic interaction, yet every TCF-based protocol states its guarantees relative to an honestly generated key. We give a family-agnostic abstraction of key certification for (noisy) TCF constructions, built on two notions: a certifiable key relation, an NP relation capturing a family's honest keys with witnesses recoverable from the trapdoor; and certified key generation, which emits with each key a certificate of membership satisfying completeness, certificate soundness with extractability, and key privacy. We instantiate certifiable key relations for different constructions, each met generically by a zero-knowledge argument of knowledge for the relation. As our main application, a generic compiler turns any TCF-based proof of quantumness into a zero-knowledge one, with each security property following from its counterpart in the certification scheme. Finally, we delimit the primitive's reach: for protocols resting on injective invariance, an accepting certificate is itself a family distinguisher, leaking exactly the bit such protocols must hide.Trapdoor claw-free functions (TCFs) underpin much of classical-quantum cryptographic interaction, yet every TCF-based protocol states its guarantees relative to an honestly generated key. We give a family-agnostic abstraction of key certification for (noisy) TCF constructions, built on two notions: a certifiable key relation, an NP relation capturing a family's honest keys with witnesses recoverable from the trapdoor; and certified key generation, which emits with each key a certificate of membership satisfying completeness, certificate soundness with extractability, and key privacy. We instantiate certifiable key relations for different constructions, each met generically by a zero-knowledge argument of knowledge for the relation. As our main application, a generic compiler turns any TCF-based proof of quantumness into a zero-knowledge one, with each security property following from its counterpart in the certification scheme. Finally, we delimit the primitive's reach: for protocols resting on injective invariance, an accepting certificate is itself a family distinguisher, leaking exactly the bit such protocols must hide.

cs.CRCross-listedarXiv:2609.25819Sep 23, 20260 citations

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

Xingyu Yan, Licheng Wang, Lize Gu +2 more

\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.\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.

arXiv:2211.16993Nov 30, 20220 citations

^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.