CoChat
Sign Up
PreprintCited by 1Cryptography and Data SecurityAdvanced Authentication Protocols SecurityWireless Communication Security Techniques

Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange

Open access
Vaikuntanathan, Vinod, Zamir, Or·2026·arXiv
DOI 10.48550/arxiv.2604.04757arXiv 2604.04757
Open this paper in CoChat — free accountOpen PDF

Abstract

AI agents are increasingly deployed to interact with other agents on behalf of users and organizations. We ask whether two such agents, operated by different entities, can carry out a parallel secret conversation while still producing a transcript that is computationally indistinguishable from an honest interaction, even to a strong passive auditor that knows the full model descriptions, the protocol, and the agents' private contexts. Building on recent work on watermarking and steganography for LLMs, we first show that if the parties possess an interaction-unique secret key, they can facilitate an optimal-rate covert conversation: the hidden conversation can exploit essentially all of the entropy present in the honest message distributions. Our main contributions concern extending this to the keyless setting, where the agents begin with no shared secret. We show that covert key exchange, and hence covert conversation, is possible even when each model has an arbitrary private context, and their messages are short and fully adaptive, assuming only that sufficiently many individual messages have at least constant min-entropy. This stands in contrast to previous covert communication works, which relied on the min-entropy in each individual message growing with the security parameter. To obtain this, we introduce a new cryptographic primitive, which we call pseudorandom noise-resilient key exchange: a key-exchange protocol whose public transcript is pseudorandom while still remaining correct under constant noise. We study this primitive, giving several constructions relevant to our application as well as strong limitations showing that more naive variants are impossible or vulnerable to efficient attacks. These results show that transcript auditing alone cannot rule out covert coordination between AI agents, and identify a new cryptographic theory that may be of independent interest.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2604.04757

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Free-form protocols enable new threats like secret collusion and coordinated swarm attacks.

    “Free-form protocols are essential for AI's task generalization but enable new threats like secret collusion and coordinated swarm attacks.”

    From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Vaikuntanathan & Zamir, 2026

    The Introduction and §9 Discussion and Open Problems support the threat of secret communication: two agents can carry on a hidden conversation during an ordinary interaction, even under passive auditing. The paper does not establish that free-form protocols are essential for task generalization or discuss coordinated swarm attacks. (LLM, conf=0.87)

    Experimental — accuracy not yet measured

  • A recent scheme enables agents to bootstrap secret keys in a covert fashion without the need for public-key infrastructure.

    “A recent scheme (Vaikuntanathan & Zamir, 2026) furthermore enables agents to bootstrap secret keys in a covert fashion without the need for public-key infrastructure.”

    From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Vaikuntanathan & Zamir, 2026

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 56

  1. Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, and Sam Gunn. Ideal pseudorandom codes. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1638-1647, 2025. 10, 44
  2. Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Shai Halevi, editor, Advances in Cryptology -CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, volume 5677 of Lecture Notes in Computer Science, pages 595-618. Springer, 2009. 38
  3. Ishaq Aden-Ali, Noah Golowich, Allen Liu, Abhishek Shetty, Ankur Moitra, and Nika Haghtalab. Subliminal effects in your data: A general mechanism via log-linearity. CoRR, abs/2602.04863, 2026. · arXiv
  4. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography with constant input locality. J. Cryptol., 22(4):429-469, 2009.
  5. Michael Alekhnovich. More on average case vs approximation complexity. In 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings, pages 298-307. IEEE Computer Society, 2003. 7, 38
  6. Elwyn R Berlekamp. Block coding with noiseless feedback. PhD thesis, Massachusetts Institute of Technology, 1964. 11
  7. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor, Advances in Cryptology -CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pages 278-291. Springer, 1993. 37
  8. Fabio Banfi, Konstantin Gegier, Martin Hirt, Ueli Maurer, and Guilherme Rito. Anamor- phic encryption, revisited. In Advances in Cryptology -EUROCRYPT 2024, volume 14652 of Lecture Notes in Computer Science, pages 3-32. Springer, 2024. 10
  9. Daniel J Bernstein, Mike Hamburg, Anna Krasnova, and Tanja Lange. Elligator: elliptic-curve points indistinguishable from uniform random strings. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 967-980, 2013. 10, 23
  10. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506-519, 2003.
  11. Mihir Bellare, Kenneth G. Paterson, Phillip Rogaway, and Thomas Shrimpton. Algo- rithm substitution attacks from a steganographic perspective. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2017.
  12. Gilles Brassard and Louis Salvail. Secret-key reconciliation by public discussion. In Tor Helleseth, editor, Advances in Cryptology -EUROCRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, pages 410-423. Springer, 1993. 39
  13. Christian Cachin. An information-theoretic model for steganography. In Information Hiding, volume 1525 of Lecture Notes in Computer Science, pages 306-318. Springer, 1998.
  14. Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. In Annual International Cryptology Conference, pages 325-347. Springer, 2024. 8, 10, 17, 27, 44
  15. Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs. Improved pseudorandom codes from permuted puzzles. arXiv preprint arXiv:2512.08918, 2025. · arXiv
  16. Dario Catalano, Emanuele Giunta, and Francesco Migliaro. Anamorphic encryption: New constructions and homomorphic realizations. In Advances in Cryptology -EU- ROCRYPT 2024, volume 14652 of Lecture Notes in Computer Science, pages 33-62. Springer, 2024. 10
  17. Dario Catalano, Emanuele Giunta, and Francesco Migliaro. Limits of black-box anamor- phic encryption. In Advances in Cryptology -CRYPTO 2024, Lecture Notes in Computer Science, pages 352-383. Springer, 2024. 10
  18. Dario Catalano, Emanuele Giunta, and Francesco Migliaro. Generic anamorphic encryption, revisited: New limitations and constructions. In Advances in Cryptology -EUROCRYPT 2025, Lecture Notes in Computer Science, pages 275-303. Springer, 2025. 10
  19. Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194, 2023. 3, 4, 5, 7, 10, 17, 18, 24, 27, 31 · arXiv
  20. Ruina Chen, Haitao Liu, and Gabriel Altmann. Entropy in different text types. Digital Scholarship in the Humanities, 32(3):528-542, 2017. 17, 24
  21. Chongwon Cho, Chen-Kuei Lee, and Rafail Ostrovsky. Equivalence of uniform key agreement and composition insecurity. In Annual Cryptology Conference, pages 447-464. Springer, 2010. 10, 23
  22. Thomas M Cover. The role of feedback in communication. In Performance Limits in Communication Theory and Practice, pages 225-235. Springer, 1988.
  23. Xue Chen, Wenxuan Shu, and Zhaienhe Zhou. Algorithms for sparse LPN and LSPN against low-noise (extended abstract). In Nika Haghtalab and Ankur Moitra, editors, The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France, volume 291 of Proceedings of Machine Learning Research, pages 1091-1093. PMLR, 2025. 7, 37
  24. Martin Degeling, Lena Frömmgen, Thomas Schneider, et al. Meteor: Cryptographically secure steganography for realistic distributions. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2021.
  25. Dana Dachman-Soled, Huijing Gong, Hunter Kippen, and Aria Shahverdi. BKW meets fourier new algorithms for LPN with sparse parities. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography -19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II, volume 13043 of Lecture Notes in Computer Science, pages 658-688. Springer, 2021. 7, 37
  26. WHITFIELD DIFFIE and MARTIN E HELLMAN. New directions in cryptography. IEEE TRANSACTIONS ON INFORMATION THEORY, 22(6), 1976. 10, 23
  27. Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. arXiv preprint arXiv:2308.00113, 2023. 10 · arXiv
  28. Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Publicly-detectable watermarking for language models. IACR Commun. Cryptol., 1(4):31, 2024.
  29. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput., 39(2):606- 645, 2009. 7, 37
  30. Dmitriy Genzel and Eugene Charniak. Entropy rate constancy in text. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 199-206, 2002. 17, 24
  31. Noah Golowich and Ankur Moitra. Edit distance robust watermarks via indexing pseudorandom codes. Advances in Neural Information Processing Systems, 37:20645- 20693, 2024.
  32. Elena Grigorescu, Lev Reyzin, and Santosh S. Vempala. On noise-tolerant learning of sparse parities and related problems. In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann, editors, Algorithmic Learning Theory -22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings, volume 6925 of Lecture Notes in Computer Science, pages 413-424. Springer, 2011. 7, 37
  33. Nicholas J Hopper, John Langford, and Luis Von Ahn. Provably secure steganography. In Advances in Cryptology-CRYPTO 2002: 22nd Annual International Cryptology Conference Santa Barbara, California, USA, August 18-22, 2002 Proceedings 22, pages 77-92. Springer, 2002. 9, 67
  34. Thomas Holenstein. Key agreement from weak bit agreement. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 664-673. ACM, 2005.
  35. Michael Horstein. Sequential transmission using noiseless feedback. IEEE Transactions on Information Theory, 9(3):136-143, 1963. 9, 11, 63
  36. Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, January 10-12, 2019, volume 124 of LIPIcs, pages 42:1-42:20. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2019. 4, 5, 6, 10, 23, 24
  37. Russell Impagliazzo, Leonid A Levin, and Michael Luby. Pseudo-random generation from one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 12-24, 1989. 12, 13
  38. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. arXiv preprint arXiv:2301.10226, 2023. · arXiv
  39. Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1067-1080. ACM, 2017. 7, 37
  40. Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023. · arXiv
  41. Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Extractors: Optimal up to constant factors. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 602-611, 2003.
  42. Ueli M. Maurer. Protocols for secret key agreement by public discussion based on common information. In Ernest F. Brickell, editor, Advances in Cryptology -CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, volume 740 of Lecture Notes in Computer Science, pages 461-470. Springer, 1992. 38
  43. Ryan O'Donnell. Analysis of boolean functions. arXiv preprint arXiv:2105.10386, 2021. 43, 46 · arXiv
  44. Giuseppe Persiano, Duong Hieu Phan, and Moti Yung. Anamorphic encryption: Private communication against a dictator. In Advances in Cryptology -EUROCRYPT 2022, volume 13276 of Lecture Notes in Computer Science, pages 34-63. Springer, 2022. 10
  45. Ofer Shayevitz and Meir Feder. Optimal feedback communication via posterior matching. IEEE Transactions on Information Theory, 57(3):1186-1222, 2011. 9, 11, 63
  46. Gustavus J. Simmons. The prisoners' problem and the subliminal channel. In David Chaum, editor, Advances in Cryptology: Proceedings of CRYPTO '83, pages 51-67, New York, 1984. Plenum Press.
  47. Yaqian Shi and Lei Lei. Lexical richness and text length: An entropy-based perspective. Journal of Quantitative Linguistics, 29(1):62-79, 2022. 17, 24
  48. Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. In Frank Thomson Leighton and Allan Borodin, editors, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 388-397. ACM, 1995.
  49. Michael Sipser and Daniel A. Spielman. Expander codes. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, November 20-22, 1994, pages 566-576. IEEE Computer Society, 1994. 39
  50. Salil P Vadhan et al. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1-3):1-336, 2012.
  51. Luis Von Ahn and Nicholas J Hopper. Public-key steganography. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 323-341. Springer, 2004. 4, 5, 6, 9, 22, 23, 24
  52. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 11-20. IEEE Computer Society, 2012. 7, 37
  53. Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. Towards codable text watermarking for large language models. arXiv preprint arXiv:2307.15992, 2023. 10 · arXiv
  54. KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for language models. arXiv preprint arXiv:2308.00221, 2023. 10 · arXiv
  55. Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. arXiv preprint arXiv:2306.17439, 2023. 10 · arXiv
  56. Or Zamir. Undetectable steganography for language models. Transactions on Machine Learning Research, 2025. 3, 4, 5, 10, 17, 18, 19, 20, 21, 24

Cited by

Sorted by citations

Authors
Vaikuntanathan, V., & Zamir, O.
Affiliations
  • Massachusetts Institute of Technology (US)
  • Tel Aviv University (IL)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2026
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2604.04757
arXiv
2604.04757
OpenAlex
W7151265183
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
  • Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Authentication Protocols Security
  • Physical Sciences › Engineering › Electrical and Electronic Engineering › Wireless Communication Security Techniques
Keywords
covert communication, AI agents, LLM watermarking, min-entropy, cryptographic primitives, adversarial perturbations

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review