# PrivInfer: Privacy-Preserving Inference for Black-box Large Language Model

Meng Tong  University of Science and Technology of China, China  Kejiang Chen
Email<EMAIL_ADDRESS>University of Science and Technology of China,
China  Yuang Qi  University of Science and Technology of China, China  Jie
Zhang  Nanyang Technological University, Singapore  Weiming Zhang  University
of Science and Technology of China, China  Nenghai Yu  University of Science
and Technology of China, China

###### Abstract

Large language models (LLMs), such as ChatGPT, have simplified text generation
tasks, yet their inherent privacy risks are increasingly garnering attention.
Existing solutions for privacy-preserving inference face significant
challenges in practical deployment and implementation. In this paper, we
propose PrivInfer, the first practical framework for privacy-preserving
inference. It comprises two modules specifically designed for black-box LLMs
in text generation. The perturbation module, employing differential privacy,
generates perturbed prompts, thus enabling privacy-preserving inference with
black-box LLMs. The restoration module extracts coherent and meaningful
responses from obtained perturbed results, thus ensuring the accomplishment of
the text generation tasks. Additionally, to enhance privacy and utility
further, we develop RANTEXT, a novel differential privacy mechanism integrated
into the perturbation module of PrivInfer. This mechanism is specifically
tailored for LLMs and utilizes random adjacency in text perturbations.
Experimental results indicate that PrivInfer is comparable to GPT-4 in text
generation quality, and RANTEXT outperforms the current leading scheme in
privacy protection, even under its adaptive attack, our proposed GPT inference
attack.

##  1 Introduction

The rapid advancement of large language models has recently garnered
widespread attention from the global academic and industrial communities.
Among them, ChatGPT, one of the representative large language models, has
attracted over 100 million monthly active users within just two months of its
launch, making it one of the fastest-growing consumer applications in history
[1]. The introduction of ChatGPT has significantly facilitated people’s daily
work and life. Through ChatGPT, users can send data and instructions to remote
servers, thereby completing various daily work and writing tasks more
efficiently, from drafting upcoming academic papers and documenting work to
preparing information for products slated for market launch.

Figure 1: Overview of PrivInfer. It consists of a perturbation module and a
restoration module.

Method | Text Generation | Black Box | Inference | Low Cost
---|---|---|---|---
SANTEXT+ [2] |  | ✓ |  | ✓
CUSTEXT+ [3] |  | ✓ |  | ✓
CipherGPT [4] | ✓ |  | ✓ |
TextObfuscator [5] |  |  | ✓ | ✓
DP-Forward [6] |  |  | ✓ | ✓
PrivInfer+RANTEXT | ✓ | ✓ | ✓ | ✓

Table 1: Qualitative comparison among different methods in terms of their
support for specific features. A check mark indicates that a feature is
supported.

However, with widespread application and increasing popularity, a substantial
amount of user privacy information has been unwittingly leaked during usage,
leading to irreversible damage to individuals, teams, and even companies. For
instance, an employee of Samsung inadvertently leaked the company’s meeting
records and critical data of unreleased products while using a large language
model [7]; previously, the Italian government also confirmed instances of user
privacy infringement by ChatGPT, making Italy the first country to ban the use
of ChatGPT [8].

In the field of natural language processing (NLP), existing work [9, 10, 11]
has investigated the privacy issues of language models. As shown in Table 1,
Yue et al. [2] and Chen et al. [3] leveraged differential privacy techniques
[12] to sequentially replace tokens in the text with semantically similar
tokens from a fixed word adjacency list. These approaches are used for the
privacy-preserving training of models. However, these methods are not suitable
for the model inference process of text generation tasks due to the inherent
bias introduced by text perturbation. Moreover, these approaches are
constrained by fixed features of their word adjacency, and our experimental
results show that even with their privacy parameter $\epsilon$ set to 1.0,
privacy adversaries can still recover over one-third of the original text. Hao
et al.[13] and Chen et al. [14] applied homomorphic encryption techniques to
transformer architecture models for encrypted data inference. Theoretically,
they can be used for privacy-preserving text generation tasks. However,
homomorphic encryption incurs significant time and communication overheads, as
stated by Hou et al. [4]: they were the first to implement homomorphic
encryption inference on GPT-2 architecture, but inferring a single token
requires 24 minutes and 93 GB of bandwidth, rendering existing schemes
impractical. Zhou et al. [5] and Du et al. [6] attempted to split a complete
model inference process into local and remote steps, adding noise during data
transmission for perturbation. Notably, these methods are not primarily
designed for text generation tasks. It is important to note that previous work
[15, 16, 17] has shown that privacy adversaries can recover the original text
from their perturbed data. Additionally, due to the protection of intellectual
property and commercial value, closed-source model owners such as OpenAI [18]
and Claude [19] do not disclose information regarding their model
architectures, rendering these methods unsuitable for the black-box scenario.

To tackle the privacy protection challenges associated with text generation
tasks in black-box scenarios, we introduce PrivInfer. Inspired by the property
of article writing, which states that texts on correlated topics share common
phrases, it consists of a perturbation module and a restoration module. The
key part for protecting the privacy of PrivInfer is the perturbation module
based on differential privacy.

In the perturbation module, we perturb the raw prompt words using a
differential privacy algorithm, establishing multiple perturbed prompts to
achieve privacy protection. We then submit the perturbed prompts to the remote
large language model for inference, obtaining multiple perturbed generated
text results; eventually, in the restoration module, the text generation
result corresponding to the raw prompt is inferred by feeding numerous
perturbed generated text results to a local language model.

To enhance the privacy of the perturbation module in PrivInfer, we design
RANTEXT, a novel differential privacy mechanism based on random adjacency
tailored for large language models. RANTEXT, abiding by differential privacy
under the exponential mechanism, redefines word adjacency for each word during
each invocation through the Laplace differential privacy mechanism, thereby
altering the raw prompt on the token vocabulary of the large language model.
While preserving the utility of text generation results, RANTEXT outperforms
the current leading schemes, CUSTEXT+ [3] and SANTEXT+ [2], regarding security
and privacy protection.

We conducted extensive experiments on datasets for open-ended text generation
tasks to validate the utility and security of our scheme. Since the previous
attack strategies for differential privacy did not work well for RANTEXT, we
propose a novel differential privacy attack method—the GPT inference attack to
conduct in-depth testing on RANTEXT. The experimental results indicate that
the GPT inference attack exhibits a higher success rate than the mask token
inference attack[2]. Although the GPT inference attack worked, RANTEXT still
maintains the highest privacy protection capability compared to the baseline.

Our primary contributions can be summarized as follows:

  * $\bullet$

We propose PrivInfer, the first practical privacy protection framework for LLM
text generation tasks in black-box scenarios. PrivInfer employs differential
privacy methods to generate perturbed prompts for remote LLMs inference and
extracts the meaningful response from the remote perturbed results. This
scheme offers a new perspective for privacy research in black-box scenarios of
LLM text generation tasks.

  * $\bullet$

We introduce RANTEXT, a novel differential privacy mechanism within the
perturbation module of PrivInfer, specifically designed for LLM text
generation tasks. It is based on random adjacency. Adhering to differential
privacy standards under the exponential mechanism and employing the Laplace
differential privacy mechanism, RANTEXT dynamically ascertains random
adjacency for tokens within the LLM token vocabulary and substitutes them
accordingly. Through this approach, RANTEXT obfuscates the original semantic
information while ensuring the utility of the generated text, courtesy of the
vector proximity between pre- and post-replacement tokens in the LLM
tokenization vocabulary.

  * $\bullet$

We design the GPT inference attack, a novel attack method against text
differential privacy techniques. Experimental validation shows that the
success rate of the GPT inference attack surpasses that of the existing mask
token inference attack, offering a new evaluation angle for the security of
text differential privacy techniques.

  * $\bullet$

We perform a series of experiments, including testing the utility of our
solutions on three datasets of open-ended text generation tasks and validating
their privacy in three different attack experiments. The results show that the
PrivInfer scheme provides privacy protection while offering a text generation
quality comparable to GPT-4’s original. The text quality generated by RANTEXT
is comparable to the best baseline solution, yet its privacy protection level
significantly outperforms existing baseline solutions. Specifically, when
$\epsilon=10.0$ and $\text{top}_{K}=250$ are set for the embedding inversion
attack, RANTEXT offers a privacy protection rate exceeding 90%. This
performance is 19.89 times and 1.76 times superior to existing baseline
solutions CUSTEXT+ and SANTEXT+, respectively.

##  2 Preliminaries

In the following section, we introduce the foundational concepts vital to
comprehending the content of this manuscript. For ease of reference, Table 2
lists the frequently used notations in this paper.

Notation |  Description
---|---
$U$ |  User
$S$ |  Server of LLM
$D$ |  Raw Document
${D}^{\prime}$ |  Perturbed Document of $D$
${D_{j}}^{\prime}$ |  $j_{th}$ Perturbed Document of $D$
$G$ |  Text Generation of LLM
$G^{\prime}$ |  Perturbed Text Generation of LLM
${G_{j}}^{\prime}$ |  $j_{th}$ Perturbed Text Generation of LLM
$I$ |  Instruction for Writing
$I^{\prime}$ |  Instruction for Text Restoration
$V$ |  Token Vocabulary of LLM
$M$ |  Random Mechanism of Differential Privacy
$u$ |  Scoring Function of Differential Privacy
$C_{W}$ |  Adjacency of Token(or Word)
$C_{E}$ |  Adjacent Embeddings
Infer |  Inference Function of remote LLM
Table 2: Glossary of Frequent Notations Used in the Paper.

###  2.1 Inference Service

Assume that a user $U$ aims to invoke the inference function
$\text{\emph{Infer}}:P\rightarrow G$ of a remote large language model $S$ to
fulfill their text generation requirements, where $G$ denotes the text
generated by $S$. Here, $P=I\parallel D$ represents the user-provided prompt.
The term $I$ stands for the fundamental writing instruction, while document
$D=\langle x_{i}\rangle_{i=1}^{L}$ is composed of a sequence of $L$ tokens
$x_{i}$, each belonging to the vocabulary $V$ of size $|V|$. In this scenario,
we treat $S$ as a commercial black-box model. To preserve its commercial
value, $S$ does not publicly disclose its internal architecture or parameters
but only exposes its token vocabulary $V$ to $U$ for billing verification.

###  2.2 Objectives and Capabilities of Users

