{"ID":5438749,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T08:54:25.326461322Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31370","arxiv_id":"2606.31370","title":"Witness Complexity of Short Descriptions: A Cryptographic Perspective","abstract":"In cryptographic practice, where protocols impose strict time bounds, implementations demand predictable resource usage, and real-world systems require immediate verification for security and usability, a short key or certificate is useful only if it can be expanded or verified within a bounded time; otherwise a compact representation that requires superpolynomial work to expand offers no operational guarantee within a bounded-time protocol. This paper formalises that gap by introducing \\emph{witness complexity} \\(\\gam(x)\\), the minimum running time over near-shortest descriptions of a string on a universal Turing machine. \\(\\gam\\) differs from Shannon entropy and Kolmogorov complexity \\(\\KC\\): low \\(\\KC\\) can coexist with high \\(\\gam\\). We prove invariance up to polynomial factors; a conditional separation (assuming \\(\\PneqNP\\)). An unconditional lower bound from incomputability of \\(\\KC\\); a biconditional characterisation of \\(\\PeqNP\\) via the class-relative variant \\(\\gP\\); and polynomial-time tractability for structured \\(\\classNP\\) families. Part II develops companion measures and shows an unconditional gap between grammar size and derivation cost, positioning \\(\\gam\\) as a metric for the usability of keys and certificates.","short_abstract":"In cryptographic practice, where protocols impose strict time bounds, implementations demand predictable resource usage, and real-world systems require immediate verification for security and usability, a short key or certificate is useful only if it can be expanded or verified within a bounded time; otherwise a compac...","url_abs":"https://arxiv.org/abs/2606.31370","url_pdf":"https://arxiv.org/pdf/2606.31370v1","authors":"[\"Fabio F. G. Buono\"]","published":"2026-06-30T09:02:35Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.CC\"]","methods":"[]","has_code":false}