Search papers, labs, and topics across Lattice.
This paper introduces the concept of witness complexity \(\gam(x)\), which quantifies the minimum running time required to expand near-shortest descriptions of a string on a universal Turing machine. It establishes that low Kolmogorov complexity can coexist with high witness complexity, highlighting a critical gap in cryptographic practice where compact representations may not guarantee operational efficiency. The authors prove several theoretical results, including invariance up to polynomial factors and a conditional separation assuming \(\PneqNP\), positioning witness complexity as a vital metric for evaluating the usability of cryptographic keys and certificates.
Low Kolmogorov complexity doesn't guarantee efficient expansion, revealing a critical flaw in cryptographic protocols that rely on compact representations.
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.
