Technical Summary: SharedRequest

Problem Statement

The widespread deployment of public Large Language Models (LLMs) like ChatGPT has created a critical tension between utility and user privacy. While cloud-based LLMs offer transformative capabilities, user prompts often contain sensitive information (e.g., personal attributes, medical history, legal details) that must remain confidential from third parties, including the service provider.

Existing privacy-preserving inference methods face a "trilemma" between privacy, utility, and efficiency:

1. Cryptographic approaches (SMPC): Methods like Iron, MPCFormer, and SecFormer offer strong privacy guarantees but introduce prohibitive communication and computation overhead, limiting scalability.
2. Local Differential Privacy (LDP): Approaches like RanText and CusText perturb prompts on the client side but often significantly degrade response quality (utility) and struggle with text generation tasks.
3. Model-specific modifications: Many solutions require access to model parameters or architectural changes, which is infeasible for proprietary black-box models.
4. Individual perturbation: Current model-agnostic methods typically perturb each prompt independently, leading to semantic distortion and high query costs when generating multiple noisy variants to ensure privacy.

Methodology: SharedRequest

The authors propose SharedRequest, a model-agnostic framework that reformulates privacy protection at the batch level rather than the individual-prompt level. The core insight is that commercial LLMs process massive batches of queries where many users share semantically equivalent generic instructions (e.g., "What are the recommended restaurants in [Location]?").

Core Mechanism

SharedRequest operates through a three-party protocol involving Users, a Noise Sampler (a third-party coordinator), and the Service Provider (LLM owner).

1. Prompt Decomposition:

   • User prompts are split into a generic instruction ($T_q$) and private attributes ($A_q$).
   • Users identify private attributes and sample a set of plausible alternative attributes ($A'$) from a pre-constructed database or local generation.

2. Batch-Level Grouping and Noise Injection:

   • The Noise Sampler receives encrypted private attributes from users. It groups prompts based on their generic instructions.
   • For each group, the sampler generates noisy variants by replacing the original private attributes with sampled alternatives.
   • Crucially, the sampler employs a combination filtering mechanism. Instead of sending all possible attribute combinations (which would be exponentially large), it uses a pre-trained discriminator to score the "genuineness" of attribute combinations within the context. Only combinations exceeding a quality threshold are selected. This ensures the noisy prompts are indistinguishable from genuine ones.

3. Secure Transmission:

   • Forward Transmission: Users encrypt private attributes using the Service Provider's public key. Messages to the Noise Sampler are encrypted with the Sampler's public key. This ensures the Sampler sees only generic instructions and candidate lists, while the Service Provider sees a shuffled mix of genuine and noisy prompts but cannot link them to specific users.
   • Backward Transmission: The Service Provider generates responses for the batch. To prevent the Noise Sampler from learning the content, the Service Provider masks responses using a pseudo-random mask derived from a seed provided by the user. Users reconstruct the true response via modular subtraction.

4. Cost Amortization:

   • The Service Provider aggregates identical prompts (both genuine and noisy) within a batch and generates a single response per unique prompt.
   • The inference cost of the "noisy" queries is amortized across the entire batch of users sharing the same generic instruction.

Privacy Definition

The paper introduces $(A_n, \epsilon)$-indistinguishability, a relaxation of standard Differential Privacy (DP).

• Neighbors: Two sets of prompts are considered neighbors if one can be obtained from the other by replacing the private attributes of a single prompt with a "qualified alternative" from a user-defined set.
• Guarantee: The mechanism ensures that the Service Provider's view (a shuffled set of prompts) is indistinguishable regarding changes in private attributes, provided the Noise Sampler and Service Provider do not collude.

Key Contributions

1. Novel Batch-Level Paradigm: A model-agnostic framework that groups semantically equivalent requests for joint processing, enabling privacy through shuffled noisy variants and cost reduction through batch-level amortization.
2. Lightweight Multi-Party Protocol: A design that preserves user anonymity and hides private attributes from the service provider without requiring modifications to the LLM architecture or access to model parameters.
3. Theoretical Formalization: Formalization of privacy via $(A_n, \epsilon)$-indistinguishability and theoretical analysis proving query-cost amortization benefits, particularly under uneven (long-tail) request distributions.
4. Third-Party Coordination: A mechanism for efficient noisy-query sampling that reduces user-side computation for prompts with multiple private attributes by offloading complex combination selection to the Noise Sampler.

Experimental Results

The framework was evaluated on three privacy-sensitive datasets: Legal-QA, Medical-QA, and MMLU-Biz.

• Utility:
  • The "Original" version (without prompt simplification) achieved utility nearly identical to the non-private baseline (within 1% loss).
  • Compared to state-of-the-art model-agnostic LDP baselines (RanText, CusText, DP-Prompt, InferDPT), SharedRequest achieved over 20% higher utility (measured by F1 score or quality ratings) at privacy budgets ($\epsilon$) ranging from 1 to 5.
• Query Cost:
  • The shared-prompt mechanism reduced query costs by up to 5.6× compared to non-batched inference, particularly when the distribution of generic instructions was concentrated (low entropy).
  • Cost reduction scales with batch size and the skewness of the request distribution.
• Robustness:
  • Against inference attacks where a server attempts to distinguish genuine prompts from noisy ones, SharedRequest reduced the attack success rate by approximately 32.7% compared to random sampling baselines.
  • The framework maintained comparable attack success rates (ASR) to other DP baselines while offering significantly higher utility.
• Efficiency:
  • The computational overhead for attribute filtering on the Noise Sampler was low (under 6.2 seconds per instruction group for a 1.5B parameter discriminator).
  • Communication overhead remained minimal (< 0.1 MB), comparable to standard DP methods and significantly lower than SMPC-based approaches.

Significance and Claims

The paper claims that SharedRequest addresses the fundamental limitations of current privacy-preserving LLM inference by breaking the trade-off between privacy, utility, and efficiency. By shifting the privacy paradigm from individual perturbation to batch-level mixing, the framework leverages the natural redundancy in large-scale LLM usage to amortize the cost of privacy protection.

The authors emphasize that this approach is model-agnostic, making it immediately applicable to proprietary black-box models without requiring service provider cooperation or architectural changes. The results suggest that for real-world scenarios with concentrated query distributions, SharedRequest offers a practical path to deploying privacy-preserving LLMs that maintain high utility while significantly reducing operational costs.

Limitations Acknowledged:

• The protocol assumes the Noise Sampler and Service Provider do not collude.
• Users are responsible for identifying private attributes and generating alternatives (though tools like NER or local LLMs can assist).
• The cost benefits are maximized when query distributions are uneven; highly unique queries may see less amortization.