arXiv:2609.25819
On the Construction of Trapdoor Claw-Free Functions with Certifiable Key
Charles Lim, Yao Ma
Abstract
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.
AI Summary
Trapdoor claw-free function (TCF) protocols generally assume honestly generated keys, although a recipient may receive a key from a malicious generator. This paper asks how to certify the required key structure without revealing the trapdoor, and when such certification is compatible with a protocol’s security. It defines a certifiable key relation—an NP relation with witnesses recoverable from honest trapdoors—and certified key generation satisfying completeness, certificate soundness, and key privacy through simulatable certificates. An extractable version additionally requires witness extraction from an accepting certifier. Relations are given for factoring-based, DDH-based, and LWE-based families. Zero-knowledge arguments of knowledge provide the generic implementation; concrete proof systems are surveyed rather than newly constructed. For LWE, the certified error bound must accommodate honest noise while remaining within the trapdoor decoding radius, $B\leq q/(C_T\sqrt{n\log q})$. The main application generalizes an existing LWE-specific zero-knowledge proof-of-quantumness transformation. The compiler attaches certificates to keys and otherwise leaves the protocol unchanged. Its theorem additionally requires *transcript simulatability*: an extracted witness must enable classical simulation of the quantum prover’s messages. Completeness, classical soundness, and zero knowledge follow respectively from certification completeness, key privacy, and extraction plus transcript simulation. Factoring- and DDH-based computational-Bell-test protocols receive explicit transcript simulators. The stated scope excludes certification of claw-freeness in protocols relying on injective invariance. Accepting certificates distinguish claw-free from injective keys, exposing the hidden family-selection bit used in measurement verification and remote state preparation. This obstruction follows from certificate soundness, independently of witness privacy.
Central claim may not hold: The abstract's universal compiler claim requires the additional, protocol-specific transcript-simulatability assumption appearing in the actual theorem. The claimed LWE certification instantiation contradicts the setup-free definition: running its public verifier on its efficient simulated certificate would distinguish claw-free keys from indistinguishable injective keys, unless certificate soundness fails. The factoring/DDH transcript simulator incorrectly samples the Hadamard outcome uniformly, whereas for a verifier choosing r = 0 the honest outcome must satisfy d·(x0 XOR x1) = 0. The supplied Bell-test instantiation has honest per-session acceptance about 0.926777, so requiring every repeated session to pass defeats rather than establishes overwhelming quantum completeness.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.