Understanding computational challenges in certifying no data leakage
Checking Leakage Witnesses versus Certifying Bounded Non-Leakage
Cryptography and SecurityComputation and Language
Summary
Sometimes it’s important to check that a computer program or language model isn’t accidentally leaking secret information. The paper by the authors looks at how hard it is to confirm when no leakage happens, depending on how the model works and what checks you can run. They identify different complexity levels for verifying leakage or certifying its absence, especially under certain technical conditions and model structures. The paper also shows through experiments that some leaks can be missed if audits don’t cover everything thoroughly.
What this means in practice
- •For machine learning engineers: Determine when automated audits can reliably certify no unintended data leakage in language models within computational limits.
- •For security analysts: Assess the computational feasibility of verifying absence of data leaks under specific decoding and model architectures for secure deployments.
Tested on simulated data.
Authors
Chao Feng, Burkhard Stiller
Abstract
When a language-model audit finds no leak, what is needed to certify non-leakage? We study guarantees over a declared prompt domain under an executable leakage criterion and decoding rule. For general bounded polynomial-time evaluators, a supplied leaking execution is polynomial-time checkable, while leak existence is \NP-complete and deterministic certification is \coNP-complete. Exact stochastic certification is $\coNP^{\PP}$-complete at every fixed rational cutoff in $(0,1)$. Restricting the computation can change these bounds. For example, certification is in \coNP\ when all randomness is a terminal draw from an efficiently computed finite probability table. Attention models admit polynomial-time certification when local dependency windows of logarithmic length precede one global head, given deterministic decoding, fixed vocabulary, exact rational weighted means, a direct binary affine readout and finite-automaton prompt domains. A construction with two global layers instead makes certification \coNP-complete over template domains, with one head per layer, polynomial width, logarithmic precision and an inverse-polynomial logit margin. Planted-secret experiments measure what finite audits miss relative to complete references. Among 30 secret--model-state pairs that leak under greedy single-prompt execution on their secret's 4,096-prompt domain, uniformly selecting 256 recorded evaluations per pair misses every leak for an expected $41.06\%$ of these pairs. Batched and single-prompt checks disagree on one complete-domain decision among all 48 fine-tuned pairs, while a same-order repeat reproduces every single-prompt output. These results distinguish computational conditions for certification from the coverage and execution conditions needed to interpret a negative audit.