Objectives. User $U$ has dual aims: first, to accomplish text generation tasks
by invoking the inference function $\emph{Infer}:P\rightarrow G$ of $S$;
second, to ensure the confidentiality of their document $D$.
Capabilities. To fulfill these dual objectives, $U$ employs a randomized
mechanism of differential privacy $M:X\rightarrow Y$ to apply $N$
perturbations to each token $x_{i}\in V$ within the document. This results in
perturbed tokens ${y_{i,j}}=M(x_{i})$, ${y_{i,j}}\in V$, for
$j=1,2,3,\ldots,N$. Consequently, $U$ obtains multiple perturbed documents
${D_{j}}^{\prime}=\langle{y_{i,j}}\rangle_{i=1}^{L}$, where
$j=1,2,3,\ldots,N$. To perform text generation while preserving privacy, $U$
will invoke $S$’s inference function $\text{\emph{Infer}}:P\rightarrow G$ $N$
times, submitting a perturbed prompt
${P_{j}}^{\prime}=I\parallel{D_{j}}^{\prime}$ and receiving perturbed
generated text ${G_{j}}^{\prime}=\langle{g_{i}}^{\prime}\rangle_{i=1}^{K}=$
_Infer_ $({P_{j}}^{\prime}$) in each iteration, where $j=1,2,3,\ldots,N$.

###  2.3 Objectives and Capabilities of Server

Objectives. While $S$ is committed to executing text generation tasks
faithfully, it harbors curiosity about $U$’s original document $D$ and aspires
to glean as much information as possible from the perturbed documents
${D_{j}}^{\prime}$, where $j=1,2,3,...,N$.
Capabilities. $S$ employs privacy invasion techniques to attempt the
reconstruction of the original document $D$ from its perturbed versions
${D_{j}}^{\prime}$, where $j=1,2,3,...,N$.

###  2.4 Defining Differential Privacy

Before formally introducing our scheme, we briefly revisit key concepts,
including $\epsilon$-Differential Privacy ($\epsilon$-DP), Exponential
Mechanism (EM), and Laplace Mechanism (LM).

######  Definition 1 ($\epsilon$-differential privacy [12]).

In $\epsilon$-DP, given a privacy parameter $\epsilon\geq 0$, a randomized
mechanism $M$ is $\epsilon$-DP compliant if it satisfies the following
condition for all adjacent inputs $x,x^{\prime}\in X$ and every possible
output $y\in Y$:

$\frac{Pr[M(x)=y]}{Pr[M(x^{\prime})=y]}\leq e^{\epsilon}.$ (1)

From the mathematical definition of differential privacy, it is evident that a
smaller value of $\epsilon$ provides higher privacy protection, albeit at the
cost of reduced data utility. Interpreting the meaning conveyed by the
formula, $\epsilon$-DP implies that given an output result $y$, when
$\epsilon$ is sufficiently small, an adversary with unlimited capabilities is
unable to discern the probability distribution of two neighboring input sets
$x$.

It is important to note that differential privacy is a robust privacy
protection concept. It equally processes all input elements. Additionally, a
critical definition here is that of neighboring inputs. In previous NLP
research [20, 2, 3], most researchers have posited that any pair of inputs
sharing the same output set $Y$ are adjacent. We observe that such a
definition leads to a challenging trade-off between text utility and privacy.
In this paper, we will redefine the adjacency in differential privacy from the
perspective of probabilistic sampling in subsequent sections.

######  Definition 2 (exponential mechanism [21] ).

For a given scoring function $u:X\times Y\rightarrow\mathbb{R}$, a randomized
mechanism $M(X,u,Y)$ is $\epsilon$-DP compliant if it satisfies:

$Pr[y|x]\propto\exp\left(\frac{\epsilon\cdot u(x,y)}{2\Delta u}\right),$ (2)

where the sensitivity $\Delta u$ is defined as:

$\Delta u=\max_{x,x^{\prime}\in X,y\in Y}|u(x,y)-u(x^{\prime},y)|.$ (3)

Typically, we can scale the upper bound of $u$ to scale $\Delta u$ to a
specific real number. Due to the discrete nature of text, the exponential
mechanism (EM) is often employed in the NLP domain for implementing
differential privacy perturbations on text.

To ensure text utility, when employing the exponential mechanism for
differential privacy perturbations on text, it is essential to ensure that the
variations in the scoring function are consistent with the semantic similarity
between the input $x\in X$ and the output $y\in Y$. Specifically, we should
ensure that as the semantic closeness between the input $x\in X$ and the
output $y\in Y$ increases, the value of the corresponding scoring function
$u(x,y)$ also increases. This ensures that semantically similar elements are
sampled for output with a higher probability, thereby maintaining text utility
before and after the perturbation.

Similarly, the smaller the value of $\epsilon$ is, the higher the security of
privacy protection, but the lower the data utility. When a smaller $\epsilon$
is chosen, the scoring function $u(x,y)$ no longer plays a decisive role in
the output probability of any perturbation result. This ensures that when
$\epsilon$ is small, the probability of neighboring elements being selected
for output is very close, and an adversary with unlimited capabilities is
unable to determine the input $x\in X$ by observing the perturbed output $y\in
Y$.

######  Definition 3 (Laplace mechanism [22] ).

The Laplace mechanism (LM) is one of the foundational mechanisms for achieving
$\epsilon$-differential privacy ($\epsilon$-DP). For any function
$f:X\rightarrow\mathbb{R}^{d}$ and a given privacy parameter $\epsilon>0$, the
Laplace mechanism ensures $\epsilon$-DP by adding noise to the output of $f$.
Specifically, the noise follows a Laplace distribution centered at zero with a
scale parameter $\frac{\Delta f}{\epsilon}$, where $\Delta f$ is the
sensitivity of $f$, defined as the maximum change in $f$ across all adjacent
inputs $x,x^{\prime}\in X$:

$\Delta f=\max_{x,x^{\prime}\in X}\left(|f(x)-f(x^{\prime})|\right).$ (4)

The Laplace mechanism can be formally expressed as:

$M(x)=f(x)+\text{Lap}\left(\frac{\Delta f}{\epsilon}\right),$ (5)

where $\text{Lap}(\cdot)$ denotes the Laplace noise distribution function.

The Laplace mechanism provides a simple and effective method to protect the
privacy of sensitive continuous data while preserving data utility. In the
Laplace mechanism, the smaller the value of $\epsilon$ is, the higher the
level of privacy protection provided, albeit at the cost of reduced data
utility. Similar to the exponential mechanism and the definition of
$\epsilon$-DP, the Laplace mechanism also balances the relationship between
privacy protection and data utility by controlling the magnitude of the added
noise through $\epsilon$.

##  3 The PrivInfer Framework

###  3.1 Overview

In this section, we pioneer the introduction of the PrivInfer mechanism, a
framework meticulously crafted to safeguard privacy in text generation
endeavors undertaken by expansive language models within black-box scenarios.
The impetus behind PrivInfer is gleaned from a human compositional phenomenon
we discerned: semantically congruent paragraphs often materialize within texts
traversing multiple intertwined topics. Analogously, we ascertained within
language models that semantically akin input texts are predisposed to
manifesting similarity within the embedding space [23, 24, 25], thereby
engendering semantically consonant paragraphs in the resultant text. This
phenomenon provides the theoretical feasibility for PrivInfer. By harnessing
the prowess of differential privacy techniques, we effectuate multiple
perturbations upon the raw prompts, potentially laden with sensitive
information, and consecutively tender these perturbed prompts, thus securing
multiple perturbed text generation outcomes from the large language models. We
leverage a locally deployed language model to restore the normal text
generation result comparable to the raw prompt from these outputs. The
PrivInfer framework, depicted in Figure 1, is architectured around two
modules: the perturbation module and the restoration module.

Algorithm 1 Perturbation Module

1:function Perturb($D,u,\epsilon,N$)

2: Input: Document $D=\langle x_{i}\rangle_{i=1}^{L}$, scoring function $u$,
privacy parameter $\epsilon$, number of perturbed documents $N$

3: Output: Perturbed documents
$[D_{1}^{\prime},D_{2}^{\prime},\ldots,D_{N}^{\prime}]$

4: Initialize an empty list $Perturbed~{}Documents$

5: for $j=1$ to $N$ do

6: $D_{j}^{\prime}\leftarrow\emptyset$

7: for $i=1$ to $L$ do

8: Compute $C_{W}(x_{i})$

9: $\text{denom}\leftarrow\sum_{x_{i}^{\prime}\in
C_{W}(x_{i})}\exp\left(\frac{\epsilon\cdot u(x_{i},x_{i}^{\prime})}{2\Delta
u}\right)$

10: for each $x_{i}^{\prime\prime}\in C_{W}(x_{i})$ do

11: $p(x_{i}^{\prime\prime}|x_{i})\leftarrow\exp\left(\frac{\epsilon\cdot
u(x_{i},x_{i}^{\prime\prime})}{2\Delta u}\right)/\text{denom}$

12: Sample $x_{i}^{\prime}\sim p(x_{i}^{\prime\prime}|x_{i})$

13: Append $x_{i}^{\prime}$ to $D_{j}^{\prime}$

14: Append $D_{j}^{\prime}$ to $Perturbed~{}Documents$

15: return $Perturbed~{}Documents$

###  3.2 Perturbation Module

Before delineating the perturbation module inherent in our scheme, we present
Definition 4 and Assumption 1. We aim to provide a quantitative exposition of
the observed phenomenon.

######  Definition 4 ($\epsilon$-document privacy).

For a given privacy parameter $\epsilon>0$, scoring function $u(\cdot)$, token
vocabulary $V$, raw document $D=\langle x_{i}\rangle_{i=1}^{L}$ and perturbed
document ${D_{1}}^{\prime}=\langle x_{j}^{\prime}\rangle_{j=1}^{L}$,
${D_{2}}^{\prime}=\langle x_{k}^{\prime}\rangle_{k=1}^{L}$, where $x_{i}\in V$
and $x_{j}^{\prime},x_{k}^{\prime}\in V$, the randomized mechanism $M(\cdot)$
is $\epsilon$-document privacy if it meets the following conditions:

$d(x_{i},x_{j}^{\prime})\geq d(x_{i},x_{k}^{\prime})\Rightarrow
u(x_{i},x_{j}^{\prime})\leq u(x_{i},x_{k}^{\prime}),$ (6) $\forall
x^{\prime}\in\\{{x_{j}}^{\prime},{x_{k}}^{\prime}\\},\quad
Pr[x^{\prime}|x]\propto\exp\left(\frac{\epsilon\cdot u(x,x^{\prime})}{2\Delta
u}\right),$ (7)

