Tell HN: Perfect – not statistical – ZKP for Kolmogorov complexity

by seccode on 2/24/2025, 6:44:13 PM with 2 comments
I had this idea that enumerating all strings<=len(string) constitutes a zero-knowledge proof of Kolmogorov complexity. In enumeration, the proof is "said," but the verifier has no way of retrieving the proof. This aligns with tradition ZKP principles, although this ZKP is different than most in that neither the prover nor the verifier knows the proof. I would like to know if anyone has thoughts on this idea or possible implications that you can prove Kolmogorov complexity but you can't know it

  • by seccode on 2/24/2025, 7:02:54 PM

    There is a well-known paper related to a statistical zero-knowledge proof about Kolmogorov complexity, but this proof introduced is considered a perfect ZKP

  • by aghilmort on 2/25/2025, 5:26:44 AM

    one place such a beast might exist is at the holographic bulk/boundary limit esp. if message adiabatically describable in some quantum system