On the Construction of Trapdoor Claw-Free Functions with Certifiable Key
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.
Related
- Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions
- Trapdoor Functions with Secure Key Leasing and Copy Protection
- [SUPERSEDED] Physics-Informed AI and Quantum Technologies for Certifiable Real-Time Control of Compact Fusion Generators
- Diagrammatic construction of GKZ systems for polygonal functions
- Universal Construction of Generalized Lyapunov Functions for Nonlinear Dynamical Systems Using Physics-Informed Neural Networks
BibTeX
@misc{lim2026construction,
title = {{On the Construction of Trapdoor Claw-Free Functions with Certifiable Key}},
author = {Charles Lim and Yao Ma},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25819},
eprint = {2609.25819},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25819},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Construction of Trapdoor Claw-Free Functions with Certifiable Key
AU - Charles Lim
AU - Yao Ma
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25819
UR - https://arxiv.org/abs/2609.25819
AB - 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.
ER -