where $i,j=1,2,3,\ldots,L$, $Pr[\cdot]$ denotes the probability output of the
randomized mechanism $M(\cdot)$, and $d(\cdot)$ is a function used to measure
the semantic similarity between two tokens (the smaller the output of
$d(\cdot)$ is, the more semantically similar the two words).

Definition 1 endeavors to quantitatively delineate the association between
differential privacy and the semantic alteration of documents, thereby aiding
our explication of Assumption 1. As the privacy parameter $\epsilon$ adopts
lower values, a probabilistic sampling standpoint assures the semantic
divergence between texts before and after perturbation, consequently
augmenting privacy safeguards, albeit compromising document utility.

Within PrivInfer, the perturbation module receives document
$D=\langle{x_{i}}\rangle_{i=1}^{L}$ from the raw prompt $P$ as input. Given a
privacy parameter $\epsilon>0$, predicated on the scoring function $u(\cdot)$
and randomized mechanism $M(\cdot)$ within the EM framework, the perturbation
module iteratively perturbs and substitutes each word $x_{i}$ in document
$D=\langle{x_{i}}\rangle_{i=1}^{L}$, where $C_{W}(x_{i})$ is the word
adjacency of word $x_{i}$. The result is $N$ perturbed documents
${D_{j}}^{\prime}=\langle{x_{i}}^{\prime}\rangle_{i=1}^{L}$, with
$j=1,2,3,\ldots N$. The algorithmic rendition of the perturbation module is
depicted in Algorithm 1.

In our paper, we have adopted three differential privacy algorithms that
comply with Definition 4: SANTEXT+, CUSTEXT+, and RANTEXT, which will be
delineated in Section 4.

###  3.3 Black-box Inference

In the inference stage, user $U$ recurrently invokes the inference function
_Infer_ $(\cdot)$ of the remote large language model $S$, each time uploading
a distinct perturbed prompt $P_{j}^{\prime}=I\parallel D_{j}^{\prime}$, where
$j=1,2,3,\dots N$. Via this mechanism, $U$ acquires the perturbed text
generation outcome
$G_{j}^{\prime}=\langle{g_{i,j}}^{\prime}\rangle_{i=1}^{K}=\emph{Infer}(P_{j}^{\prime})$
from inference on the perturbed prompt $P_{j}^{\prime}$. For a comprehensive
understanding of the prompt within the inference stage, please refer to
Appendix A.

###  3.4 Restoration Module

Our objective in the Restoration Module stage is to recuperate the original
text generation outcome $G=\langle g_{i}\rangle_{i=1}^{K}=\emph{Infer}(P)$
from the acquired $N$ perturbed text generation results
$G_{j}^{\prime}=\langle{g_{i,j}}^{\prime}\rangle_{i=1}^{K}=$ _Infer_
$(P_{j}^{\prime})$. The design of the Restoration Module is based on the
following phenomena we observed:

######  Assumption 1.

Consider a scoring function $u(\cdot)$, a randomized function $M(\cdot)$, a
writing instruction $I$, a vocabulary $V$, and an inference function
Infer($\cdot$) of a Large Language Model (LLM). Given a document $D$ perturbed
through $u(\cdot)$ and $M(\cdot)$, it yields $D^{\prime}$. If the randomized
mechanism $M(\cdot)$ satisfies $\epsilon$-document privacy, then there exists
a probability that $g_{i}\in G$ also satisfies $g_{i}\in G^{\prime}$, and
corr($\epsilon\;,\;|\\{g_{i}\mid g_{i}\in G^{\prime}\\}|$) > 0\. Here, "corr"
measures how two variables move together, ranging from -1 to 1;
$g_{i},g_{i}^{\prime}\in V$, $G=\langle
g_{i}\rangle_{i=1}^{K_{1}}=\text{{Infer}}(P)$, $G^{\prime}=\langle
g^{\prime}_{i}\rangle_{i=1}^{K_{2}}=\text{{Infer}}(P^{\prime})$, $P=I\|D$,
$P^{\prime}=I\|D^{\prime}$, and $\epsilon>0$.

Assumption 1 posits: should two documents $D$ and $D^{\prime}$ exhibit
similarity subsequent to differential privacy perturbation, and both proffer
identical writing instructions $I$, the ensuing text contents $G$ and
$G^{\prime}$ generated via the large language model inference function
_Infer_($\cdot$) ought to bear considerable similarity. Assumption 1 further
substantiates that the PrivInfer framework is capable of proficiently
executing text generation tasks while preserving privacy.

Algorithm 2 Restore Function

1:function restore($\hat{P}$)

2: Input: Prompt
$\hat{P}=I\|I^{\prime}\|D\|G_{1}^{\prime}\|G_{2}^{\prime}\|\ldots\|G_{N}^{\prime}$

3: Output: Generation text G corresponding to the raw prompt $P=I\|D$

4: Initialize an empty list $G$

5: for each $G_{j}^{\prime}$ in
$\\{G_{1}^{\prime},G_{2}^{\prime},\ldots,G_{N}^{\prime}\\}$ do

6: Extract segments from $G_{j}^{\prime}$ as directed by $I^{\prime}$

7: Append the extracted segments to $segments$

8: Stitch $segments$ together to form the text $G$ corresponding to the raw
prompt $P=I\|D$

9: Align $G$ with the central theme of $D$ as specified in $I^{\prime}$

10: return $G$

Based on Assumption 1, perturbed text generation outcomes contain elements
from the text generation corresponding to the raw prompt. In the restoration
module, we extract text from multiple perturbed text generation results and
reorganize them into the generated text corresponding to the raw prompt by
stitching the text segments and aligning them with the central theme.
Specifically, thanks to open-source language models [26, 27], we can
accomplish simple command interpretation and text generation tasks at a low
deployment cost. Our recovery module strategy involves deploying a lightweight
language model locally on U to perform the text extraction and stitching tasks
in $G_{j}^{\prime}$.

Explicitly, U invokes the $\text{restore}(\cdot)$ function to execute the
inference procedure on its locally deployed model. The input argument for the
inference of $\text{restore}(\cdot)$ function is denoted as prompt
$\hat{P}=I\|I^{\prime}\|D\|G_{1}^{\prime}\|G_{2}^{\prime}\|\ldots\|G_{N}^{\prime}$,
Where $I$ denotes the fundamental writing instruction, $I^{\prime}$
encompasses directives for text extraction, text stitching, and theme
alignment, $D$ refers to the raw document, and $G_{j}^{\prime}$ represents the
outcome of perturbed text generation. Finally, the local model of U will
complete the text generation task corresponding to the raw prompt $P=I\|D$
through text extraction, text stitching, and topic alignment according to the
instructions provided. The specific $restore(\cdot)$ algorithm is shown in
Algorithm 2. For detailed guidance on the prompt related to the restoration
module, see Appendix B.

PrivInfer uses the exponential mechanism in differential privacy to ensure
privacy-preserving text generation by black-box LLMs. It is widely applicable
and works with any differential privacy algorithm that supports
$\epsilon$-document privacy, as stated in Assumption 1. In Section 5, we
tested PrivInfer with three different privacy algorithms and found strong
support for Assumption 1.

In order to further enhance privacy protection in the perturbation module, we
designed RANTEXT, a novel differential privacy mechanism within the
perturbation module. RANTEXT is specifically designed for LLM, and it
comprises two main steps: Computing Random Adjacency and Sampling from
Adjacency. We are going to formally introduce it in the following Section 4.

Figure 2: The workflow of RANTEXT comprises two main steps: Computing Random
Adjacency and Sampling from Adjacency.

##  4 The RANTEXT Mechanism

###  4.1 Overview

In this section, we design a novel text differential privacy mechanism for
large language models, denominated RANTEXT, predicated on random adjacency.
Drawing inspiration from the Byte Pair Encoding (BPE) algorithm delineated in
Section 3.3, RANTEXT is crafted to engage with the model language composed of
tokens, as discerned by large language models. We have amended the word
adjacency design in preceding works, namely SANTEXT+ [2] and CUSTEXT+ [3], and
discerned that RANTEXT strikes a more favorable equilibrium between security
and utility. RANTEXT primarily encapsulates two segments: compute random
adjacency and sample from adjacency, as depicted in Figure 2.

###  4.2 Token Vocabulary

In order to better understand the idea of RANTEXT, we introduce the concepts
of tokenizer and token vocabulary [28].

In the black-box setting, $S$ undertakes the computation of the _Infer_
$(\cdot)$ function. To facilitate comprehension of the user input prompt $P$
by the large language model, the _Infer_ $(\cdot)$ function initially invokes
the corresponding model’s $tokenizer(\cdot)$ algorithm. This is necessary
because language models interact not directly with human language but with a
language formulated by token combinations from a specified token vocabulary
$V$, with diverse language models utilizing different $V$. For instance, GPT-4
[29] operates with the token vocabulary cl100k_base [28]. The
$tokenizer(\cdot)$ algorithm predominantly employs BPE [30] to partition the
input prompt into tokens that are intelligible to the LLM.

In the inference stage, the calculation of $tokenizer(\cdot)$ is executed by
$S$ in the black-box scenario. $S$ invokes the $tokenizer(\cdot)$ function,
procuring $T=\langle{t_{i}}\rangle_{i=1}^{Z}=BPE(P)$, where ${t_{i}}\in V$,
${P}=I\parallel{D}$, and $V$ constitutes the token vocabulary employed for
model training. After that, $T$ is input into the black-box LLM, eventually
returning the generated text $G=\langle{g_{i}}\rangle_{i=1}^{K}$ to $U$.
Nevertheless, in practical scenarios such as the service provided by GPT-4,
$S$ discloses its token vocabulary $V$ to $U$ for the purpose of billing
verification. This necessary disclosure consequently enables $C$ to
independently execute the $tokenizer(\cdot)$ calculation of LLM locally.

###  4.3 Workflow of RANTEXT

Before delving into the workflow of RANTEXT, we extend Assumption 1 by
introducing the following new assumption:

######  Assumption 2.

