Private Knowledge Retrieval and Private Reasoning for Secure Multi-Agent Systems
On Private Knowledge Retrieval and Private Inference for secure multi-agent systems
The authors propose using a signed knowledge base plus private information retrieval (PIR) to mitigate agent semantic memory poisoning; in the Python prototype, two-server IT-PIR uncached queries average 0.22s.
A malicious agent wants to poison another agent's semantic memory (external knowledge base); the paper assumes the knowledge base servers are untrusted but server collusion is not allowed; the defense goal is to make it so the attacker does not know what is stored in memory and finds it difficult to tamper with, with the knowledge base stored externally and logical reasoning performed locally by the agent.
- In multi-agent systems, a malicious agent can poison another agent's semantic memory (external knowledge base) to change its behavior; the authors argue that the existing AgentPoison-style attack formalization relies on three assumptions: the attacker knows the clean database, can write to it, and can observe the reasoning output.
- Proposes private knowledge retrieval and private inference: the knowledge base is stored externally, each piece of knowledge carries source metadata and is signed with SHA-256, Prolog-style reasoning is performed locally by the agent, and external access hides query contents using one of three protocols: two-server IT-PIR, k-anonymity, or bucketing.
- The Python prototype measures execution time on 99 Horn clauses, 46 indices, and 18 queries: non-cached baseline averages 0.17s, two-server IT-PIR 0.22s; the authors state that the overhead of the XOR implementation is comparable to lightweight schemes, and provide a communication bit overhead analysis of the four schemes.
- The authors point out that the system does not implement secure communication or a communication log, does not support parallel agents, and does not implement retrieval by arguments (JITI) or the tabling optimization; the experiments were conducted only on a single-machine prototype, and the paper reports no evaluation of defense effectiveness against real poisoning attacks.
- Benchmarks
- nreverse(SICStus Prolog 基准)zebra(SICStus Prolog 基准)
- Metrics
- 执行时间(Mean/St. dev./Min/Max)通信与计算开销(bits)
Targeting memory poisoning attacks in LLM multi-agent systems, the paper focuses on semantic memory and proposes private knowledge retrieval and private reasoning as defense solutions. The scheme introduces a signing mechanism in the knowledge base to prevent unintended tampering; agents locally run a Horn-clause-based Prolog-like reasoning system to access externally signed knowledge bases in a privacy-preserving manner. The authors implemented multiple privacy levels in Python, including k-anonymity and information-theoretic privacy (IT-PIR).
Paper analysis
What problem does this paper attempt to solve?
Defending against agent semantic memory poisoning: using a signed knowledge base plus private retrieval so the attacker does not know the contents of the store and finds tampering difficult.
Core problem: how to prevent a malicious agent in a multi-agent system from changing another agent's behavior by poisoning its semantic memory (knowledge base).
- Scenario and importance: the authors state that Agentic AI enables large numbers of LLM-based agents to collaborate, that interactions are long-term rather than one-off, and that a malicious agent can exploit vulnerabilities for long-term attacks; memory poisoning is one important class of such attacks.
- Shortcomings of the existing attack formalization: the authors argue that AgentPoison by Chen et al. [7] formalizes memory poisoning as an optimization problem (similar to data/model poisoning in federated learning), and that its assumptions—the attacker knows the clean database, can write key-value pairs, and can observe the output of the local agent's LLM—do not always hold, and security design can directly challenge these assumptions.
- Core observation: semantic memory is relatively static, infrequently updated knowledge, suitable for protection with cryptographic means; if the attacker cannot know Dclean, cannot tamper, and cannot compute the reasoning output E, the attack formalization (Equations 1–3) does not apply.
- The paper proposes: a private knowledge retrieval and private inference architecture: the knowledge base is stored externally and each entry is signed, Prolog-style reasoning is performed locally by the agent, and external access hides query contents via PIR; a Python prototype implementation is given.
- Threat model:
- Attacker goal: poison another agent's semantic memory so that it produces malicious behavior (e.g., deleting the home directory, buying the wrong flight ticket).
- Attacker knowledge: the AgentPoison model assumes knowledge of the clean database Dclean and of the local agent's reasoning output; this paper's defense is precisely to deprive the attacker of this knowledge.
- Attacker capability: inject adversarial key-value pairs into the external knowledge base; the paper assumes the knowledge base servers are untrusted but does not allow the servers to collude.
- Victim system: an agent containing a local Prolog-style reasoning mechanism and accessing an external knowledge base (applicable to both LLM agents and classical architectures such as BDI).
What related research exists?
Related work is divided into four groups: agent memory system classification, AgentPoison memory poisoning, PIR and coded storage, and FHE private inference.
Agent memory systems and architectures
- Chong et al. (2007), Kotseruba and Tsotsos (2020), Laird (2012), Wu et al. (2025)—surveys of cognitive architectures and memory mechanisms in the LLM era, with different classifications of memory systems; this paper distinguishes short-term, episodic, and semantic memory by duration and degree of consolidation.
- Wooldridge (2006)—classical multi-agent systems (including the BDI architecture); the discussion in this paper applies to both LLM agents and classical architectures.
Memory poisoning and prompt attacks
- Chen et al. (2024, NeurIPS)—AgentPoison, a red-team attack that injects adversarial key-value pairs into memory or knowledge bases and activates malicious behavior with triggers; this paper explicitly challenges its assumptions (the attacker knows the clean database, can write, and can observe the reasoning output) and proposes targeted mitigations.
- Das et al. (2025)—a survey of LLM security and privacy challenges, covering prompt injection and jailbreak; the authors point out that prompt attacks do not access memory and differ from memory poisoning.
Private information retrieval (PIR) and coded storage
- Chor et al. (1995, 1998)—proved that at least two non-communicating database replicas can achieve information-theoretic privacy (IT-PIR); the two-server scheme in this paper directly adopts this method.
- Kushilevitz and Ostrovsky (1997) and subsequent single-database computational-privacy PIR (surveys [24], [1])—single-server implementation becomes possible after relaxing to computational privacy.
- Freij-Hollanti et al. (2017), Holzbaur et al. (2022)—PIR on coded databases resistant to server collusion; Shah et al. (2014), Tajeddine et al. (2018)—PIR on MDS-coded distributed storage; Domingo-Ferrer et al. (2009)—P2P community-style user private retrieval. These are discussed in this paper as candidate schemes for multi-server extension and collusion resistance.
Private inference and data provenance
- Pindado et al. (2026)—a survey of private inference for deep networks based on fully homomorphic encryption (FHE); the authors state that such schemes are costly and only applicable to small networks, and that to their knowledge there is no private inference scheme in the literature for knowledge base reasoning.
- Chapman et al. (2024), Torra et al. (2017)—coarse/fine-grained data provenance structures, used to ensure the integrity of knowledge base updates.
Baselines and benchmarks: this paper has no defense baseline method for comparison; the experimental comparison is four access configurations within the same prototype (baseline without privacy protection, pir_bucket, pir_kAnon, itpir_2servers), and the knowledge base contains the SICStus Prolog benchmark predicates nreverse and zebra.
The authors position this paper as: rather than improving the attack, it invalidates the assumptions of the AgentPoison-style attack from a security design perspective, and provides a runnable private knowledge retrieval/inference prototype.
How does the paper address this problem?
The knowledge base is stored externally with signatures, reasoning is performed locally, queries are hidden via PIR, and the three retrieval protocols trade off between privacy and overhead.
Overall idea: make the semantic memory knowledge base external and digitally sign each entry, perform logical reasoning locally by the agent, and hide query contents for external knowledge access via private information retrieval (PIR), so that attackers neither know what is stored nor can easily tamper with it, thereby invalidating the premises of the AgentPoison-style attack formalization (Equations 1–3).
Rebuttal to the attack formalization
- The AgentPoison attack model is Dpoison(xt) = Dclean ∪ A(xt), i.e., the attacker injects adversarial key-value pairs into the clean database and optimizes two objectives: maximizing the probability of malicious actions under trigger queries and minimizing the impact on non-target queries.
- The authors point out that this model assumes Dclean is known, writable, and that the reasoning output E is observable; a defense only needs to keep E locally protected and use signatures to prevent unauthorized updates, and Equations 1–3 no longer apply.
Three mitigation strategies (Section 2.3)
- Secure memory mechanism: hash-based detection of modifications, signatures to guarantee provenance; when the knowledge base is external at a third party, signatures are likewise used to restrict malicious tampering; the reasoning mechanism E remains locally protected.
- Secure knowledge base updates: each piece of knowledge (Horn clause) carries source metadata, and together with the source information is signed by the source agent with a private key using SHA-256; the receiver verifies integrity with the public key before reasoning.
- Secure communication and logging: public-key encryption and signatures are suggested to protect communication; the authors explicitly state that this part is not implemented in the current prototype.
Local Prolog-style reasoning mechanism (Section 3.1)
- Implemented in Python; knowledge is represented as Horn clauses (facts and rules, recursion allowed); disjunction is not supported (the authors state it is logically equivalent to multiple pure Horn clauses), and the wildcard "_" and the cut operator are not supported.
- Lists are constructed with nil/cons; preprocessing translates standard list notation into constructor form.
- Standard Prolog resolution and the closed-world assumption (CWA) are adopted; unlike standard Prolog, by default all possible instantiations of a predicate within a given recursion depth are returned, and facts and rules are not required to be defined in a particular order.
Knowledge base client and server (Section 3.2–3.3)
- The client retrieves Horn clauses by (predicate name, arity); when there are no local clauses or the knowledge exceeds the TTL (time-to-live), the request is forwarded to the external server; retrieval results are cached, and the reason given by the authors is that recursive solving requires multiple accesses to the same fact, and repeated external accesses would leak query clues to intruders.
- The server is untrusted; all servers are initialized at system startup and loaded with all signed knowledge.
Three implementations of private knowledge retrieval (Section 3.4)
- Two-server IT-PIR (itpir_2servers): following the scheme of Chor et al., two non-communicating database replicas are used; the database is padded by index to equal length, the client constructs two random queries that differ only at the target index i, sends one to each server, and decodes the result by XORing the two XOR responses.
- Single-server k-anonymity: the target index plus k−1 random indices are submitted, the server returns all clauses for the k indices, and the client selects its own.
- Single-server buckets: at initialization the knowledge is divided into b buckets, retrieved as whole buckets and filtered locally; the authors point out that when b = npa/k the privacy guarantee is similar to k-anonymity, but bucketing is deterministic for repeated accesses to the same index.
- Notation: npa is the number of (predicate name, arity) pairs, nh is the number of Horn clauses, r is the number of bits per entry after padding.
Evaluation method
- There are no attack success rate metrics; the evaluation consists of complexity analysis (bits sent and received for each scheme, Table 1) and query execution time of the single-machine prototype (Tables 2–4).
What experiments did the paper conduct?
Single-machine prototype measured execution time for four knowledge base access configurations: two-server IT-PIR uncached average 0.22s, baseline 0.17s.
Experimental setup
- Subject under test: the paper's own Python prototype, including the local Prolog-style reasoning mechanism; no models such as LLMs were evaluated.
- Knowledge base: nh = 99 facts and rules, corresponding to npa = 46 (predicate name, arity) indices; includes non-recursive and recursive rules, as well as the SICStus Prolog benchmark predicates nreverse (recursion depth 496 at n = 30) and zebra.
- Queries: 18 queries, executed under four configurations.
- Configurations: baseline (single external knowledge base, no privacy protection), pir_bucket (buckets), pir_kAnon (k-anonymity, k = 4/6/8/10), itpir_2servers (two-server PIR).
- Cache settings: Non-cached (5 executions, each treated as a first external access, but caching is allowed within recursion and within the query set), Standard caching (executed twice, external access only on the first), All cached (5 executions, no external access).
- Environment: all components run on the same laptop, with servers and client as separate software implementations; the servers are assumed untrusted and not allowed to collude.
Main results
Mean execution time (seconds), according to Table 2 (Non-cached) and Table 4 (All cached):
Configuration Non-cached mean All cached mean baseline 0.17787843 0.0135 bucket 0.16892560 0.0149 Anon k4 0.17944365 0.0158 Anon k6 0.17852928 0.0140 Anon k8 0.18061575 0.0126 Anon k10 0.17887916 0.0144 it2pir 0.22309446 0.0129 - The authors call the two-server PIR results "surprisingly good": non-cached baseline 0.17s, it2pir 0.22s; they consider the XOR implementation on the knowledge base extremely fast, comparable to lightweight schemes that require generating multiple queries, forwarding, and filtering.
- The authors point out that execution time is independent of the logical reasoning engine: query processing is entirely handled by the knowledge base client and server, and the Prolog engine only fetches clauses from the local client.
- Under Standard caching (Table 3), the means for each configuration are baseline 0.0969, bucket 0.0919, Anon k4 0.1006, Anon k6 0.0976, Anon k8 0.0978, Anon k10 0.0987, it2pir 0.1192 seconds.
Complexity analysis
- Table 1 gives bit-level overhead: k-anonymity sends k·64 bits and receives k·r; b-bucketing sends 1·64 and receives m·r (m = npa/b); 2-PIR sends 2·npa, receives 2r and performs XOR; the extension with 2^d databases sends d·npa^(1/d) and receives dr.
- The authors explicitly write "Our solution is not optimal", pointing out that a scheme with 2^d databases exists that uses less communication.
Other ablations and analyses
- Cache impact: Non-cached (Table 2) means about 0.17–0.22s, Standard caching (Table 3) about 0.09–0.12s, All cached (Table 4) about 0.013–0.016s; the authors state that the non-cached case takes the longest "as expected".
- k parameter: as k goes from 4 to 10, the Anon means are close (0.1785–0.1806s in Table 2); the paper gives no further interpretation of the effect of k.
- Privacy-overhead trade-off (textual discussion): the authors state that the two-server scheme has the strongest privacy guarantee and in principle the greatest computation time, while k-anonymity and bucketing are lighter but offer weaker guarantees; when b = npa/k the two have similar privacy guarantees, but bucketing is deterministic for repeated accesses to the same index.
Negative results and exceptions
- The paper reports no experiments on defense effectiveness against real poisoning attacks (e.g., no data on reduction in attack success rate); the experiments are only execution time and complexity.
- The authors explicitly state that the current system does not implement the secure communication mechanism or the communication log, because the prototype does not support parallel agents and everything runs on a single machine (Section 2.3 (iii)).
What are some points that can be further explored?
The authors list future directions such as JITI retrieval, tabling, and multi-server extensions; the experiments cover only the execution time of the single-machine prototype.
Limitations and future directions noted by the authors
- Secure communication and communication log not implemented (Section 2.3 (iii)): the authors explicitly state that neither is implemented in the current system, but point out that this limitation has little impact in a single-machine prototype without parallel agents.
- Retrieval only by predicate name and arity (Section 3.2, Section 5): finer-grained retrieval by predicate arguments (e.g., SWI-Prolog's Just In Time Indexing) is possible, and the authors list it as a possible improvement.
- Tabling not implemented (Section 3.2, Section 5): i.e., memoization caching of predicate call results, listed by the authors as an optimization technique not adopted.
- Only a single or two replicated knowledge bases (Section 5): the authors state it can be extended to multiple specialized knowledge bases with different contents, each providing its own hash function, with the client first deciding which server to send the request to.
- The 2-PIR scheme is not optimal (Section 4.1): the authors explicitly write "Our solution is not optimal", pointing out that a scheme with 2^d databases sending d·npa^(1/d) bits exists that uses less.
- Collusion resistance and reliability extensions (Section 3.5): the authors discuss using error-correcting codes/MDS codes, locally repairable codes (LRC), and P2P PIR to cope with server collusion and data perturbation, as additional safeguards that can be added.
Scope of the experiments
- The experimental subject is the paper's own Python prototype, with all components running on one laptop and servers and client as separate software implementations (Section 4).
- The knowledge base size is nh = 99 Horn clauses and npa = 46 indices; the query set is 18 queries (Section 4.2).
- The evaluated configurations are baseline, pir_bucket, pir_kAnon (k=4/6/8/10), and itpir_2servers; the number of repetitions is 5 each for Non-cached and All cached, and 2 for Standard caching (Section 4.2).
- The evaluation metrics are only execution time and communication bit overhead; the paper reports no defense effectiveness against real memory poisoning attacks (e.g., changes in attack success rate).
- The paper reports no hardware configuration, no separate timing of signature verification, and no performance as the knowledge base size grows.
Summarize the main content of the paper
For agent semantic memory poisoning, proposes a defense architecture of a signed knowledge base plus PIR private retrieval and provides prototype overhead data.
A defense paper on semantic memory security in multi-agent systems, proposing a private knowledge retrieval and private reasoning architecture and providing a Python prototype.
- Problem: A malicious agent can inject adversarial content into another agent's external semantic memory (knowledge base) to change its behavior; the authors argue that the attack formalization of AgentPoison [7] relies on three assumptions—knowing the clean knowledge base, being able to write, and being able to observe reasoning outputs—and that security design can render them ineffective.
- Method highlights: The knowledge base is externalized, each Horn clause is attached with source metadata and digitally signed based on SHA-256; Prolog-style reasoning (pure Horn clauses, CWA, returning all instantiations) is performed locally by the agent; external access is indexed by (predicate name, arity), and queries are hidden through three protocols: two-server IT-PIR, k-anonymity, or bucketing.
- Result 1: The complexity analysis (Table 1) gives the bit overhead of each scheme; 2-PIR sends 2·npa and receives 2r; the authors explicitly state that this scheme is not optimal.
- Result 2: On 99 clauses, 46 indexes and 18 queries, uncached execution time averages 0.17s for baseline and 0.22s for two-server IT-PIR (Table 2); when fully cached, each configuration is about 0.013–0.016s (Table 4).
- Result 3: The authors state that the XOR implementation overhead of IT-PIR is comparable to lightweight schemes, and that execution time is independent of the reasoning engine.
- Authors' conclusion: The authors believe that the three strategies—secure memory mechanism, secure knowledge base updates, and secure communication—can mitigate the standard memory poisoning formalization; future directions include retrieval by parameters (JITI), tabling, extension to multiple specialized knowledge bases, and collusion-resistant encoding.
- Takeaway for readers: This is work at the architecture and prototype level; the paper does not report experiments on defense effectiveness against real poisoning attacks, and the evidence is limited to execution time and communication overhead.