Grateful to coauthors Matthias Caro, Ari Karchmer and Saachi Mutreja. Lots to explore: stronger adversaries, other oracles & learning tasks, and further applications of covertness. Feedback welcome! 😀

Using (iii), we show the classical–quantum query separations for Forrelation and Simon's problem persist even under covertness constraints, suggesting that quantum advantages can be realized privately and verifiably, even with untrusted, remote data! 🚀

(iii) Target-covert & verifiable acquisition of phase states from public quantum phase queries + private classical membership queries (against certain restricted adversaries): the learner obtains certified states while the adversary gains no information about the target function.

(ii) Target-covert Pauli shadow tomography and stabilizer state learning using public multi-copy + private single-copy measurements: using only the public queries, any adversary can succeed with at most negligible probability.

Our results. We instantiate the model without cryptographic hardness assumptions for several natural oracles:

(i) Strategy-covert quantum statistical queries via classical shadows: we accurately estimate expectation values, but an eavesdropper doesn’t know for which observables.

Our setting: A learner interacts with a quantum data source over a public eavesdropped channel and wants
• strategy-covertness (hide the learning algorithm) or
• target-covertness (hide the learned object)
We also equip the learner with a private but strictly weaker oracle.