Given a scoring function $u(\cdot)$, a randomized function $M(\cdot)$, a
writing instruction $I$, and an inference function _Infer_ $(\cdot)$ trained
on a token vocabulary $V$ of a Large Language Model (LLM), consider a document
$\hat{D}=\langle t_{i}\rangle_{i=1}^{L}$. Perturbing $\hat{D}$ through
$u(\cdot)$ and $M(\cdot)$ yields
${D}^{\prime}=\langle{t_{i}}^{\prime}\rangle_{i=1}^{L}$, where
$t_{i},{t_{i}}^{\prime}\in V$. If the randomized mechanism $M(\cdot)$
satisfies $\epsilon$-document privacy, then there exists a probability that
for any $g_{i}\in G$, it also holds that $g_{i}\in G^{\prime}$, and
corr$(\epsilon\;,\;|\\{g_{i}\mid g_{i}\in G^{\prime}\\}|)>0$. Here, "corr"
measures the co-movement between two variables, ranging from -1 to 1;
$g_{i},g_{i}^{\prime}\in V$, $G=\langle
g_{i}\rangle_{i=1}^{K_{1}}=\text{Infer}(P)$,
$G^{\prime}=\langle{g_{i}}^{\prime}\rangle_{i=1}^{K_{2}}=\text{Infer}(P^{\prime})$,
$P=I\|\hat{D}$, $P^{\prime}=I\|{D}^{\prime}$, and $\epsilon>0$.

Algorithm 3 RANTEXT Mechanism

1:function RANTEXT($D,LLM,tokenizer,u,M$)

2: Input: Original document $D$, Large Language Model $LLM$, Tokenizer
$tokenizer$, Scoring function $u(\cdot)$, Random mechanism $M(\cdot)$

3: Output: Perturbed document $D^{\prime}$

4: $\hat{D}=\langle t_{i}\rangle_{i=1}^{L}=tokenizer(D)$ $\triangleright$
Tokenize the document

5: for $i=1$ to $K$ do

6: $C_{W}(t_{i})$ $\triangleright$ Compute adjacency for each token

7: for $i=1$ to $K$ do

8: $p_{i}=M(t_{i},u,C_{W}(t_{i}))$

9: Normalize $p_{i}$ such that $\sum p_{i}=1$

10: $t_{i}^{\prime}=\text{sample}(C_{W}(t_{i}),p_{i})$

11: $D^{\prime}=\langle{t_{i}}^{\prime}\rangle_{i=1}^{K}$ $\triangleright$
Construct the perturbed document

12: return $D^{\prime}$

Assumption 2 aims to illustrate that if two documents $D$ and $D^{\prime}$ are
semantically similar in the token vocabulary of the large language model, when
the writing instructions $I$ submitted by both are the same, the corresponding
text $G$ and $G^{\prime}$ generated by the large language model inference
function Infer($\cdot$) should also be broadly similar. In fact, the set of
words predicted by the large language model is determined by the token
vocabulary used during its training. That is, the language actually understood
and generated by the large language model is governed by its token vocabulary.

In RANTEXT, for a certain large language model $LLM$, let the corresponding
token vocabulary set be $V$. For the original document input by user
$D=\langle{x_{i}}\rangle_{i=1}^{L}$, RANTEXT uses the function
${tokenizer}:X\rightarrow V$ to transform the original document $D$ into a set
of tokens corresponding to $V$, $\hat{D}=\langle{t_{i}}\rangle_{i=1}^{K}$, and
subsequently computes the random adjacency $C_{W}(t_{i})$ corresponding to
every token ${t_{i}}$, where $i=1,2,3,...K$. Then, RANTEXT, based on its
differential privacy mechanism scoring function $u$($\cdot$) and randomized
mechanism $M$($\cdot$), perturbs token $t_{i}$ in $\hat{D}$ in sequence and
selects $t_{i}^{\prime}$ from its random adjacency $C_{W}(t_{i})$ to replace
$t_{i}$, thereby obtaining the perturbed document
$\hat{D}^{\prime}=\langle{t_{i}}^{\prime}\rangle_{i=1}^{K}$. The RANTEXT
algorithm is shown as Algorithm 3.

###  4.4 Computing Random Adjacency

To achieve a balance between utility and privacy for the perturbed document
$\hat{D}^{\prime}=\langle{t_{i}}^{\prime}\rangle_{i=1}^{K}$ derived from the
raw document $\hat{D}=\langle{t_{i}}\rangle_{i=1}^{K}$ through the exponential
mechanism of differential privacy perturbation in RANTEXT, the designed random
adjacency function $C_{W}$($\cdot$) primarily adheres to the following two
theorems:

######  Theorem 1.

Consider arbitrary tokens $t_{j},t_{k}\in V$ and any $t_{i}\in V$. For the
random adjacency mechanism $C_{W}(\cdot)$ employed by RANTEXT, the following
inequality should hold:

$d(t_{i},t_{j})\leq d(t_{i},t_{k})\implies\mathbb{E}[t_{j}\in
C_{W}(t_{i})]\geq\mathbb{E}[t_{k}\in C_{W}(t_{i})]$ (8)

Theorem 1 aims to illustrate that, in RANTEXT, the algorithm $C_{W}$($\cdot$)
should ensure from a probabilistic perspective that for any $t_{i}\in V$,
words semantically closer to it will appear in its token adjacency
$C_{W}(t_{i})$ with a higher expected probability, to ensure the utility of
the final perturbed text.

######  Theorem 2.

Considering an arbitrary token $t_{i}\in V$, under repeated applications of
the random adjacency mechanism $C_{W}(\cdot)$, the maximum possible
cardinality of the intersection set $|\\{\bigcap C_{W}(t_{i})_{j}\\}|$ must
satisfy the following condition:

$\max\left(|\\{\bigcap C_{W}(t_{i})_{j}\\}|\right)=|V|.$ (9)

Theorem 2 aims to illustrate that, for any $t_{i}\in V$, the random adjacency
function $C_{W}$($\cdot$) will not provide adversaries with additional
knowledge to narrow down the possible range of attacks on the raw text,
thereby ensuring the privacy of the raw document.

In fact, the definition of the random adjacency function $C_{W}$($\cdot$) in
RANTEXT satisfies the above two theorems to ensure both the utility and
privacy of the perturbed text. After introducing the complete definition of
random adjacency function $C_{W}$($\cdot$) later in this section, we will go
back and prove these two theorems.

Algorithm 4 Random Adjacent Embeddings

1:procedure Compute Random Adjacent
Embeddings($t_{i},\phi,\hat{\phi},d_{e},\varepsilon$)

2: Input: token $t_{i}$, embedding function $\phi$, perturbed embedding
function $\hat{\phi}$, distance function $d_{e}$, privacy parameters
$\varepsilon$

3: Output: set of random adjacent embeddings $C_{E}(t_{i})$

4: Initialize $C_{E}(t_{i})\leftarrow\emptyset$

5: Compute embedding $emb_{i}\leftarrow\phi(t_{i})$

6: Compute perturbed embedding $\hat{emb}_{i}\leftarrow\hat{\phi}(t_{i})$

7: $d_{\text{threshold}}\leftarrow d_{e}(\hat{emb}_{i},emb_{i})$

8: for each $emb\in\mathbb{R}^{N}$ do

9: if $d_{e}(emb,emb_{i})\leq d_{\text{threshold}}$ then

10: $C_{E}(t_{i})\leftarrow C_{E}(t_{i})\cup\\{emb\\}$

11: return $C_{E}(t_{i})$

Then, to introduce the random adjacency function $C_{W}$($\cdot$) in RANTEXT,
we propose the following new definition for better understanding of it:

######  Definition 5 (random adjacent embeddings).

For a given token $t_{i}\in V$, its random adjacent embeddings are obtained
through the function $C_{E}(\cdot)$ as follows:

$C_{E}(t_{i})=\left\\{\text{emb}\,|\,d_{e}\left(\text{emb},\phi(t_{i})\right)\leq
d_{e}\left(\hat{\phi}(t_{i}),\phi(t_{i})\right)\right\\}.$ (10)

where $emb\in\mathbb{R}^{N}$ represents an $N$-dimensional vector within the
real number domain. The function $d_{e}(\cdot)$ is utilized to compute the
distance between two vectors and is defined as
$d_{e}({a},{b})=\sqrt{\sum_{i=1}^{n}({a}_{i}-{b}_{i})^{2}}$. The function
$\phi:t_{i}\rightarrow\mathbb{R}^{N}$ maps any given token to a vector in the
$N$-dimensional real number vector space (Note: The set of tokens used by
$\phi(\cdot)$ should be consistent with _Infer_ $(\cdot)$). The function
$\hat{\phi}(t_{i})={\phi}(t_{i})+Y$, where $Y\sim L(0,\frac{\Delta
f}{\varepsilon})$, represents noise following the Laplace mechanism.

The algorithm for $C_{E}(\cdot)$ is outlined in Algorithm 4. For any $t_{i}\in
V$, its $C_{E}(t_{i})$ is determined by adding noise to the corresponding
vector in the $N$-dimensional real number vector space. The notion of
$C_{E}(t_{i})$ aims to obtain a randomized adjacent set for $t_{i}$ in the
vector space through a differential privacy algorithm adhering to the Laplace
mechanism.

To ensure the utility of random adjacency, it is also imperative to note that
the token vocabulary utilized by $\phi(\cdot)$ should align with _Infer_
$(\cdot)$. This is because, according to Section 4.2, the right training
tokens could theoretically make LLMs understand our perturbed prompts better.
We will derive the definition of random adjacency based on the random adjacent
embeddings.

######  Definition 6 (random adjacency).

For a given token $t_{i}\in V$, we define its random adjacency as the
following set obtained through the function $C_{W}(\cdot)$:

$C_{W}(t_{i})=\left\\{t_{i}^{\prime}|{\phi}({t_{i}}^{\prime})\in
C_{E}(t_{i})\right\\}.$ (11)

Our definition of random adjacency comes from random adjacent embeddings.
Specifically, the random adjacency set for any given token consists of tokens
whose embeddings are part of its random adjacent embeddings in the vector
space.

After introducing the definition of random adjacency in RANTEXT, we can give
proofs of Theorem 1 and Theorem 2. These theorems offer theoretical insights
into how RANTEXT effectively balances utility and privacy in the perturbation
of text:
Proof of Theorem 1. Given $t_{j},t_{k}\in V$ and any $t_{i}\in V$, we define
$d(t_{i},t_{j})=d_{e}(\phi(t_{i}),\phi(t_{j}))$ and
$d(t_{i},t_{k})=d_{e}(\phi(t_{i}),\phi(t_{k}))$. Assuming $d(t_{i},t_{j})\leq
d(t_{i},t_{k})$, we have:

$d_{e}(\phi(t_{i}),\phi(t_{k}))-d_{e}(\phi(t_{i}),\phi(t_{j}))\geq 0.$ (12)

