Trapdoor claw-free functions gain certifiable keys for better quantum proofs
On the Construction of Trapdoor Claw-Free Functions with Certifiable Key
Cryptography and Security
Summary
Some cryptographic tools called trapdoor claw-free functions (TCFs) help classical and quantum computers prove things to each other. Usually, these tools only guarantee security when keys are honestly made. The authors introduce a way to certify these keys, proving they are genuine without revealing secret information. This certification lets any quantum proof using TCFs be turned into a zero-knowledge proof, meaning the verifier learns nothing extra beyond the statement’s truth. They also explain limitations in cases where key certificates can leak information, making certain security assumptions impossible.
What this means in practice
- •For quantum cryptography engineers: Create zero-knowledge quantum proofs with provable guarantees by integrating key certification methods into existing TCF-based protocols.
- •For security protocol designers: Understand the limits of key certification approaches in protocols relying on injective invariance to avoid information leakage.
A theory result. No direct application yet.
Authors
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.