Signed Knowledge Bases and Private Retrieval: A Security-by-Design Architecture for LLM Agents' Semantic Memory

Proposes cryptographic signatures + private information retrieval to protect multi-agent LLM systems from memory poisoning — the agent equivalent of slipping bad entries into a trusted encyclopedia.

Imagine a librarian who fetches books for you without ever learning which book you asked for — and every book has a tamper-evident seal so you know nobody swapped a page. That's the core mechanism here: combining Private Information Retrieval (PIR) with signed knowledge bases so that LLM agents can query external semantic memory without leaking what they're looking for, and without trusting that nobody has poisoned the answers. The committed claim: by pairing a local Prolog-like inference engine (Horn clauses) with an externally hosted, cryptographically signed knowledge base accessed through PIR protocols, you can prevent semantic memory poisoning attacks on multi-agent systems — security by design rather than detection after the fact. The paper positions this as the first architecture to combine these two primitives specifically for agentic AI memory protection. The architecture leans on a clean separation: the agent reasons locally using Horn clause inference, but facts come from an external signed knowledge base. The signing prevents unauthorized modification (integrity), while PIR prevents the knowledge-base server from learning which facts the agent retrieves (confidentiality). The authors implement multiple privacy tiers in Python — k-anonymity (you hide among k similar queries) and information-theoretic PIR (IT-PIR, where the server learns literally zero bits about your query, even with unbounded compute). This is a meaningful design choice: IT-PIR is the gold standard but expensive; k-anonymity is cheaper but weaker. Where does this sit on the ladder? Memory poisoning in multi-agent systems is a recognized threat — prior work from groups like Zou et al. on adversarial attacks and Carlini et al. on data poisoning establishes the problem. But existing defenses tend to be reactive (anomaly detection, filtering) rather than structural. The paper's contribution is the structural prevention approach: don't let poisoning happen rather than detect it afterward. However, the paper does not benchmark against these reactive defenses with comparative numbers — no false-positive rates, no latency overhead comparisons, no attack-success-rate reductions measured against a named baseline. The integrity picture is the weakest link. The validation is a Python proof-of-concept with multiple privacy implementations, but there's no adversarial red-teaming, no formal security proof beyond the known guarantees of the underlying PIR protocols, and no deployment in a real multi-agent system under adversarial conditions. The knowledge base uses Prolog-style Horn clauses — a clean formalism, but real LLM agent memory systems use vector databases with embedding-based retrieval, not symbolic logic. The gap between the demo and production agentic AI is substantial. The milestone question is where this gets interesting for practitioners. The real unlock would be PIR over vector-database retrieval at sub-100ms latency for knowledge bases exceeding 1M entries — that's when this architecture becomes practical for production LLM agents. Current IT-PIR protocols have communication costs that scale linearly (or worse) with database size, so the gap between this clean symbolic demo and a real RAG pipeline is not just engineering — it's a fundamental efficiency barrier. The paper doesn't quantify this gap or name a concrete performance target. The obvious experiment the authors didn't run: embedding-based retrieval through PIR over a real vector store, benchmarked against a standard RAG pipeline for latency and accuracy. The honest read is (a) — this is a different research group's expertise (cryptographic protocols applied to symbolic AI), and bridging to neural retrieval would require a different stack and likely a collaboration. The Prolog-based formalism is the authors' home ground, and they stayed on it.