For $\mathbb{E}[t_{j}\in C_{W}(t_{i})]$, we use Equation (11) and introduce
Laplace noise $Y\sim L(0,\frac{\Delta f}{\varepsilon})$ that is independently
distributed over an $N$-dimensional real vector space:

$\displaystyle f(Y_{i})=\frac{\epsilon}{2\Delta
f}\exp\left(-\frac{\epsilon|Y_{i}|}{\Delta f}\right).$ (13)

For $t_{k}$ and $\mathbb{E}[t_{k}\in C_{W}(t_{i})]$, we obtain:

$\displaystyle\mathbb{E}[$ $\displaystyle t_{k}\in
C_{W}(t_{i})]=\mathbb{E}[t_{k}\in\\{t_{i}^{\prime}|\phi(t_{i}^{\prime})\in
C_{E}(t_{i})\\}]$ (14) $\displaystyle=\int_{d_{e}(\phi(t_{k}),\phi(t_{i}))\leq
d_{e}(\hat{\phi}(t_{i}),\phi(t_{i}))}\prod_{i=1}^{N}f(Y_{i})\,dY_{1}\ldots
dY_{N}.$ (15)

Similarly, for $t_{j}$ and $\mathbb{E}[t_{j}\in C_{W}(t_{i})]$, we obtain:

$\displaystyle\mathbb{E}[t_{j}\in
C_{W}(t_{i})]={E}[t_{j}\in\left\\{t_{i}^{\prime}|{\phi}({t_{i}}^{\prime})\in
C_{E}(t_{i})\right\\}]$ (16)
$\displaystyle=\int_{\begin{subarray}{c}{d_{e}(\phi(t_{j}),\phi(t_{i}))}\leq{d_{e}(\hat{\phi}(t_{i}),\phi(t_{i}))}\end{subarray}}\prod_{i=1}^{N}f(Y_{i})\,dY_{1}\ldots
dY_{N}$ (17)
$\displaystyle=\int_{\begin{subarray}{c}{d_{e}(\phi(t_{k}),\phi(t_{i}))}\leq{d_{e}(\hat{\phi}(t_{i}),\phi(t_{i}))}\end{subarray}}\prod_{i=1}^{N}f(Y_{i})\,dY_{1}\ldots
dY_{N}$
$\displaystyle+\int_{{d_{e}(\phi(t_{j}),\phi(t_{i}))}\leq{d_{e}(\hat{\phi}(t_{i}),\phi(t_{i}))}\leq{d_{e}(\phi(t_{k}),\phi(t_{i}))}}\prod_{i=1}^{N}f(Y_{i})\,dY_{1}\ldots
dY_{N}.$ (18)

Since $f(Y_{i})>0$, when subtracting $\mathbb{E}[t_{k}\in C_{W}(t_{i})]$ from
$\mathbb{E}[t_{j}\in C_{W}(t_{i})]$, we find:

$\displaystyle\mathbb{E}[t_{j}\in C_{W}(t_{i})]-\mathbb{E}[t_{k}\in
C_{W}(t_{i})]$ $\displaystyle=\int_{d_{e}(\phi(t_{j}),\phi(t_{i}))\leq
d_{e}(\phi(t_{k}),\phi(t_{i}))}\prod_{i=1}^{N}f(Y_{i})\,dY_{1}\ldots
dY_{N}\geq 0.$ (19)

Thus, we have proven that the random adjacency mechanism $C_{W}(\cdot)$ in
RANTEXT satisfies Objective 1.
Proof of Theorem 2. In RANTEXT, the random adjacency mechanism $C_{W}(\cdot)$
probabilistically selects the adjacency for any given input $t_{i}$ by
utilizing Laplace differential privacy noise. Since the range of the Laplace
noise function $f(Y_{i})$ is $[0,\infty)$, this ensures that for any
$t_{i}^{\prime}\in V$, it is possible for $t_{i}^{\prime}\in C_{W}(t_{i})$ to
be satisfied. Thus, we have:

$\displaystyle\max\left(|\\{\bigcap C_{W}(t_{i})_{j}\\}|\right)=|V|.$ (20)

The application of the $C_{W}$($\cdot$) algorithm within RANTEXT does not
furnish adversaries with extra knowledge that would narrow the potential range
of attacks on the original text.

We ultimately demonstrate that the $C_{W}$($\cdot$) algorithm’s architecture
satisfies Objective 2.

###  4.5 Sampling from Random Adjacency

In RANTEXT, to guarantee the utility of the perturbed document, the scoring
function $u(\cdot)$ is required to conform to Equation (6):

$d(x_{i},x_{j}^{\prime})\geq d(x_{i},x_{k}^{\prime})\Rightarrow
u(x_{i},x_{j}^{\prime})\leq u(x_{i},x_{k}^{\prime}),$ (21)

Given the imperative to yield, for each $t_{i}\in V$, an adjacency
$C_{W}(t_{i})$ populated predominantly by semantically similar words, RANTEXT
employs a scoring function aligned with token semantic similarity.

The scoring function $u$($\cdot$) in RANTEXT is formulated as follows: For
$\phi(t_{i})=\hat{\phi}(t_{i})$, the function $u(t_{i},t_{i}^{\prime})$ is set
to 1. In the case where $\phi(t_{i})\neq\hat{\phi}(t_{i})$, the function takes
the form

$\displaystyle u(t_{i},t_{i}^{\prime})$
$\displaystyle=\frac{d_{E}(\phi(t_{i}),\hat{\phi}(t_{i}^{\prime}))-d_{E}(\phi(t_{i}^{\prime}),\phi(t_{i}))}{d_{E}(\phi(t_{i}),\hat{\phi}(t_{i}^{\prime}))}$
(22)
$\displaystyle=\frac{d_{E}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i}^{\prime}))}{d_{E}(\phi(t_{i}),\hat{\phi}(t_{i}^{\prime}))},$
(23)

where the ultimate functional values for $u$($\cdot$) are consequently given
by:

$u(t_{i},t_{i}^{\prime})=\\\
\begin{cases}\dfrac{d_{E}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i}))}{d_{E}(\phi(t_{i}),\hat{\phi}(t_{i}))}&\;\text{if
}\phi(t_{i})\neq\hat{\phi}(t_{i}),\\\\[8.61108pt] \quad\quad\quad 1&\;\text{if
}\phi(t_{i})=\hat{\phi}(t_{i}).\end{cases}$ (24)

The function $d_{E}(\cdot)$ is derived by normalizing the function
$d_{e}(\cdot)$, as demonstrated by equation

$d_{E}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i}))=\frac{d_{e}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i}))-\min(d_{e})}{\max(d_{e})-\min(d_{e})},$
(25)

where $\min(d_{e})$ and $\max(d_{e})$ are defined as

$\min(d_{e})=\min_{t_{i}^{\prime}\in
C_{W}(t_{i})}d_{e}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i})),$ (26)
$\max(d_{e})=\max_{t_{i}^{\prime}\in
C_{W}(t_{i})}d_{e}(\phi(t_{i}^{\prime}),\hat{\phi}(t_{i})).$ (27)

Given that $d_{E}(\cdot)\in[0,1]$, and in accordance with the definition of
$\Delta u$, we conclude that $\Delta u=1$.

Utilizing the scoring function $u(\cdot)$, and in reference to Equation (2),
for any given input $x\in X$ and output $y\in Y$, the stochastic mechanism
$M(\cdot)$ within RANTEXT adheres to the following probabilistic output
relationship:

$Pr[y|x]=\frac{\exp\left(\frac{\epsilon\cdot u(x,y)}{2\Delta
u}\right)}{\sum_{y\in Y}\exp\left(\frac{\epsilon\cdot u(x,y)}{2\Delta
u}\right)}.$ (28)

By capitalizing on RANTEXT’s specialized design for large language models and
the introduction of the pivotal concept of random adjacency, experiments in
Section 5 provide evidence that RANTEXT surpasses existing differential
privacy methods designed for black-box scenarios in both text utility and
privacy.

Moreover, RANTEXT fulfills the subsequent theorems, thereby validating that it
aligns with the foundational preconditions set forth in Assumption 2.
Theorem 3. For any privacy parameter $\epsilon\geq 0$, RANTEXT ensures
$\epsilon$-differential privacy.
Theorem 4. For any privacy parameter $\epsilon\geq 0$, RANTEXT guarantees
$\epsilon$-document privacy.
Proof of Theorem 3. Given inputs $x,x^{\prime}\in X$ and output $y\in Y$, and
utilizing the scoring function $u(\cdot)$ and randomization mechanism
$M(\cdot)$ in RANTEXT, we establish the following equation:

$\displaystyle\frac{\displaystyle\Pr[y|x]}{\displaystyle\Pr[y|x^{\prime}]}$
$\displaystyle=\frac{\displaystyle\frac{\displaystyle\exp\left(\frac{\epsilon\cdot
u(x,y)}{2\Delta u}\right)}{\displaystyle\sum_{y\in
Y}\exp\left(\frac{\epsilon\cdot u(x,y)}{2\Delta
u}\right)}}{\displaystyle\frac{\displaystyle\exp\left(\frac{\epsilon\cdot
u(x^{\prime},y)}{2\Delta u}\right)}{\displaystyle\sum_{y\in
Y}\exp\left(\frac{\epsilon\cdot u(x^{\prime},y)}{2\Delta u}\right)}}$ (29)
$\displaystyle=\frac{\displaystyle\exp\left(\frac{\epsilon\cdot
u(x,y)}{2\Delta u}\right)}{\displaystyle\exp\left(\frac{\epsilon\cdot
u(x^{\prime},y)}{2\Delta u}\right)}$ (30)

By substituting the value range of the scoring function $u(\cdot)$ and $\Delta
u$ in RANTEXT, we derive the following inequality:

$\frac{Pr[y|x]}{Pr[y|x^{\prime}]}\leq\exp\left(\frac{\epsilon\cdot
u(x,y)}{2}\right)\leq e^{\epsilon}.$ (31)

Proof of Theorem 4. From Theorem 1, we know that RANTEXT satisfies Equation
(7). In RANTEXT, we use $d_{E}(\cdot)$ to represent the function $d(\cdot)$.
Given $d_{E}(x_{i},x_{j}^{\prime})\geq d_{E}(x_{i},x_{k}^{\prime})$, we
substitute into RANTEXT’s computation for the function $u(\cdot)$, obtaining
$u(x_{i},x_{j}^{\prime})\leq u(x_{i},x_{k}^{\prime})$. Thus, we have completed
the proof of Theorem 4.

