Jeongho Bang
Abstract Security in machine learning is fragile when data are exfiltrated or perturbed, yet existing frameworks rarely connect data-path security to learnability. In this work, we develop an operational theory of secure learning grounded in the probably-approximately-correct (PAC) viewpoint. An explicit stopping time combines the event that a trained hypothesis attains a target accuracy with the event that a run-based validation gate halts within a finite sample budget. We derive a closed-form sufficient budget requirement for this joint PAC-within-budget guarantee under an admissible random-classification-noise channel. We then specialize the construction to a BB84-like quantum label path. Under the stated ideal single-qubit, authenticated-classical-channel, memoryless, basis-symmetric, collective-attack, asymptotic, and one- way-reconciliation assumptions, the standard Holevo bound gives the protocol-specific information-advantage criterion 1−2h(η) > 0, with the threshold ηBB84 ≃ 0.11. The quantum layer is not invoked to reduce distribution-free PAC sample complexity; rather, it turns a designer-chosen classical noise tolerance into a physically testable, protocol-dependent security condition by linking information acquisition to observable disturbance. Below the threshold, the PAC and information-advantage conditions provide complementary statistical and physical guarantees; at or above it, the present protocol and proof no longer certify the latter. Basis sifting is incorporated explicitly in the conversion from sifted-sample budgets to expected raw channel uses.