DNA‐Based Zero‐Knowledge Cryptography Using Biochemically Encoded Graph Isomorphism

ABSTRACT

A zero‐knowledge proof lets one party convince another that a claim is true while withholding everything that would explain why it is true. We move that idea off conventional hardware and into chemistry, encoding a proof of graph isomorphism directly in synthetic DNA. Each node of a graph is given its own deliberately orthogonal DNA strand; an edge is confirmed only when a short complementary half‐linker meets its matching pair and forms a stable duplex. The verifier watches which bindings occur, but the pattern of binding never reveals how the two graphs line up, so the isomorphism stays hidden. Whether such a construction stays secure at the molecular level turns on two things: how distinguishable the sequences are, and how stable the duplexes they form turn out to be. We probe both. A seeded Monte Carlo study of orthogonal 20‐m libraries, built with balanced GC content and a minimum Hamming separation of , places the chance that an off‐target strand passes for a genuine linker on the order of : empirically at a binding threshold of mismatches, and under once the threshold is tightened to , each value reported with a Wilson confidence interval. This molecular error never becomes the bottleneck. A cheating prover already passes a round with probability one‐half from the isomorphism challenge alone, so the biochemical term enters soundness only as an additive correction, over the edges examined, rather than racing the decay across rounds. Read this way, DNA strands behave as cryptographic witnesses whose noise is small enough to bound and to account for, which lets a proof run at molecular scale without surrendering the hidden mapping.