Dataset | Method | diversity$\uparrow$ | MAUVE$\uparrow$ | coherence$\uparrow$
---|---|---|---|---
$\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$ | $\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$ | $\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$
CNN/Daily Mail | GPT-4 | 0.983 | 0.671 | 0.632
Vicuna-7B | 0.945 | 0.648 | 0.669
PrivInfer+SANTEXT+ | 0.970 | 0.971 | 0.971 | 0.598 | 0.609 | 0.636 | 0.828 | 0.828 | 0.828
PrivInfer+CUSTEXT+ | 0.963 | 0.960 | 0.958 | 0.552 | 0.555 | 0.575 | 0.803 | 0.809 | 0.819
PrivInfer+RANTEXT | 0.971 | 0.970 | 0.971 | 0.566 | 0.597 | 0.659 | 0.828 | 0.828 | 0.828
Wikitext-103-v1 | GPT-4 | 0.987 | 0.453 | 0.650
Vicuna-7B | 0.965 | 0.142 | 0.880
PrivInfer+SANTEXT+ | 0.953 | 0.954 | 0.954 | 0.443 | 0.451 | 0.468 | 0.874 | 0.874 | 0.874
PrivInfer+CUSTEXT+ | 0.959 | 0.957 | 0.958 | 0.377 | 0.389 | 0.404 | 0.823 | 0.829 | 0.834
PrivInfer+RANTEXT | 0.954 | 0.954 | 0.955 | 0.389 | 0.458 | 0.467 | 0.874 | 0.874 | 0.874
ArXiv Dataset | GPT-4 | 0.935 | 0.736 | 0.726
Vicuna-7B | 0.928 | 0.400 | 0.833
PrivInfer+SANTEXT+ | 0.938 | 0.939 | 0.939 | 0.558 | 0.594 | 0.601 | 0.864 | 0.864 | 0.864
PrivInfer+CUSTEXT+ | 0.939 | 0.940 | 0.939 | 0.592 | 0.634 | 0.655 | 0.864 | 0.865 | 0.865
PrivInfer+RANTEXT | 0.939 | 0.939 | 0.939 | 0.612 | 0.633 | 0.641 | 0.864 | 0.864 | 0.864

Table 3: Performance comparison on open-ended text generation tasks across
different methods, datasets, and privacy settings ($\epsilon=1,2,3$),
evaluated based on diversity, MAUVE, and coherence.

Method | CNN/Daily Mail | Wikitext-103-v1 | ArXiv Dataset
---|---|---|---
$\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$ | $\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$ | $\epsilon=1$ | $\epsilon=2$ | $\epsilon=3$
SANTEXT+ | 223.24 | 213.31 | 201.50 | 225.93 | 217.59 | 205.61 | 255.19 | 242.90 | 227.95
CUSTEXT+ | 945.81 | 853.35 | 785.50 | 939.07 | 881.45 | 846.58 | 906.18 | 870.59 | 787.36
RANTEXT | 322.16 | 308.63 | 289.78 | 329.81 | 3313.79 | 299.26 | 359.29 | 343.15 | 319.66

Table 4: Edit distance scores across methods and datasets under varying
privacy settings ($\epsilon=1,2,3$).

##  5 Experiments

###  5.1 Experiment Setup

In our experiment, the utility and privacy of our proposals were assessed on
open-ended text generation tasks. Since there has been no prior privacy
protection solution designed for black-box LLMs in text generation tasks, we
are the first to propose a practical solution to this problem formally.
Consequently, we did not establish a baseline in the PrivInfer framework
experiment. Within the perturbation module, implementations were made for
SANTEXT+ [2], CUSTEXT+ [3], and our proposed RANTEXT scheme. In the inference
stage, GPT-4 [29] was selected as our remote black-box large language model
with its temperature parameter set to 0.5. For the Restoration Module,
Vicuna-7B [31] was chosen as our local language model, with its temperature
parameter set to 0 to mitigate Vicuna-7B’s inherent capabilities’ impact on
the experiment. The experiments adhered to the default recommended parameters
for SANTEXT+ and CUSTEXT+. For the function $\phi(\cdot)$ in the RANTEXT
scheme, the text-embedding-ada-002 [32] was selected, utilizing the same token
vocabulary as employed in GPT-4 training. They were trained using the
cl100k_base vocabulary, with RANTEXT deploying the initial 11,000 tokens of
cl100k_base to ensure the vector space computation within a 32 GB memory
space.

In the utility assessment, PrivInfer was employed on three disparate datasets
for open-ended text generation tasks, and the outcomes were juxtaposed with
those obtained from the GPT-4 model under a temperature parameter of 0.5.
Ablation experiments were conducted to elucidate the local model’s impact
further, solely utilizing the Vicuna-7B model set at a temperature of 0 for
text generation. As per the configurations in [33, 34, 35], we define the
document $D$ as the first 50 tokens of the articles, and then use GPT-4 [29]
to generate the next 100 tokens. The token count of the text was determined
using the GPT-2 tokenizer method as described in [36].

In the privacy assessment, assaults were initiated on the perturbed prompt
$P_{j}^{\prime}$ uploaded by user $U$, initially utilizing the mask token
inference attack as per the selections in [3, 2]. Given that the algorithm’s
transparency might furnish adversaries with additional insights, embedding
inversion attacks [37] were selected for adaptive assaults based on the token
adjacency information within the algorithm. Moreover, a scheme for assaulting
RANTEXT, termed the GPT inference attack, was proposed. Given the remote model
choice of GPT-4 and RANTEXT’s perturbations on GPT-4’s training token set
cl100k_base, theoretically, RANTEXT can facilitate an enhanced understanding
of perturbed prompts for GPT-4. Hence, the GPT inference attack endeavors to
exploit GPT-4’s superior text analysis and comprehension capabilities,
uploading the perturbed prompts to GPT-4 for autonomous analysis and
restoration of the original documents, thereby achieving the attack’s
objective. All assessments were orchestrated on a server furnished with two
Intel Xeon Gold 6130 2.10 GHz CPUs and one NVIDIA RTX A6000 graphics card.

###  5.2 Utility Evaluation

To validate the utility of our proposals, the schemes RANTEXT+, CUSTEXT+, and
RANTEXT were selected within our perturbation module, with privacy parameters
set to $\epsilon=1,2,3$. Open-ended text generation tasks were executed on
three distinct datasets harboring private information. These datasets are
elucidated as follows:

  * $\bullet$

CNN/Daily Mail [38] is a prevalent dataset of news articles, encompassing
approximately 300,000 unique pieces penned by journalists from CNN and Daily
Mail. It includes a vast array of real individuals and events.

  * $\bullet$

Wikitext-103-v1 [39] is a wiki dataset boasting over 100 million words and
260,000 unique tokens, meticulously extracted from authenticated, high-
quality, and featured Wikipedia articles. It includes numerous real names and
events.

  * $\bullet$

ArXiv Dataset [40] is a scientific corpus that aggregates a plethora of
academic papers and scholarly achievements. With several million research
papers, this dataset epitomizes researchers employing large language models to
draft unpublished, key-technology-centric research papers.

Aligning with [34], three metrics were employed to appraise the quality of the
generated text:
Diversity. This metric gauges the text’s diversity by computing the n-gram
repetition rates as follows:

$\text{DIV}=\sum_{n=2}^{4}\frac{\left|\text{unique
n-grams}(d_{cont})\right|}{\left|\text{total n-grams}(d_{cont})\right|}.$

A diminished diversity score suggests repetition affliction in the model,
whereas an augmented score denotes lexical diversity in the generated text.
MAUVE. [41] Employed to assess the resemblance between language model-
generated and human-authored text, a higher score is desirable in this metric.
Coherence. Adhering to the methodologies of coherence [42, 34], coherence was
approximated by computing the cosine similarity between sentence embeddings of
the prompt prefix $d_{pre}$ and the generated continuation $d_{cont}$:

$COH(d_{pre},d_{cont})=\frac{SimCSE(d_{pre})\cdot
SimCSE(d_{cont})}{\|SimCSE(d_{pre})\|\cdot\|SimCSE(d_{cont})\|},$

where $SimCSE(x)$ represents the pretrained SimCSE sentence embedding [43].

To elucidate the impact of various schemes in the perturbation module on
prompt perturbation, the Levenshtein distance [44] was harnessed to quantify
the disparity between the pre-and postperturbation prompts $p$ and
$p_{j}^{\prime}$. An escalated value in this metric implies diminished
similarity between the two strings. Table 3 delineates the principal outcomes
of our strategies juxtaposed with baseline methodologies in the text utility
experiments. Several pivotal observations emanate from these data:

(1) Relative to the text directly generated by GPT-4, PrivInfer sustains the
inherent text generation quality of GPT-4 while ensuring privacy. Our findings
accentuate that PrivInfer retains a text generation quality on par with GPT-4
across the datasets, thereby reinforcing the viability of the PrivInfer
approach.

(2) The text generated by PrivInfer demonstrates better quality compared to
the local model within the restoration module. In the CNN/Daily Mail and ArXiv
Datasets, PrivInfer outperforms the local Vicuna-7B model in terms of
diversity and coherence. Additionally, in the Wikitext-103-v1 and ArXiv
Datasets, PrivInfer scores higher than Vicuna-7B on the MAUVE metric,
indicating that the comparable text quality of PrivInfer with GPT-4 is not due
to the local model.

(3) Employing RANTEXT as the perturbation module demonstrates improved text
quality compared to CUSTEXT+ and comparable quality to SANTEXT+. Across
various metrics, RANTEX outperforms the CUSTEXT+ scheme in open-ended text
generation tasks across the three datasets and shows performance on par with
SANTEXT+. Moreover, Table 4 indicates that both RANTEX and SANTEXT+ have
smaller Levenshtein distances between the pre-and postperturbation prompts $p$
and ${p_{j}}^{\prime}$, which is notably lower than that of CUSTEXT+. This
analysis supports the observations made earlier.

###  5.3 Privacy Evaluation

In the CNN/Daily Mail dataset, we performed multiple adjustments to the
privacy parameter $\epsilon$, with values of 0.01, 2.0, 6.0, 10.0, 14.0, and
18.0. We employed three distinct text recovery methodologies to execute
privacy attacks. The success rate (ASR) of these attacks was computed, and
$1-\text{ASR}$ was utilized as the metric for assessing privacy protection
(Privacy).

Figure 3: Results of mask token inference attack.

Mask token inference attack [2]. As depicted in Figure 3, RANTEXT manifests
superior privacy protection capability under this attack compared to other
methods. The experimental outcomes suggest that, within an $\epsilon$ value
spectrum of 0.01-18.0, the RANTEXT scheme invariably furnishes over 90%
privacy safeguarding. This is primarily attributed to the construction-
oriented toward the GPT-4 token vocabulary in the RANTEXT scheme. It was
discerned that BERT faces difficulties in recognizing the text information
conveyed within the RANTEXT scheme, thereby proving challenging to decipher
and retrieve the original textual information encapsulated within RANTEXT.
Conversely, regarding the baseline schemes, it is evident that their privacy
safeguarding levels are subpar compared to RANTEXT. With $\epsilon$ values of
0.01, 2.0, and 6.0, CUSTEXT+ exhibits a marginally superior privacy protection
efficacy compared to SANTEXT+; however, with the escalation of $\epsilon$, its
privacy shielding capacity swiftly degrades. On the other hand, at $\epsilon$
values of 10.0, 14.0, or 18.0, the privacy-safeguarding efficacy of SANTEXT+
markedly surpasses that of CUSTEXT+.

Figure 4: Results of embedding inversion attack ($K=250$). Figure 5: Results
of embedding inversion attack ($K=500$).

Embedding inversion attack [37]. Propounded by Qu et al., this attack computes
the distance between the embedding of each token in the perturbed document and
the embeddings of other words in the vocabulary, returning the proximate top
$K$ tokens as the attack outcome. For the vocabulary, we deployed the word
vector compilations of the differential privacy algorithms inherent in each
scheme.

Experiments were conducted under the conditions of top $K=250$ and $500$.
Figures 4 and 5 illustrate that, under both conditions, SANTEXT+ and CUSTEXT+
are susceptible to embedding inversion attacks, indicating a relatively lower
level of privacy protection. Even at $\epsilon=0.01$, these methods could only
provide privacy protection for over 40% of the original documents. As the top
$K$ changes from $250$ to $500$, the privacy protection capability of SANTEXT+
and CUSTEXT+ remains largely unchanged. On the other hand, RANTEXT, benefiting
from its random token adjacency design, prevents attackers from utilizing
adjacency information for successful attacks, thus demonstrating a stronger
privacy protection capability under this attack.

Figure 6: Results of GPT inference attack.

GPT inference attack. Given that RANTEXT executes perturbations on the token
vocabulary of the GPT-4 model, it is hypothesized that the perturbed text
engendered through this perturbation technique should be more discernible to
GPT-4. Accordingly, we devised the GPT inference attack. Within this
methodology, the attacker capitalizes on GPT-4’s text comprehension property
by feeding the perturbed text into the GPT-4 model and instructs the model to
recuperate each token. The attack is considered successful if the recuperated
tokens coincide with the original tokens. For details on the prompt involved
in GPT inference attacks, see Appendix C.

Figure 6 shows the outcomes of the GPT inference attack: in contrast to BERT,
GPT-4 manifests a heightened attack success rate across all schemes. We
conjecture that this might stem from GPT-4’s more substantial model scale,
enhanced text generation, and understanding capacities, rendering it more
adept in decoding and recovering the perturbed text.

Confronted with the GPT inference attack, we discerned a pronounced downturn
in the privacy preservation levels of both SANTEXT+ and CUSTEXT+, trailing
RANTEXT. This accentuates RANTEXT’s tenacity in navigating intricate attack
landscapes. It is noteworthy that despite RANTEXT’s design for better synergy
with the GPT-4 model, it retains a high defensive fortitude against GPT-4.
Under the configuration of $\epsilon=18.0$, it continues to uphold a 90%
privacy preservation rate.

In summary, through the appraisal of diverse privacy attack techniques, it can
be inferred that RANTEXT exemplifies superior privacy protection prowess
across an array of assaults, while other methodologies, notably SANTEXT+ and
CUSTEXT+, exhibit relative vulnerability under certain assaults. These
experimental outcomes robustly validate that our advocated RANTEXT
methodology, while facilitating high-caliber text generation, also ascertains
the safeguarding of user privacy.

##  6 Discussion

Metric | N=1 | N=2 | N=3 | N=4 | N=5
---|---|---|---|---|---
diversity | 0.971 | 0.971 | 0.971 | 0.971 | 0.971
MAUVE | 0.659 | 0.658 | 0.660 | 0.659 | 0.658
coherence | 0.828 | 0.828 | 0.828 | 0.828 | 0.828
Table 5: Performance of RANTEXT with various $N$ values. Metric | $\epsilon=0.01$ | $\epsilon=2.0$ | $\epsilon=6.0$ | $\epsilon=10.0$ | $\epsilon=14.0$ | $\epsilon=18.0$
---|---|---|---|---|---|---
diversity | 0.971 | 0.971 | 0.971 | 0.971 | 0.971 | 0.971
MAUVE | 0.556 | 0.603 | 0.660 | 0.670 | 0.695 | 0.735
coherence | 0.828 | 0.828 | 0.828 | 0.828 | 0.828 | 0.828
Table 6: Performance of RANTEXT with various $\epsilon$ values.

This section elucidates the textual generation outcomes of both the PrivInfer
and RANTEXT schemes under varying configurations. Specifically, for PrivInfer,
we centered our attention on the potential ramifications of the quantity of
Perturbed Prompts ($N$) on the resultant text generation; in the RANTEXT
scheme, our focus was directed toward understanding the influence of different
privacy parameters ($\epsilon$) on the quality of the produced text.

As illustrated in Table 5, an increment in the number of Perturbed Prompts
from 1 to 5 did not manifest a notable alteration in PrivInfer across the
three metrics of diversity, MAUVE, and coherence. This might insinuate that
although PrivInfer stands as the pioneer privacy protection inference scheme
for large language models in black-box settings, achieving a degree of privacy
protection and enhancement in text quality, it might not have exploited all
the viable information within Perturbed Prompts fully. This indication also
propels the notion that a considerable volume of exploratory space and
research potential resides in this domain, evoking anticipation for more
profound explorations in ensuing studies.

Concerning the RANTEXT scheme, Table 6 shows that with a progressive
augmentation of the privacy parameter ($\epsilon$), there is a gradual ascent
in the MAUVE, while the diversity and coherence metrics maintain stability
across varying $\epsilon$ values. This observation resonates with our
anticipations. With the amplification of $\epsilon$, perturbed prompts
incrementally converge toward the raw prompt, naturally bolstering the
similarity between the perturbed generated text and the raw prompt phrases and
subsequently elevating the MAUVE.

##  7 Related Work

Feyisetan et al. [20] formally defined a differential privacy perturbation
algorithm for text. The authors achieved text privacy by directly adding noise
to the word vectors in a high-dimensional space defined by a word-embedding
model and then substituting the words with their nearest word. In their
implementation, they assumed that any two words in the vocabulary are
adjacent. Their categorization experiments demonstrated the practical utility
of their method, especially in training binary classifiers. However, their
approach does not theoretically guarantee that semantically similar words are
replaced with a higher probability; it only ensures that words that are
proximate in vector space are more likely to be selected.

Yue et al. [2] extended the framework originally proposed by Feyisetan et al.
They presented a version termed SANTEXT+. This method incorporates
differential privacy using the exponential mechanism. A notable characteristic
of SANTEXT+ is its approach to word substitution. Rather than replacements
with nearest words, SANTEXT+ gives priority to substituting semantically
similar words, aiming for higher probability during each operation. Consistent
with prior research, this approach has been evaluated on classification tasks.

Chen et al. [3] argued that the assumption that any two words are adjacent
limits the ability of the SANTEXT+ scheme to find a satisfactory trade-off
between privacy and utility. They proposed CUSTEXT+, which considers two words
in a fixed small set as adjacent. In CUSTEXT+, only the top K nearest words in
the word vector space are selected as adjacency. In their experiments, K was
set to a maximum of 50, ensuring greater semantic similarity in the replaced
words. Similar to previous works, the CUSTEXT+ scheme was also only evaluated
on classification tasks.

Other researchers have attempted to divide a complete model inference process
into local and remote parts, adding noise during data transmission. Du et al.
[6] perturbed the forward-pass embeddings of each sequence to achieve privacy.
Zhou et al. [5] also introduced random perturbations in functionally similar
representations, making it difficult for privacy attackers to distinguish
between them. Their methods also focused on classification tasks and needed
the model owners to disclose partial model architecture, which conflicted with
black-box settings. Additionally, works such as [14, 13, 4] have tried
applying homomorphic encryption on transformer-based [45] models to perform
encrypted inference, although the computational overhead remains a significant
challenge.

##  8 Conclusion

This study explores the challenge of privacy leakage in text generation tasks
executed by black-box large language models and introduces PrivInfer as a
proposed solution. Additionally, we propose RANTEXT, a differential privacy
algorithm designed for large language models following the exponential
mechanism to enhance user privacy protection. These methodologies aim to
contribute to user privacy protection while maintaining text generation
quality. Through multidisturbance prompt inference, PrivInfer strives for
privacy-protected text generation in black-box scenarios. On the other hand,
RANTEXT aims to improve privacy protection levels in text generation tasks by
introducing the concept of random token adjacency and devising a perturbation
scheme on the token set of large language models in compliance with
differential privacy.

Furthermore, we introduce a new privacy attack strategy named the GPT
inference attack, offering a tool for evaluating privacy protection schemes.
Experimental results show that, compared to the existing mask token inference
attack strategy, the GPT inference attack has a higher attack success rate,
supporting its use in evaluating privacy schemes.

In summary, this research aims to provide technical insights into the current
privacy challenges and sheds light on potential future explorations in privacy
protection within large language models. As the field of artificial
intelligence continues to develop, privacy protection is expected to emerge as
a key research topic, with a likely increase in the number of researchers
working collaboratively in this domain to further the advancement of privacy
protection technology.

## References

  * [1] Reuters Articles.  https://www.reuters.com/article/us-tech-openai-chatgpt-idUSKBN2A12SV.
  * [2] Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow.  Differential privacy for text analytics via natural text sanitization.  In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3853–3866, Online, August 2021. Association for Computational Linguistics.
  * [3] Sai Chen, Fengran Mo, Yanhao Wang, Cen Chen, Jian-Yun Nie, Chengyu Wang, and Jamie Cui.  A customized text sanitization mechanism with differential privacy.  In Findings of the Association for Computational Linguistics: ACL 2023, pages 5747–5758, 2023.
  * [4] Xiaoyang Hou, Jian Liu, Jingyu Li, Yuhan Li, Wen-jie Lu, Cheng Hong, and Kui Ren.  Ciphergpt: Secure two-party gpt inference.  Cryptology ePrint Archive, 2023.
  * [5] Xin Zhou, Yi Lu, Ruotian Ma, Tao Gui, Yuran Wang, Yong Ding, Yibo Zhang, Qi Zhang, and Xuan-Jing Huang.  Textobfuscator: Making pre-trained language model a privacy protector via obfuscating word representations.  In Findings of the Association for Computational Linguistics: ACL 2023, pages 5459–5473, 2023.
  * [6] Minxin Du, Xiang Yue, Sherman SM Chow, Tianhao Wang, Chenyu Huang, and Huan Sun.  Dp-forward: Fine-tuning and inference on language models with differential privacy in forward pass.  arXiv preprint arXiv:2309.06746, 2023.
  * [7] Samsung employees leak proprietary information via ChatGPT.  https://www.cshub.com/data/news/iotw-samsung-employees-allegedly-leak-proprietary-information-via-chatgpt.
  * [8] ChatGPT Is Banned in Italy Over Privacy Concerns.  https://www.nytimes.com/2023/03/31/technology/chatgpt-italy-ban.html.
  * [9] Lingjuan Lyu, Xuanli He, and Yitong Li.  Differentially private representation for nlp: Formal guarantee and an empirical study on privacy and fairness.  arXiv preprint arXiv:2010.01285, 2020.
  * [10] Richard Plant, Dimitra Gkatzia, and Valerio Giuffrida.  Cape: Context-aware private embeddings for private language learning.  arXiv preprint arXiv:2108.12318, 2021.
  * [11] Jiahui Hu, Zhibo Wang, Yongsheng Shen, Bohan Lin, Peng Sun, Xiaoyi Pang, Jian Liu, and Kui Ren.  Shield against gradient leakage attacks: Adaptive privacy-preserving federated learning.  IEEE/ACM Transactions on Networking, pages 1–16, 2023.
  * [12] Cynthia Dwork.  Differential privacy.  In International colloquium on automata, languages, and programming, pages 1–12. Springer, 2006.
  * [13] Meng Hao, Hongwei Li, Hanxiao Chen, Pengzhi Xing, Guowen Xu, and Tianwei Zhang.  Iron: Private inference on transformers.  Advances in Neural Information Processing Systems, 35:15718–15731, 2022.
  * [14] Tianyu Chen, Hangbo Bao, Shaohan Huang, Li Dong, Binxing Jiao, Daxin Jiang, Haoyi Zhou, Jianxin Li, and Furu Wei.  The-x: Privacy-preserving transformer inference with homomorphic encryption.  arXiv preprint arXiv:2206.00216, 2022.
  * [15] Xudong Pan, Mi Zhang, Shouling Ji, and Min Yang.  Privacy risks of general-purpose language models.  In 2020 IEEE Symposium on Security and Privacy (SP), pages 1314–1331. IEEE, 2020.
  * [16] Congzheng Song and Ananth Raghunathan.  Information leakage in embedding models.  In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 377–390, 2020.
  * [17] Hongsheng Hu, Zoran Salcic, Gillian Dobbie, Jinjun Chen, Lichao Sun, and Xuyun Zhang.  Membership inference via backdooring.  arXiv preprint arXiv:2206.04823, 2022.
  * [18] OpenAI.  https://www.openai.com/.
  * [19] Claude AI.  https://claude.ai/.
  * [20] Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe.  Privacy-and utility-preserving textual analysis via calibrated multivariate perturbations.  In Proceedings of the 13th international conference on web search and data mining, pages 178–186, 2020.
  * [21] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103, 2007.
  * [22] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [23] Hongwei Wang and Dong Yu.  Going beyond sentence embeddings: A token-level matching algorithm for calculating semantic textual similarity.  In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 563–570, 2023.
  * [24] Wataru Hirota, Yoshihiko Suhara, Behzad Golshan, and Wang-Chiew Tan.  Emu: Enhancing multilingual sentence embeddings with semantic specialization.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7935–7943, 2020.
  * [25] Katharina Hämmerl, Björn Deiseroth, Patrick Schramowski, Jindřich Libovickỳ, Constantin A Rothkopf, Alexander Fraser, and Kristian Kersting.  Speaking multiple languages affects the moral bias of language models.  arXiv preprint arXiv:2211.07733, 2022.
  * [26] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [27] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  arXiv preprint arXiv:2302.13971, 2023.
  * [28] Fast BPE tokeniser for use with OpenAI’s models.  https://github.com/openai/tiktoken.
  * [29] producing safer GPT-4 is OpenAI’s most advanced system and more useful responses.  https://openai.com/gpt-4.
  * [30] Rico Sennrich, Barry Haddow, and Alexandra Birch.  Neural machine translation of rare words with subword units.  arXiv preprint arXiv:1508.07909, 2015.
  * [31] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.  See https://vicuna. lmsys. org (accessed 14 April 2023), 2023.
  * [32] New and improved embedding model.  https://openai.com/blog/new-and-improved-embedding-model.
  * [33] Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston.  Neural text generation with unlikelihood training.  arXiv preprint arXiv:1908.04319, 2019.
  * [34] Xiang Lin, Simeng Han, and Shafiq Joty.  Straight to the gradient: Learning to use novel tokens for neural text generation.  In International Conference on Machine Learning, pages 6642–6653. PMLR, 2021.
  * [35] Jin Xu, Xiaojiang Liu, Jianhao Yan, Deng Cai, Huayang Li, and Jian Li.  Learning to break the loop: Analyzing and mitigating repetitions for neural text generation.  Advances in Neural Information Processing Systems, 35:3082–3095, 2022.
  * [36] Klemens Lagler, Michael Schindelegger, Johannes Böhm, Hana Krásná, and Tobias Nilsson.  Gpt2: Empirical slant delay model for radio space geodetic techniques.  Geophysical research letters, 40(6):1069–1073, 2013.
  * [37] Chen Qu, Weize Kong, Liu Yang, Mingyang Zhang, Michael Bendersky, and Marc Najork.  Natural language understanding with privacy-preserving bert.  In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1488–1497, 2021.
  * [38] Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom.  Teaching machines to read and comprehend.  Advances in neural information processing systems, 28, 2015.
  * [39] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models.  arXiv preprint arXiv:1609.07843, 2016.
  * [40] Colin B. Clement, Matthew Bierbaum, Kevin P. O’Keeffe, and Alexander A. Alemi.  On the use of arxiv as a dataset, 2019.
  * [41] Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui.  Mauve: Measuring the gap between neural text and human text using divergence frontiers.  Advances in Neural Information Processing Systems, 34:4816–4828, 2021.
  * [42] Yixuan Su, Tian Lan, Yan Wang, Dani Yogatama, Lingpeng Kong, and Nigel Collier.  A contrastive framework for neural text generation.  Advances in Neural Information Processing Systems, 35:21548–21561, 2022.
  * [43] Tianyu Gao, Xingcheng Yao, and Danqi Chen.  Simcse: Simple contrastive learning of sentence embeddings.  arXiv preprint arXiv:2104.08821, 2021.
  * [44] Li Yujian and Liu Bo.  A normalized levenshtein distance metric.  IEEE transactions on pattern analysis and machine intelligence, 29(6):1091–1095, 2007.
  * [45] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.

## Appendix

##  Appendix A Prompt for Black-box Inference

In the inference stage, user $U$ utilizes various unique perturbation cues
$P_{j}^{\prime}=I\parallel{D_{j}}^{\prime}$ on multiple occasions, by invoking
the inference function Infer($\cdot$) of the large language model $S$ to
attain the perturbed text generation outcomes
$G_{j}^{\prime}=\langle{g_{i,j}}^{\prime}\rangle_{i=1}^{K}$, where
${D_{j}}^{\prime}$ is the perturbed document, and $j=1,2,3,\dots N$. In the
experiment, the instruction $I$ is:

> Your task is to extend the "Prefix Text".
> \- Prefix Text:
>  [PREFIX TEXT HERE]

##  Appendix B Prompt for Restoration Module

In the restoration module, the local language model of ${U}$ executes the
restore($\cdot$) function; the input recovery prompt is denoted as
$\hat{P}=I\|I^{\prime}\|D\|G_{1}^{\prime}\|G_{2}^{\prime}\|\ldots\|G_{N}^{\prime}$,
where $I$ represents the basic writing instruction, $I^{\prime}$ denotes the
instruction for extracting text and stitching text, $D$ stands for the
original document, and $G_{j}^{\prime}$ represents the perturbed text
generation result. The instruction for $I^{\prime}$ is :

> Use the "Related Results" as your primary source material. Extract text from
> the ’Related Results’ carefully, and integrate them into your continuation,
> ensuring a seamless alignment with the context established by the "Prefix
> Text".
>

The complete prompt $\hat{P}$ is:

> Your task is to extend the "Prefix Text". Use the "Perturbed Results" as
> your primary source material. Extract text from the ’Perturbed Results’
> carefully, and integrate them into your continuation, ensuring a seamless
> alignment with the context established by the "Prefix Text".
> \- Prefix Text:
> [PREFIX TEXT HERE]
> \- Perturbed Results:
> [PERTURBED RESULTS HERE]

##  Appendix C Prompt for GPT inference attack

The GPT inference attack is a novel attack we propose against differential
privacy for text. Concurrently, this attack serves as the adaptive attack in
our RANTEXT scheme. Leveraging the superior text analysis and comprehension
capabilities of GPT-4, the GPT inference attack endeavors to recover the
original text information corresponding to the perturbed text through GPT-4
automatically. The prompt corresponding to the GPT inference attack is:

> Given a list of tokens, denoted as “INPUTS,” which have been subjected to
> text perturbation through differential privacy techniques, the task is to
> revert each token in the list to its most likely original token. For each
> perturbed token, provide the most likely original tokens from which it could
> have been transformed.
> As an example, consider the list “INPUTS”: ["Privacy", "LLM", "Text"]. The
> desired output format should be:
> [
> ["Prediction1"], # Corresponding to "Privacy"
> ["Prediction2"], # Corresponding to "LLM"
> ["Prediction3"] # Corresponding to "Text"
> ]
> Here, "Prediction" represents the most plausible original tokens prior to
> perturbation.
> For the given list of “INPUTS”:
> [INPUT HERE]
> Generate predictions for each token in the list, without exception. Ensure
> that exactly the most likely predictions are produced for each token.