of [K2, Proposition 7.4]. The inclusion $\overline{j}$ induces an isomorphism
in cohomology

$\overline{j}^{*}:H_{N}^{*}(\widehat{S})\to H_{N}^{*}(\widehat{S}\cap F)\,.$

Indeed, it is shown in the proof of [K2, Proposition 7.4] that for each
individual stratum, the inclusion induces an isomorphism

$\overline{j}_{\beta}^{*}:H^{*}_{N}(\widehat{S}_{\beta})\to
H^{*}_{N}(\widehat{S}_{\beta}\cap F)\,.$

Comparing the spectral sequence of the two stratifications of $\widehat{S}$
and $\widehat{S}\cap F$ (or equivalently by comparing the Gysin sequences
induced by adding the unstable strata one at a time), we conclude the same is
true about the map $\overline{j}^{*}.$

By the above discussion and [K2, Lemma 7.8], we see that

$\widehat{S}\cap F\to N\widehat{Z}_{R_{2}}$

is a $\mathbb{P}^{10}\sqcup\mathbb{P}^{7}$-fibration contained in the
$\mathbb{P}^{18}$-fibration $F\to N\widehat{Z}_{R_{2}}.$ To establish (33),
let

$\alpha\in H_{N}^{*}(\widehat{\Sigma}),\quad\alpha\in\text{Ker
}h^{*}\cap\text{Im }g^{*}\,.$

Then, from the third-term column of the diagram, we have

$\alpha=i_{!}(\gamma),\quad\gamma\in H^{*}_{N}(\widehat{S})\,.$

We compute

$j^{*}\alpha=j^{*}i_{!}(\gamma)=\overline{i}_{!}\overline{j}^{*}(\gamma)\,.$

The class $j^{*}\alpha$ must come from the base of the
$\mathbb{P}^{18}$-fibration $F\to N\widehat{Z}_{R_{2}},$ since $\alpha$ is in
the image of $g^{*}$. However, the argument in the paragraphs above shows that
classes $\overline{j}^{*}(\gamma)$ supported on the unstable part
$\widehat{S}\cap F$ do not come from the base, unless of course

$\overline{j}^{*}(\gamma)=0\,.$

Using that $\overline{j}^{*}$ is an isomorphism, we must have $\gamma=0$,
hence $\alpha=i_{!}(\gamma)=0$ as claimed by (33).

A similar analysis applies to $R_{3}=\text{diag
}\langle\lambda,\lambda^{-1},1\rangle$, so

$\widehat{Z}_{R_{3}}=\mathbb{P}\langle x^{3}y^{3},xyz^{4},z^{6}\rangle\,.$

The blowup is a $\mathbb{P}^{17}$-bundle over the base, and the representation
of $R_{3}$ is computed in [KL1, Section 5.4]. The unstable locus is similarly
a projective bundle over the base. An analogous argument applies in this case
as well.

## References

  * [A] V. Arena, On weighted blow-ups and their intersection theory, Mathematics Theses and Dissertations 2024, Brown Digital Repository, Brown University Library https://repository.library.brown.edu/studio/item/bdr:rwe96j9r/.
  * [AO] V. Arena, S. Obinna, The integral Chow ring of weighted blowups, preprint arXiv:2307.01459.
  * [BHPV] W. Barth, K. Hulek, C. Peters, A. Van de Ven, Compact Complex Surfaces, Ergeb. Math. Grenzgeb., Vol. 4, Springer-Verlag, Berlin, 2004.
  * [BLMM] N. Bergeron, Z. Li, J. Millson, C. Moeglin, The Noether-Lefschetz conjecture and generalizations, Invent. Math. 208 (2017), 501 - 552.
  * [BM] A. Borel, J. Moore, Homology theory for locally compact spaces, Michigan Math. J. 7 (1960), 137 - 159.
  * [B] J. Bruinier, On the rank of Picard groups of modular varieties attached to orthogonal groups, Compositio Math. (2002), 49 - 63.
  * [CK] S. Canning, B. Kong, The Chow rings of moduli spaces of elliptic surfaces over $\mathbb{P}^{1}$, Algebr. Geom. 10 (2023), 489 – 503.
  * [CL1] S. Canning, H. Larson, Chow rings of low-degree Hurwitz spaces, J. Reine Angew. Math. 789 (2022), 103 - 152.
  * [CL2] S. Canning, H. Larson, On the Chow and cohomology rings of moduli spaces of stable curves, preprint arXiv:2208.02357, to appear in J. Eur. Math. Soc.
  * [CLP] S.Canning, H. Larson, S. Payne, Extensions of tautological rings and motivic structures in the cohomology of $\overline{\mathcal{M}}_{g,n}$, preprint arXiv:2307.08830.
  * [COP1] S. Canning, D. Oprea, R. Pandharipande, Degree2K3, Github repository, available at https://github.com/ src2165/Degree2K3.
  * [COP2] S. Canning, D. Oprea, R. Pandharipande, Cycles on the moduli space of principally polarized abelian varieties, in preparation. Lecture available at https://people.math.ethz.ch/~rahul/AbelianBerlin.pdf.
  * [D] I. V. Dolgachev, Weighted Projective Varieties, Group Actions and Vector Fields (Vancouver, B.C., 1981), Lecture Notes in Math. 956, Springer-Verlag (1982), 34 - 71.
  * [EG] D. Edidin, W. Graham, Equivariant intersection theory, Invent. Math. 131 (1998), 595 - 634.
  * [Fa] C. Faber, A conjectural description of the tautological ring of the moduli space of curves, Moduli of curves and abelian varieties, Aspects Math., E33 (1999), 109 - 129.
  * [F] W. Fulton, Intersection theory, Springer-Verlag, Berlin, 1998.
  * [GK] G. van der Geer, T. Katsura, Note on tautological classes of moduli of $K3$ surfaces, Mosc. Math. J. 5 (2005), 775 - 779.
  * [GP] T. Graber, R. Pandharipande, Constructions of nontautological classes on the moduli spaces of curves, Michigan Math. J. 51 (2003), 93 - 109.
  * [GS] D. R. Grayson, M. E. Stillman, Macaulay2, a software system for research in algebraic geometry, available at http://www.math.uiuc.edu/Macaulay2/.
  * [GSSEC] D. R. Grayson, M. E. Stillman, S. A. Strømme, D. Eisenbud, C. Crissman, Schubert2: characteristic classes for varieties without equations, Version 0.7, Macaulay2 package available at http://www.math.uiuc.edu/Macaulay2/.
  * [GLT] F. Greer, Z. Li, Z. Tian, Picard groups on moduli of K3 surfaces with Mukai models, Int. Math. Res. Not. 16 (2015), 7238 - 7257.
  * [K1] F. Kirwan, Cohomology of quotients in symplectic and algebraic geometry, Mathematical Notes, Princeton University Press, Princeton, NJ, 1984.
  * [K2] F. Kirwan, Partial desingularizations of quotients of nonsingular varieties and their Betti numbers, Ann. of Math. 122 (1985), 41 - 85.
  * [K3] F. Kirwan, Rational intersection cohomology of quotient varieties, Invent. Math. 86 (1986), 471 - 505.
  * [KL1] F. Kirwan, R. Lee, The cohomology of moduli spaces of K3 surfaces of degree 2. I., Topology 28 (1989), 495 - 516.
  * [KL2] F. Kirwan, R. Lee, The cohomology of moduli spaces of K3 surfaces of degree 2. II., Proc. London Math. Soc. 58 (1989), 559 - 582.
  * [Ke] S. Keel, Intersection theory of moduli space of stable N-pointed curves of genus zero, Trans. Amer. Math. Soc. 330 (1992), 545 - 574.
  * [Kr] A. Kresch, Cycle groups for Artin stacks, Invent. Math. 138 (1999), 495 - 536.
  * [La] R. Laza, The KSBA compactification for the moduli space of degree two K3 pairs, J. Eur. Math. Soc. 18 (2016), 225 - 279.
  * [LOG] R. Laza, K. O’Grady, Birational geometry of the moduli space of quartic K3 surfaces, Compositio Math. 155 (2019), 1655 - 1710.
  * [Le] J. Lewis, A Survey of the Hodge Conjecture, CRM Monogr. Ser., 10 American Mathematical Society, Providence, RI, 1999.
  * [Lo] E. Looijenga, New compactifications of locally symmetric varieties, Proceedings of the 1984 Vancouver conference in algebraic geometry, CMS Conf. Proc., Amer. Math. Soc., 1986, 341 - 364.
  * [LFV] A. Di Lorenzo, R. Fringuelli, A. Vistoli, Integral Picard group of moduli of polarized K3 surfaces, preprint arXiv:2305.07574.
  * [MOP] A. Marian, D. Oprea, R. Pandharipande, Segre classes and Hilbert schemes of points, Ann. Sci. Éc. Norm. Supér. 50 (2017), 239 - 267.
  * [MP] D. Maulik, R. Pandharipande, Gromov-Witten theory and Noether-Lefschetz theory, in A celebration of algebraic geometry, 469 - 507, Clay Math. Proc., 18, Amer. Math. Soc., Providence, RI, 2013.
  * [Ma] A. Mayer, Families of K-3 Surfaces, Nagoya Math. J. 48 (1972), 1 - 17.
  * [M] R. Miranda, The moduli of Weierstrass fibrations over ${\bf P}^{1}$, Math. Ann. 255 (1981), 375 - 394.
  * [OG] K. O’Grady, On the Picard group of the moduli space for $K3$ surfaces, Duke Math J. 53 (1986), 117 - 124.
  * [P] R. Pandharipande, A calculus for the moduli space of curves, Algebraic geometry: Salt Lake City 2015, 459 - 487, Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, RI, 2018.
  * [PY] R. Pandharipande, Q. Yin, Relations in the tautological ring of the moduli space of K3 surfaces, J. Eur. Math. Soc. 22 (2020), 213 - 252.
  * [PS] C. Peters, J. Steenbrink, Mixed Hodge Structures, Ergeb. Math. Grenzgeb., Vol 52, Springer–Verlag, Berlin, 2008.
  * [Pe1] D. Petersen, A vanishing result for tautological classes on the moduli of K3 surfaces, Amer. J. Math. 141 (2019), 733 - 736.
  * [Pe2] D. Petersen, answer to https://mathoverflow.net/questions/142858/.
  * [S] J. Shah, A complete moduli space for K3 surfaces of degree 2, Ann. of Math. 112 (1980), 485 - 510.
  * [T] A. Thompson, Degenerations of K3 surfaces of degree two, Trans. Amer. Math. Soc. 366 (2014), 219 - 243.
  * [To] B. Totaro, Chow groups, Chow cohomology and linear varieties, Forum of Mathematics, Sigma 2 (2014), Paper No. e17.
  * [V] A. Vistoli, Intersection theory on algebraic stacks and on their moduli spaces, Invent. Math. 97 (1989), 613-670.
  * [Z] J. van Zelm, Nontautological bielliptic cycles, Pacific J. Math., (2018), 495 - 504.


# Watermarking Generative Tabular Data

Hengzhi He
<EMAIL_ADDRESS>&Peiyu Yu*
<EMAIL_ADDRESS>&Junpeng Ren
<EMAIL_ADDRESS>&Ying Nian Wu
<EMAIL_ADDRESS>&Guang Cheng
<EMAIL_ADDRESS>
Equal Contribution.

###### Abstract

In this paper, we introduce a simple yet effective tabular data watermarking
mechanism with statistical guarantees. We show theoretically that the proposed
watermark can be effectively detected, while faithfully preserving the data
fidelity, and also demonstrates appealing robustness against additive noise
attack. The general idea is to achieve the watermarking through a strategic
embedding based on simple data binning. Specifically, it divides the feature’s
value range into finely segmented intervals and embeds watermarks into
selected “green list" intervals. To detect the watermarks, we develop a
principled statistical hypothesis-testing framework with minimal assumptions:
it remains valid as long as the underlying data distribution has a continuous
density function. The watermarking efficacy is demonstrated through rigorous
theoretical analysis and empirical validation, highlighting its utility in
enhancing the security of synthetic and real-world datasets.

##  1 Introduction

The recent surge of powerful generative models has lead to increasingly adept
generative data synthesizers [1, 2, 3, 4, 5, 6, 7, 8, 9] that closely mimic
real datasets. However, the surge in AI-driven data synthesis also raises
significant concerns. Distinguishing AI-generated content from human-generated
content poses challenges that impact copyright infringement, privacy breaches,
and the spread of misinformation. These concerns have prompted regulatory
responses at both national and international levels. For example, the White
House’s Executive Order 111 https://www.whitehouse.gov/briefing-
room/presidential-actions/2023/10/30/executive-order-on-the-safe-secure-and-
trustworthy-development-and-use-of-artificial-intelligence/ and the EU’s
Artificial Intelligence Act 222 https://artificialintelligenceact.eu/wp-
content/uploads/2024/02/AIA-Trilogue-Committee.pdf both emphasize the
importance of secure, responsible AI practices and making AI-generated content
detectable and traceable to uphold transparency and protect users’ rights.

In the context of ensuring the integrity and authenticity of generative
products, watermarking techniques emerge as a common solution. Significant
advancements have been achieved in the watermarking of unstructured generative
data, such as texts [10], [11] and images [12] (please see Appendix A for an
extended discussion of related works). However, the structured domain of
tabular data remains less explored. Effective watermarking in this area must
address the specific challenges of maintaining data fidelity and usability in
structured datasets, which are critical in applications like healthcare and
finance where data integrity is paramount.

To fill in this important missing part on the landscape of watermarking
generative data, in this work we propose, to the best of our knowledge, the
first tabular data watermarking framework with solid theoretical foundation.
We focus extensively on watermarking continuous variables in the tabular data.
Our proposed mechanism is achieved through a strategic embedding of watermarks
using data binning. Specifically, it divides the feature’s value range into
finely segmented intervals and embeds watermarks into selected “green list”
intervals. This specification of “green list” intervals shares the same spirit
as “green list” techniques as in text data watermarks [10], while the
methodology and underlying theoretical framework are completely new. To detect
the watermarks, we develop a statistical hypothesis-testing framework with
minimal assumptions, requiring that the underlying data distribution has a
continuous density function. Finally, we provide empirical evidence that
demonstrates the effectiveness of our proposed framework on both synthetic and
real-world tabular datasets. We summarize and highlight our major
contributions as follows:

Figure 1: Overview of the tabular data watermarking scheme.

  * •

Theoretical guarantee of data fidelity: We show theoretically that finer or
smaller intervals result in watermarked data closer to the original data,
specifically with an error rate of $O(\frac{1}{m})$, where $m$ is the number
of “green list” intervals. Empirically, we observe minimal fidelity and
utility loss on both synthetic and real datasets when applying our proposed
watermark to the generative tabular data.

  * •

Principled detection framework: We propose a principled hypothesis-testing
framework for tabular data watermark detection. Our testing process is backed
by an interesting theoretical result that as the number of intervals
$m\to\infty$, the probability of a data point falls within the “green list”
intervals converges to $\frac{1}{2}$.

  * •

Robustness against noise masking attack: We demonstrate appealing robustness
of our proposed tabular data watermark against attacks with additive noise,
where attackers use continuous noise to perturb the watermarked tabular data.
Our theoretical result indicates that if the success probability of attacking
an individual element is capped at $\frac{1}{2}$, then even attacking almost
all elements is insufficient to significantly increase the likelihood of
overcoming the hypothesis test. We show that our watermark remains valid even
when $\sim 95\%$ of the elements are attacked with large noise. We validate
our result on both synthetic and real datasets, and observe that our watermark
can be effectively detected.

##  2 Watermarking Tabular Data

###  2.1 Problem Statement

We consider a dataset $\mathbf{X}$, structured as an $n\times p$ table where
each of the $p$ columns consists of $n$ i.i.d. data points from a distribution
$F_{i}$, each with a continuous probability density function
$f_{i},i=1,...,p$. Typically, $\mathbf{X}$ represents synthetic data generated
from some generative model, which we refer to as generative tabular data
throughout the paper. Our objective is to construct a watermarked version of
this dataset, denoted as $\mathbf{X}_{w}$. This watermarked dataset aims to
achieve three primary goals (Fig. 1): i) maintaining a minimal discrepancy
$|\mathbf{X}-\mathbf{X}_{w}|$ under standard assumptions; ii) ensuring that
$\mathbf{X}_{w}$ can be reliably identified as the outcome of our specific
detection process; and iii) achieving desirable robustness against potential
attacks. We next show how this watermark can be achieved with a surprisingly
simple yet effective procedure.

###  2.2 Watermarking Tabular Data with Data Binning

The proposed watermark is applied element-wise, with the detailed procedure
consisting of the following steps (illustrated in Fig. 2):

Input: number of “green list” intervals $m$; original tabular dataset
$\mathbf{X}$.

Output: watermarked dataset $\mathbf{X}_{w}$.

1 Interval Division: The continuous interval from 0 to 1 is divided into $2m$
equal parts, forming intervals such as $[0,\frac{1}{2m}]$,
$[\frac{1}{2m},\frac{2}{2m}]$, …, $[\frac{2m-1}{2m},1]$, and form $m$ pairs of
consecutive intervals
$\\{[0,\frac{1}{2m}],[\frac{1}{2m},\frac{2}{2m}]\\},\\{[\frac{2}{2m},\frac{3}{2m}],[\frac{3}{2m},\frac{4}{2m}]\\},\cdots,\\{[\frac{2m-2}{2m},\frac{2m-1}{2m}],[\frac{2m-1}{2m},1]\\}$.

2Green List Selection: From each pair of intervals, one interval is selected
as a “green list” interval. The resulting set of $m$ intervals is denoted as
$G$, the set of “green list” intervals.

3Watermark Embedding: for  _each element $x$ in $\mathbf{X}$_ do

4

5 Finding the nearest green list interval $g$: For the fractional part of each
data point $x$, we identify the closest interval on the green list as
$g=\operatorname*{arg\,max}\limits_{{g\in G}}\|\left(x-i(x)\right)-{\rm
center}(g)\|$, where $i(x)$ is the integer part of $x$.

6 Imposing green list constraints: If $x-i(x)\in g$, then $x$ is left as is.
Else, we replace $x$ as $i(x)+r$, where $r$ is uniformly sampled from $g$.

Algorithm 1 Tabular data watermarking algorithm. Figure 2: Illustration of our
proposed watermarking scheme for tabular data. Specifically, our scheme
consists of three major steps: i) dividing the continuous interval $[0,1]$
into $2m$ equal parts, forming $m$ pairs of consecutive intervals; ii)
randomly selecting one interval from each pair, resulting in the set of $m$
“green list” intervals; and iii) sampling new fractional part for the input
element from the nearest “green list” interval if the original fractional part
falls outside of this interval.

#### An illustrative example

We can consider an artificial $10\times 1$ dataset as an illustrative example
for the implementation of this watermarking process. Without loss of
generality, we can assume that the value range of this dataset is $[0,1]$.
Otherwise, we can subtract the integer part of each element in the table to
obtain the fractional part that falls with in $[0,1]$. In the context of this
manuscript, we therefore consider an element $x$ as falling into the “green
list” if and only if its fractional part $x-i(x)$ falls into one of the
intervals inside the “green list” intervals in $[0,1]$; $i(x)$ is the integer
part of $x$. For simplicity, we set the watermark with $m=5$. The value range
is then divided into 10 smaller intervals $\\{[0,0.1],...,[0.9,1]\\}$, forming
5 pairs of consecutive intervals $\\{P_{i}\\}_{i=1}^{5}$. From each pair, one
interval is randomly selected for the green list. As an example, the green
list intervals (highlighted in green) selected might be:

$\displaystyle
P_{1}=\\{{\color[rgb]{0,.5,.5}[0.0,0.1]},[0.1,0.2]\\},P_{2}=\\{[0.2,0.3],{\color[rgb]{0,.5,.5}[0.3,0.4]}\\},P_{3}=\\{{\color[rgb]{0,.5,.5}[0.4,0.5]},[0.5,0.6]\\},$
$\displaystyle
P_{4}=\\{[0.6,0.7],{\color[rgb]{0,.5,.5}[0.7,0.8]}\\},P_{5}=\\{[0.8,0.9],{\color[rgb]{0,.5,.5}[0.9,1.0]}\\}.$

Given this setup, a data point $x$ with a fractional value of 0.21 would be
identified as falling outside the green list interval in $P_{2}$.
Consequently, a new value would be randomly chosen from the nearest green list
interval, $\color[rgb]{0,.5,.5}[0.3,0.4]$. For instance, $0.31$ could be
selected as the watermarked value for $0.21$. This procedure is repeated for
each subsequent data point to generate a fully watermarked tabular dataset.
Given $m$, we can use $(x-i(x))/(1/2m)$ to find the nearest “green list”
intervals pair and consequently the closest interval with $O(1)$ time
complexity. Therefore, the overal time complexity for watermarking an $n\times
p$ tabular dataset is $O(np)$. We provide python-style pseudocode in Appendix
C to facilitate understanding of the watermarking scheme.

#### Tabular watermark with marginal data distortion

We establish the following theorem concerning the impact on data fidelity of
our watermarking approach.

######  Theorem 1 (Fidelity).

Let $\mathbf{X}$ be a $n\times p$ dataframe, and let $\mathbf{X}_{w}$ denote
its watermarked version. Conditioned on $\mathbf{X}$, it holds with
probability one that

$\|\mathbf{X}_{w}-\mathbf{X}\|_{\infty}\leq\frac{1}{m},$

where $m$ is the number of “green list” intervals, a parameter controlling the
granularity of the watermarking process.

We refer to Section B.1 for the full proof of Theorem 1. A corollary naturally
emerges that establishes an upper bound on the Wasserstein distance between
$\mathbf{X}_{w}$ and $\mathbf{X}$ based on Theorem 1, providing a quantifiable
measure of the distance between the two distributions.

######  Corollary 1.1.

Let $F_{\mathbf{X}}=\sum_{j=1}^{n}\frac{1}{n}\delta_{\mathbf{X}[j,:]}$ be the
empirical distribution built on $\mathbf{X}$, let
$F_{\mathbf{X}_{w}}=\sum_{j=1}^{n}\frac{1}{n}\delta_{\mathbf{X}_{w}[j,:]}$
built on $\mathbf{X}_{w}$, then it holds with probability one that

$\displaystyle\mathcal{W}_{k}\left(F_{\mathbf{X}},F_{\mathbf{X}_{w}}\right)\leq\frac{p^{\frac{1}{2}}}{m},$
(1)

where $\mathcal{W}_{k}$ is the $k$-Wasserstein distance.

######  Remark 1.

Theorem 1 assures us that the proposed watermark has marginal impact on the
data fidelity. Specifically, it indicates that by increasing $m$ to
sufficiently refine the granularity of the intervals (i.e., the length of each
interval is $1/(2m)$), the watermarked data $\mathbf{X}_{w}$ will closely
approximate the original $\mathbf{X}$, with an error rate of $1/m$ (the bounds
in Theorems 1 and 1.1 are tight). This property is crucial for ensuring that
the fidelity of the data is maintained, while still embedding a robust
watermark, as we will see later.

##  3 Detection of the Tabular Data Watermark

Similar to [10], the detection of watermarks in tabular data is conceptualized
within a theoretical framework that transforms the process into a hypothesis-
testing problem. In this context, we first introduce a theorem that solidifies
the theoretical underpinnings of watermark detection:

######  Lemma 1 (Prelim. for detection).

Consider a probability distribution $F$ with a continuous probability density
function $f$. As $m\rightarrow\infty$,

$P_{x\sim F}(x-i(x)\in G)\to\frac{1}{2},$

where $i(x)$ is the integer part of $x$, such that $x\in[i(x),i(x)+1)$; $G$
represents the set of green list intervals. $x-i(x)$ therefore specifies the
fractional part of the data point $x$.

######  Remark 2.

From the proof of Lemma 1 (see Section B.3), we can see that this convergence
is in fact consistent on all the possible choices of the green list.

We formulate the task of detecting watermarks as a hypothesis-testing problem:

$H_{0}$: The table is not watermarked. vs. $H_{1}$: The table is watermarked.

Based on the theoretical result in Lemma 1, we can claim that for any column
of continuous variables in the given tabular data, the probability of an
element falling into the “green list” intervals approximates $\frac{1}{2}$,
when $m$ is large enough. This result is tangential to how the “green list”
intervals are exactly chosen, _i.e_., any possible choice of these intervals
following the procedure in Algorithm 1 would suffice. Let $\mathbf{T}_{i}$
denotes the number of elements in the $i$-th column that fall into the “green
list” intervals. We can see that $\mathbf{T}_{i}$ approximately follows a
binomial distribution $B(n,\frac{1}{2})$ under $H_{0}$ when $m$ is large. For
a particular value $t_{i}$ of $\mathbf{T}_{i}$, the p-value can be calculated
using $\mathbf{P}(B(n,\frac{1}{2})\geq t_{i})$ to determine how statistically
significant $t_{i}$ is.

When $n$ is large, by the central limit theorem, we can further model $T_{i}$
by

$\displaystyle 2\sqrt{n}(\frac{T_{i}}{n}-\frac{1}{2})\to N(0,1).$ (2)

To extend the analysis to tabular data with multiple columns, we need to
consider the joint distribution across all all $p$ columns. We present the
following theorem that indicates a quite surprising result which we term as
the “asymptotic independence” of the watermarked column distributions.
Specifically, for a random sample (one random row) of the $n\times p$ table,
_i.e_., $\mathbf{x}=(x_{1},x_{2},\cdots,x_{p})$ generated from a distribution
$F$ with continuous probability density function, the events
$\\{x_{i}-i(x_{i})\in G\\},i=1,2,\cdots,p$ are independent when $m\to\infty$:

######  Theorem 2 (Asymptotic independence).

Consider a $p$-dimensional probability distribution $F$ with continuous
probability density function $p(x_{1},x_{2},x_{3},\cdots,x_{p})$, then as
$m\to\infty$,

$\displaystyle\begin{split}\mathbf{P}_{x\sim
F}(\bigcap_{i=1}^{p}A_{i})\to(\frac{1}{2})^{p},\end{split}$ (3)

where $A_{i}\in\\{\\{x-i(x)\in G\\},\\{x-i(x)\notin G\\}\\}$

######  Remark 3.

Theorem 2 implies that when $m$ is large enough, $\\{T_{i}\\}_{i=1}^{p}$ are
independent random variables. Of note, the independence shown above does not
require independence of the data distribution, making this statement
especially non-trivial; it holds for any continuous density functions. We can
see from the proof in Section B.4 that the independence originates from our
design of the watermarking process, and is induced by sufficiently large $m$.

Consequently, we can establish that as $n$ approaches infinity, the sum of
squared standardized deviations of $T_{j}$ converges to a chi-squared
distribution by definition:

$\displaystyle\sum_{j=1}^{p}\left[2\sqrt{n}\left(\frac{T_{j}}{n}-\frac{1}{2}\right)\right]^{2}\to\chi^{2}_{p}.$
(4)

Of note, in practical scenarios, the specific entries that are watermarked
within the table could remain unknown. Consequently, it is imperative to
consider all columns uniformly, which results in the chi-squared testing as
detailed above. Another practical concern is that sometimes it is possible to
encounter datasets with high dimensionality, _i.e_., large $p$. We provide the
following asymptotic result indicating that the $\chi_{p}^{2}$ statistics
remain valid even when the dimension $p$ goes to infinity, as long as $p$ and
$n$ goes to infinity with certain rates:

######  Theorem 3.

Assume that $\\{T_{i}\\}_{i=1}^{p}$ i.i.d. follows $B(n,\frac{1}{2})$, then as
$n\to\infty$, if $p=o(n^{\frac{2}{7}})$, we have

$\displaystyle\sum_{j=1}^{p}\left[2\sqrt{n}\left(\frac{T_{j}}{n}-\frac{1}{2}\right)\right]^{2}\xrightarrow{d}\chi^{2}_{p}.$
(5)

still holds even if $p\to\infty$.

##  4 Robustness of the Tabular Data Watermark

In this section, we further examine the robustness of the proposed watermark
when exposed to attacks. We assume that the attacker has no knowledge about
the “green list” intervals. Since our detection framework is based on
hypothesis-testing, the ultimate goal of this attack can be regarded as
increasing p-value as much as possible.

Specifically, we consider a scenario where the attacker alters $k_{i}$
elements from green-listed to non-green-listed in the $i$-th column of a fully
watermarked tabular dataset. The resultant chi-square statistic for this
modification is
$\sum_{j=1}^{p}4n\left(\frac{1}{2}-\frac{k_{i}}{n}\right)^{2}$. Therefore, to
assess the robustness of the proposed watermark, we identify the minimum of
$\sum_{j=1}^{p}k_{i}$ such that:

$\sum_{j=1}^{p}4n\left(\frac{1}{2}-\frac{k_{i}}{n}\right)^{2}\leq\chi^{2}_{p}(1-\alpha),$
(6)

where $\chi^{2}_{p}(1-\alpha)$ is the $(1-\alpha)\%$ quantile of the chi-
square distribution with $p$ degrees of freedom. Typically, $1-\alpha$ is set
as $0.95$. Eq. 6 quantifies the minimum number of elements required for a
successful attack, _i.e_., increasing the p-value so that it is higher than
$\alpha$. By Mean Squared-Arithmetic Inequality, to achieve this target, we
require:

$\displaystyle\frac{2\sqrt{n}\sum_{j=1}^{p}\left(\frac{1}{2}-\frac{k_{i}}{n}\right)}{p}\leq\sqrt{\frac{\sum_{j=1}^{p}4n\left(\frac{1}{2}-\frac{k_{i}}{n}\right)^{2}}{p}}\leq\sqrt{\frac{\chi^{2}_{p}(1-\alpha)}{p}},$
(7)

which consequently implies that:

$\sum_{j=1}^{p}k_{j}\geq\frac{1}{2}(np)-\frac{1}{2}\sqrt{np}\sqrt{\chi^{2}_{p}(1-\alpha)}.$
(8)

Eq. 8 demonstrates a lower bound of the number of elements to be moved out of
“green list” intervals for a successful attack.

To further assess the robustness of our watermarking framework, we consider
the common choice of attacking with additive noise, since a wide range of
attacks can be generally regarded as adding noise to the watermarked data;
different noise distributions correspond with different attacking strategies.
We start with examining how these attacks influence the distribution of green-
listed elements. The probability that this additive noise successfully moves
an element out of the “green list” intervals (a.k.a. attack success rate) is
specified by the following theorem:

######  Theorem 4 (Attack success rate).

Given noise $\epsilon$ following a (not necessarily zero mean) distribution
$A$ with a continuous probability density function, for any $x_{w}$ whose
fractional part lies within a green list interval, as $m\to\infty$,

$P_{\epsilon\sim
A}(x_{w}+\epsilon-i(x_{w}+\epsilon)\notin\textit{G})\to\frac{1}{2},$

where $i(\cdot)$ is the integer part, _i.e_.,
$x_{w}+\epsilon\in[i(x_{w}+\epsilon),i(x_{w}+\epsilon)+1)$.

###### Proof.

The idea for proving Theorem 4 is as follows. Given $x_{w}$, $x_{w}+\epsilon$
is a random variable with a continuous density. In Lemma 1 we have proved that
the probability of any random variable with a continuous density falling into
the “green list” intervals converges to $\frac{1}{2}$. Symmetrically, the
probability of any random variable with a continuous density not falling into
the “green list” intervals also converges to $\frac{1}{2}$. Applying this to
$x_{w}+\epsilon$, we finish the proof of Theorem 4. ∎

Motivated by the preceding discussions, we would like to address a crucial
scenario: if each element within the “green list” intervals has an upper-
bounded attack success probability of $q\leq\frac{1}{2}$ (note that
$q\to\frac{1}{2}$ regardless of the distribution of $\epsilon$ as
$m\to\infty$), how many elements must be attacked to ensure a p-value higher
than $\alpha$, thereby indicating a successful attack?

We therefore formalize the following theorem:

######  Theorem 5 (Robustness).

Consider a $n\times p$ table $\mathbf{X}$ with all elements initially in the
“green list” intervals. If the prob. of successfully attacking each element is
no more than $\frac{1}{2}$, and $\widehat{k}_{i}$ denotes the number of
elements attacked in the $i$-th column, then an attack will fail—meaning the
calculated p-value will be $\alpha$ or higher—with at least probability
$1-e^{-\frac{1}{2}(\sqrt{np}-\sqrt{\mathcal{X}_{p}^{2}(1-\alpha)})}$ if:

$\sum_{j=1}^{p}\widehat{k}_{j}\leq\frac{1}{1+\frac{1}{(np)^{\frac{1}{4}}}}(np-\sqrt{np}\sqrt{\mathcal{X}_{p}^{2}(1-\alpha)}).$

######  Remark 4.

Theorem 5 underscores that if the success probability of attacking an
individual element is capped at $\frac{1}{2}$, then even attacking
$(1+o(1))np$ elements is insufficient to significantly increase the likelihood
of overcoming the hypothesis test. This result implies that an extensive
number of targeted attacks is required to disrupt the hypothesis-testing
mechanism effectively.

##  5 Experiments

We now empirically evaluate our proposed tabular data watermark regarding i)
fideliy, ii) detection rate and iii) robustness on synthetic and real-world
datasets. We kindly refer to Appendix D for additional experiment settings,
results and discussions.

###  5.1 Synthetic Dataset Examples

We first evaluate our method with synthetic data as a quick sanity check to
validate our theoretical results. As the proof-of-concept experiments, we use
Gaussian data to show that our framework can indeed greatly maintain data
fidelity, demonstrate satisfying detection rates and achieve appealing
robustness against attacks with additive noise. We set $m=1000$ for the
following experiments.

#### Fidelity

We start with evaluating the impact of our tabular data watermark on data
fidelity with single-column data. Specifically, we draw a $2000\times 1$ table
from standard Gaussian to embed our proposed watermark. We can see from the
kernel density estimation results in LABEL:subfig:kde_syn_before and
LABEL:subfig:kde_syn_after that our proposed watermark has negligible impact
on the original data distribution, consistent with our statement in Theorems 1
and 1.1. We provide quantitative results on real datasets in Table 1 and
Appendix E. We further evaluate the impact of our watermark on correlated
multi-column data. To enforce the correlation between columns, we iteratively
generate each column as $X_{j+1}=1.1X_{j}+\epsilon$ if $j$ is odd, or
$X_{j+1}=X_{j}/1.1+\epsilon$ if $j$ is even, $j=1,...,p$. $X_{j}$ denotes the
$j$-th column data, and $\epsilon\sim N(0,I_{n})$. In this experiment, we
construct a $10000\times 1000$ table, and calculate the correlation matrices
before and after applying our tabular data watermark ($m=1000$) to probe the
impact. We can see from LABEL:subfig:corr_no_wm, LABEL:subfig:corr_wm_all and
LABEL:subfig:corr_diff that the proposed watermark demonstrates marginal
influences on the statistical relation among columns, with a maximum absolute
difference of correlation values of $\sim 0.01$.

#### Detection rate (True Postive Rate)

For multi-column tabular data, we consider two scenarios including i) adding
the watermark to only one column, as a stress test to examine the
effectiveness of our approach with extremely limited computational resources,
and ii) adding the watermark to all columns in the table, which is the
standard case. We evaluate the detection rates when applying our watermark to
tables with different number of rows and columns (see
LABEL:subfig:chi_sing_col and LABEL:subfig:chi_mult_col). The true negative
rate is 1 in all settings. We refer to Sections D.1 and E for details and ROC-
AUC scores. In LABEL:subfig:chi_sing_col, we observe that the watermark is
still largely detectable even when only one column is watermarked. We can see
that the detection rate under this particular circumstance is high as long as
the number of rows is sufficiently large. In LABEL:subfig:chi_mult_col, the
detection rate is constantly high regardless of the size of the table,
confirming the effectiveness of our approach. We refer to Appendix E for
additional results of simulating high-dimensional tables, where the column
number $p$ exceeds the row number, _e.g_. $p=100n$. Our watermark can still be
effectively detected with near perfect rates.

#### Robustness

In these experiments, we apply the watermark to tables of size $5000\times
100$ as the representative, and then add Gaussian noises with different
variances to perturb different proportion of the watermarked data. In
LABEL:subfig:chi_sing_col_atck, it is demonstrated that watermarking just a
single column (approx. 1% of the original data) already has decent robustness
when 75% of the elements are modified by the attacker. In
LABEL:subfig:chi_mult_col_atck, the detection rate is constantly high
regardless of the variance of the added noise or the proportion (can be as
high as $\sim 95\%$) of the elements being modified, as long as all columns
are watermarked. The result in LABEL:subfig:chi_mult_col_atck is particularly
encouraging as the variance of the added noise can be as large as 10, while
the variance of data distribution is only approximately 1. The results support
our theoretical analysis in Theorem 5.

###  5.2 Results on Generative Tabular Data

In this section, we extensively evaluate our watermarking framework on real-
world datasets to check the effectiveness of our approach.

#### Datasets & tab. generators

Specifically, we employ TVAE [13], CTABGAN [14] and TabDDPM [15] as
representatives of VAE-based [16], GAN-based [17], and DDPM-based [2] tabular
data generators to generate tabular data. For systematic investigation of our
tabular data watermark performance on these tabular generative models, we
consider a diverse set of 6 real-world public datasets with various sizes,
nature, number of features, and their distributions; these datasets are
commonly used for tabular model evaluation [14, 18]. We provide additional
details of datasets, evaluation measure, and tunning process for tabular data
generators in Section D.2.

#### Practical implementation

In practice, some columns in certain generated datasets can follow ill-shaped
distributions, _e.g_., some distributions have spikes concentrated on certain
values, which may violate the assumption of our framework (see Appendix E). To
be specific, from Lemma 1 we know that as $m$ tends to infinity, the
probability of an element falling within a “green list” interval converges to
1/2. The rate at which this convergence occurs, however, depends largely on
the smoothness of the distribution. To address this issue, we therefore adopt
a heuristic approach by selecting columns with relatively smooth data
distributions to embed the watermark.

Our heuristic approach assumes that for a column data distribution with enough
smoothness, the probability of an element falling within a “green list”
interval, denoted as $\widehat{p}$, lies with in
$[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]$, when $m$ is not sufficiently large.
We can therefore use the frequency $\widehat{f}\approx\widehat{p}$ of an
element falling within “green list” intervals as an indicator of the
distribution smoothness. Specifically, to filter out the columns with low
smoothness, we set $\Delta=0.01$ and $m$ to be within the range
$\\{1000,1500,2000,2500,...,4500,5000\\}$ and count for each column how many
times $\widehat{f}$ falls outside the range
$[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]$ with different choices of $m$.
Specifically, we sweep $m$ over its range, and repeat the experiment 5 times
for each value of $m$. If the number exceeds 10% of the total number ($5\times
9$) of experiments, then we identify this column as a non-smooth column and
discard it (see Appendix E for further results of this filtering process; most
generated datasets remain untouched). For the rest of these columns, we choose
for each column the $m$ that maximize the number of times that $\widehat{f}$
falls inside the range $[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]$ to conduct
the following experiments. For each column, we normalize the distribution to
zero mean and unit variance before adding our proposed watermark.

#### Fidelity

We verify the distribution distance between the original generated data and
watermarked data is indeed of $O(\frac{1}{m})$. In Table 1, we calculate the
Wasserstein-1 distance between the empirical distribution generated by TabDDPM
(see Appendix E for results of TVAE and CTABGAN) and its watermarked version;
we provide the distance between real data and generated data for reference.

Table 1: Wasserstein-1 distance between generated data distribution and watermarked data distribution. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
Orig2Gen | 0.0222 | 0.0602 | 0.0315 | 0.0767 | 0.0142 | 0.0161
Gen2Watermarked | 0.0004 | 0.0004 | 0.0004 | 0.0005 | 0.0003 | 0.0001
$m$ | 1000 | 1000 | 1000 | 1000 | 1000 | 2500
$1/m$ | 0.001 | 0.001 | 0.001 | 0.001 | 0.001 | 0.0004

#### Accuracy of the watermarked tabular data

We summarize the effectiveness (measured by ROC-AUC scores) of our tabular
data watermark on the generated tabular data. We can see in Table 2 that our
method demonstrates desirable accuracies on these generated datasets.

Table 2: Accuracy (ROC-AUC score) of the tabular data watermark. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
TVAE | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000
CTABGAN | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000
TabDDPM | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 0.999

#### Robustness

To examine the robustness of our approach, we add zero mean Gaussian noise
with the standard variance as $0.01\widehat{\sigma}$ to perturb the
watermarked tabular data; $\widehat{\sigma}$ represents the standard variance
of the watermarked tabular data. We choose this relatively small noise
variance to make sure that the ML efficiency (or utility) [13] of the
generated data is not severely deteriorated by the attacks, while the added
noise can distort the watermark as much as possible. This is consistent with
most practical scenarios, where the attacker intends to remove the watermark
as much as possible while preserving the original data information (_e.g_.,
[10, 19]). The noise are added to 95% of all the elements in the watermarked
tabular data. We can see from Table 3 that our watermark can still be reliably
detected on all the generated datasets.

Table 3: Accuracy (ROC-AUC score) of the tabular data watermark after additive noise attack. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
TVAE | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000
CTABGAN | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000
TabDDPM | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 0.999

#### Utility

To examine the impact of our watermark on the utility of the generated data,
we follow the evaluation protocol in [15] and train CatBoost classifiers [20]
using the watermarked generated data and the original generated data and
compare the performances. We can see in Table 4 that our tabular data
watermark has negligible impact on the utility of the synthesized data.

Table 4: Impact of the tabular data watermark on utility. The metrics used for each dataset is provided after the dataset name. Results calculated using 20 generated copies of the original dataset. | Generator | California (R2) | Gesture (F1) | House (R2)
---|---|---|---|---
| TVAE | $0.736\pm 0.004$ | $0.418\pm 0.012$ | $0.448\pm 0.010$
orig. data | CTABGAN | $0.577\pm 0.007$ | $0.411\pm 0.005$ | $0.327\pm 0.008$
| TabDDPM | $0.823\pm 0.003$ | $0.575\pm 0.009$ | $0.638\pm 0.007$
| TVAE | $0.735\pm 0.037$ | $0.419\pm 0.012$ | $0.449\pm 0.011$
wm. data | CTABGAN | $0.577\pm 0.007$ | $0.409\pm 0.009$ | $0.328\pm 0.007$
| TabDDPM | $0.823\pm 0.003$ | $0.554\pm 0.007$ | $0.638\pm 0.007$
| Generator | Wilt (F1) | Higgs-small (F1) | Miniboone (F1)
| TVAE | $0.500\pm 0.020$ | $0.665\pm 0.001$ | $0.905\pm 0.002$
orig. data | CTABGAN | $0.666\pm 0.019$ | $0.602\pm 0.004$ | $0.852\pm 0.002$
| TabDDPM | $0.892\pm 0.017$ | $0.713\pm 0.002$ | $0.931\pm 0.001$
| TVAE | $0.494\pm 0.020$ | $0.665\pm 0.001$ | $0.905\pm 0.002$
wm. data | CTABGAN | $0.666\pm 0.019$ | $0.601\pm 0.005$ | $0.852\pm 0.002$
| TabDDPM | $0.886\pm 0.013$ | $0.713\pm 0.002$ | $0.930\pm 0.001$

##  6 Conclusion

This paper presents a new watermarking method for tabular data to ensure the
fidelity of synthetic datasets. The approach embeds watermarks into finely
segmented data intervals, using a "green list" technique to minimize
distortion and retain high data fidelity. A robust statistical hypothesis-
testing framework is then proposed allowing for reliable detection of the
watermarks, even in the presence of additive noise with large variances.
Experimental results demonstrate the effectiveness of the technique, with
near-perfect detection rates in terms of AUC. The watermarking process shows
high robustness against Gaussian noise attacks while having minimal impact on
data utility, indicating its usefulness in practical scenarios where ML
efficency for downstream tasks is of primary concern. This work contributes to
enhancing the security of both synthetic and real-world datasets, which is
critical in the context of AI and machine learning applications. Future
research could focus on improving the robustness of the watermarking method
and extending its applicability across different types of data, for example,
the categorical data.

## References

  * Vaswani et al. [2017] 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.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Song et al. [2020] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  In _International Conference on Learning Representations_ , 2020.
  * Yu et al. [2021] Peiyu Yu, Sirui Xie, Xiaojian Ma, Yixin Zhu, Ying Nian Wu, and Song-Chun Zhu.  Unsupervised foreground extraction via deep region competition.  _Advances in Neural Information Processing Systems_ , 34:14264–14279, 2021.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10684–10695, 2022.
  * Yu et al. [2022] Peiyu Yu, Sirui Xie, Xiaojian Ma, Baoxiong Jia, Bo Pang, Ruiqi Gao, Yixin Zhu, Song-Chun Zhu, and Ying Nian Wu.  Latent diffusion energy-based model for interpretable text modeling.  _arXiv preprint arXiv:2206.05895_ , 2022.
  * Qian et al. [2023] Yilue Qian, Peiyu Yu, Ying Nian Wu, Wei Wang, and Lifeng Fan.  Learning concept-based visual causal transition and symbolic reasoning for visual planning.  _arXiv preprint arXiv:2310.03325_ , 2023.
  * Yu et al. [2024] Peiyu Yu, Yaxuan Zhu, Sirui Xie, Xiaojian Shawn Ma, Ruiqi Gao, Song-Chun Zhu, and Ying Nian Wu.  Learning energy-based prior model with diffusion-amortized mcmc.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Zhang et al. [2024] Yasi Zhang, Peiyu Yu, and Ying Nian Wu.  Object-conditioned energy-based attention map alignment in text-to-image diffusion models.  _arXiv preprint arXiv:2404.07389_ , 2024.
  * Kirchenbauer et al. [2023] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein.  A watermark for large language models.  In _International Conference on Machine Learning_ , pages 17061–17084. PMLR, 2023.
  * Zhao et al. [2023a] Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang.  Provable robust watermarking for ai-generated text.  In _The Twelfth International Conference on Learning Representations_ , 2023a.
  * Wen et al. [2023] Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein.  Tree-rings watermarks: Invisible fingerprints for diffusion images.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=Z57JrmubNl.
  * Xu et al. [2019] Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni.  Modeling tabular data using conditional gan.  _Advances in neural information processing systems_ , 32, 2019.
  * Zhao et al. [2021] Zilong Zhao, Aditya Kunar, Robert Birke, and Lydia Y Chen.  Ctab-gan: Effective table data synthesizing.  In _Asian Conference on Machine Learning_ , pages 97–112. PMLR, 2021.
  * Kotelnikov et al. [2023] Akim Kotelnikov, Dmitry Baranchuk, Ivan Rubachev, and Artem Babenko.  Tabddpm: Modelling tabular data with diffusion models.  In _International Conference on Machine Learning_ , pages 17564–17579. PMLR, 2023.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27, 2014.
  * Gorishniy et al. [2021] Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko.  Revisiting deep learning models for tabular data.  _Advances in Neural Information Processing Systems_ , 34:18932–18943, 2021.
  * Zhao et al. [2023b] Xuandong Zhao, Kexun Zhang, Zihao Su, Saastha Vasan, Ilya Grishchenko, C Kruegel, G Vigna, YX Wang, and L Li.  Invisible image watermarks are provably removable using generative ai.  _Saastha Vasan, Ilya Grishchenko, Christopher Kruegel, Giovanni Vigna, Yu-Xiang Wang, and Lei Li,“Invisible image watermarks are provably removable using generative ai,” Aug_ , 2023b.
  * Prokhorenkova et al. [2018] Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin.  Catboost: unbiased boosting with categorical features.  _Advances in neural information processing systems_ , 31, 2018.
  * Christ et al. [2023] Miranda Christ, Sam Gunn, and Or Zamir.  Undetectable watermarks for language models.  _arXiv preprint arXiv:2306.09194_ , 2023.
  * Zhao et al. [2024] Xuandong Zhao, Lei Li, and Yu-Xiang Wang.  Permute-and-flip: An optimally robust and watermarkable decoder for llms.  _arXiv preprint arXiv:2402.05864_ , 2024.
  * Zhao et al. [2022] Xuandong Zhao, Lei Li, and Yu-Xiang Wang.  Distillation-resistant watermarking for model protection in nlp.  _arXiv preprint arXiv:2210.03312_ , 2022.
  * Zhao et al. [2023c] Xuandong Zhao, Yu-Xiang Wang, and Lei Li.  Protecting language generation models via invisible watermarking.  In _International Conference on Machine Learning_ , pages 42187–42199. PMLR, 2023c.
  * Xu et al. [2024] Xiaojun Xu, Yuanshun Yao, and Yang Liu.  Learning to watermark llm-generated text via reinforcement learning.  _arXiv preprint arXiv:2403.10553_ , 2024.
  * Wen et al. [2024] Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein.  Tree-rings watermarks: Invisible fingerprints for diffusion images.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Fernandez et al. [2023] Pierre Fernandez, Guillaume Couairon, Hervé Jégou, Matthijs Douze, and Teddy Furon.  The stable signature: Rooting watermarks in latent diffusion models.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 22466–22477, 2023.
  * Zhang et al. [2023] Hanlin Zhang, Benjamin L Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak.  Watermarks in the sand: Impossibility of strong watermarking for generative models.  _arXiv preprint arXiv:2311.04378_ , 2023.
  * Bentkus [2005] Vidmantas Bentkus.  A lyapunov-type bound in rd.  _Theory of Probability & Its Applications_, 49(2):311–323, 2005.
  * Vershynin [2018] Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Akiba et al. [2019] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama.  Optuna: A next-generation hyperparameter optimization framework.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 2623–2631, 2019.

##  Appendix A Related Works

With the burgeoning success of generative models, there has been an increasing
focus on integrating watermarking techniques into these models to enhance
security and traceability recently.

#### LLM watermark

One class of watermarking techniques for text generated by LLMs is based on
dividing the vocabulary into “green lists” and “red lists”. This line of works
shares the spirit of our proposed tabular data watermark, but differs
significantly from the methodological perspective. Representative works of
this interesting direction include [10] and [11]. [10] embeds watermarks by
prioritized sampling of randomized “green list” tokens during text generation.
It considers “hard” and “soft” embedding of “green list” tokens, which
demonstrates great empirical effectiveness on the modern LLMs such as the OPT
model. [11] introduces a framework that infuses binary signatures into LLM-
generated text using a learning-based approach. The framework features three
key components: a message encoding module to embed the binary signatures, a
reparameterization module to transform the encoded messages for reliable
embedding, and a decoding module to extract the watermarks. An optimized beam
search algorithm is employed to ensure the watermarked text remains coherent
and consistent.

Concurrently, watermarking LLM-generated text from the cryptographic
perspective has led to fruitful and inspiring results in this direction. [21]
introduces a watermarking scheme that embeds undetectable watermarks into
generated text by modifying token selection probabilities using cryptographic
techniques. This makes the watermark detectable only by those with a secret
key. Similarly, [22] presents the Permute-and-Flip (PF) decoder, which offers
a watermarking scheme specifically tailored for the PF decoder. This scheme
aims to maintain text quality and robustness while performing well in terms of
perplexity and the detectability of watermarked texts. Additionally, there are
methods that embed watermarks directly into the weights of LLMs [23, 24, 25].
Specifically, [23] introduces Distillation-Resistant Watermarking (DRW), which
injects watermarks into prediction probabilities using a sinusoidal signal.
The proposed watermark can be effectively detected by model probing, without
inducing significant performance loss of the original model. [24] presents
GINSEW, embedding invisible watermarks into probability vectors during text
generation, which is detectable only with a secret key and robust against
synonym randomization attacks. [25] introduces a reinforcement learning-based
framework that co-trains a LLM and a detector to embed watermarks into model
weights. The proposed framework has an emphasized robustness against
adversarial attacks while successfully maintaining model utility.

#### Watermarking generated image data

Watermarking generative image data has drawn growing interest especially in
recent years. In the pioneering work of [26], the proposed framework embeds
watermarks into the initial noise vector of diffusion models during the
sampling process, resulting in surprisingly resilient, effective and invisible
image data watermark. [27] finetunes the decoder of a diffusion model to embed
watermarks directly into generated images, ensuring high detection accuracy
and robustness against modifications. Both approaches emphasize the importance
of embedding watermarks during the generation process to ensure invisibility
and robustness.

#### Challenges in watermarking AI-generated data

Recent studies highlight significant theoretical and practical challenges in
watermarking AI-generated content. [28] proves the theoretical impossibility
of simultaneously creating i) strong watermarks that cannot be removed by a
computationally bounded attacker and ii) watermarks that does not
significantly degrade data quality. As a counterexample, it constructs a
random-walk-based attack that preserves content quality while effectively
removing watermarks. [19] demonstrates the practical vulnerability of
invisible watermarks, showing that regeneration attacks with noise addition
and image reconstruction via generative models can remove up to $99\%$ of
watermarks without significant quality loss. These findings emphasize the need
to shift from invisible to semantically visible watermarks for robust
protection.

##  Appendix B Proof of Main Theorems

###  B.1 Proof of Theorem 1

###### Proof.

$\forall x\in\mathbf{X}$, assume $x-i(x)$ lies in the $jth$ pair of
consecutive intervals
$[\frac{2j-2}{2m},\frac{2j-1}{2m}]\cup[\frac{2j-1}{2m},\frac{2j}{2m}]$. In our
watermarking process, we resample a value $x_{w}$ from the nearest interval in
the “green list” intervals $G$ to replace the $x$. We can see that

$\displaystyle\operatorname*{arg\,min}_{Y\in G}\min_{y\in
Y}d(x,y)=\operatorname*{arg\,min}_{Y\in G}\max_{y\in Y}d(x,y).$

Assume $Y^{*}$ is the chosen nearest interval from the green list, and
$Y^{**}$ is the interval chosen to be in the green list in the group
$\\{[\frac{2j-2}{2m},\frac{2j-1}{2m}],[\frac{2j-1}{2m},\frac{2j}{2m}]\\}$, we
then have

$\displaystyle d(x,x_{w})\leq\max_{y\in Y^{*}}d(x,y)\leq\max_{y\in
Y^{**}}d(x,y)\leq\max_{y\in[\frac{2j-2}{2m},\frac{2j-1}{2m}]\cup[\frac{2j-1}{2m},\frac{2j}{2m}]}d(x,y)\leq\frac{1}{m}$

∎

###  B.2 Proof of Corollary 1.1

###### Proof.

The $k$-Wasserstein distance for two discrete measures

$\mu_{0}:=\sum_{i=1}^{k_{0}}a_{0i}\delta_{x_{0i}}\quad\text{ and
}\quad\mu_{1}:=\sum_{i=1}^{k_{1}}a_{1i}\delta_{x_{1i}},$ (A1)

is defined as

$\left[\mathcal{W}_{k}\left(\mu_{0},\mu_{1}\right)\right]^{k}=\left\\{\begin{aligned}
\min_{T\in\mathbb{R}^{k_{0}\times
k_{1}}}&\sum_{ij}T_{ij}\left|x_{0i}-x_{1j}\right|_{2}^{k}\\\ \text{ s.t.
}&T\geq 0\\\ &\sum_{j}T_{ij}=a_{0i}\\\
&\sum_{i}T_{ij}=a_{1j}.\end{aligned}\right.$ (A2)

For $F_{\mathbf{X}}$ and $F_{\mathbf{X}_{w}}$, if we take
$T=diag\\{\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}\\}$,
$x_{0i}=\mathbf{X}[i,:],x_{1j}=\mathbf{X}_{w}[j,:]$ in (A2), we could see

$\displaystyle\mathcal{W}_{k}\left(F_{\mathbf{X}},F_{\mathbf{X_{w}}}\right)\leq(\sum_{j=1}^{n}\frac{1}{n}\|\mathbf{X}[j,:]-\mathbf{X}_{w}[j,:]\|_{2}^{k})^{\frac{1}{k}}\leq\frac{p^{\frac{1}{2}}}{m}$
(A3)

∎

###  B.3 Proof of Lemma 1

###### Proof.

We prove this by using the technique of truncation. $\forall\epsilon>0$, we
could first choose $n$ large enough, so that

$\displaystyle\int_{-n}^{n}f(x)dx>1-\epsilon.$

Denote the “green list” intervals $G$ in $[0,1]$ as
$\\{g_{1}(0),g_{2}(0),\cdots,g_{m}(0)\\}$, where $g_{i}(0)$ is the interval
chosen in the $i$-th group to be in the green list. We then define $g_{k}(j)$
as $g_{k}+j$, $\forall j\neq 0$. Therefore,

$\displaystyle\mathbf{P}(x-i(x)\in G)$
$\displaystyle=\mathbf{P}(x\in\bigcup_{j=-\infty}^{\infty}\bigcup_{k=1}^{m}g_{k}(j))$
$\displaystyle=\mathbf{P}(x\in\bigcup_{j=-\infty}^{-n-1}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=n+1}^{\infty}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j)),$

the first two terms of which could be bounded by

$\displaystyle\mathbf{P}(x\in\bigcup_{j=-\infty}^{-n-1}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=n+1}^{\infty}\bigcup_{k=1}^{m}g_{k}(j))$
$\displaystyle\leq\int_{-\infty}^{-n}f(x)dx+\int_{n}^{\infty}f(x)dx$
$\displaystyle=1-\int_{-n}^{n}f(x)dx<\epsilon.$

We next consider the third term: we use $h_{k}(j)$ to denote the interval such
that $g_{k}(j)\cup h_{k}(j)=[\frac{k-1}{m}+j,\frac{k}{m}+j]$. We can see that
$h_{k}(0)$ is the complement of the $k$-th “green list” intervals in the
$k$-th group
$\\{[\frac{2j-2}{2m},\frac{2j-1}{2m}],[\frac{2j-1}{2m},\frac{2j}{2m}]\\}$, and
$h_{k}(j)=h_{k}(0)+j$.

We then have

$\displaystyle|\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))-\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}h_{k}(j))|$
$\displaystyle\leq\sum_{j=-n}^{n}\sum_{k=1}^{m}|\mathbf{P}(x\in
g_{k}(j))-\mathbf{P}(x\in h_{k}(j))|$
$\displaystyle=\sum_{j=-n}^{n}\sum_{k=1}^{m}|\int_{x\in
g_{k}(j)}f(x)dx-\int_{x\in h_{k}(j)}f(x)dx|$
$\displaystyle\leq\sum_{j=-n}^{n}\sum_{k=1}^{m}\max_{x\in g_{k}(j),y\in
h_{k}(j)}|f(x)-f(y)|\frac{1}{m}$ $\displaystyle\leq\max_{k,j}\max_{x\in
g_{k}(j),y\in h_{k}(j)}|f(x)-f(y)|(2n+1).$

Using the result that a continuous function in a compact set is uniformly
continuous, we can find some $m_{0}$ so that when $m\geq m_{0}$, namely
$\frac{2}{m}\leq\frac{2}{m_{0}}$,

$\displaystyle\max_{k,j}\max_{x\in g_{k}(j),y\in
h_{k}(j)}|f(x)-f(y)|\leq\max_{-n\leq x,y\leq
n;|x-y|\leq\frac{2}{m_{0}}}|f(x)-f(y)|<\frac{\epsilon}{2n+1}.$

Under this circumstance, we have

$\displaystyle|\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))-\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}h_{k}(j))|\leq\max_{k,j}\max_{x\in
g_{k}(j),y\in h_{k}(j)}|f(x)-f(y)|(2n+1)<\epsilon,$

which implies

$\displaystyle
2\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))-\epsilon$
$\displaystyle\leq\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}h_{k}(j))$
(A4) $\displaystyle\leq
2\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))+\epsilon.$

Note that

$1-\epsilon<\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}h_{k}(j))=\mathbf{P}(x\in[-n,n])\leq
1,$ (A5)

Plugging (A4) into (A5), we then have

$\displaystyle
1-2\epsilon<2\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))\leq
1+\epsilon,$

Therefore we have

$\displaystyle{P({x}-i(x)\in G)}$
$\displaystyle=\mathbf{P}(x\in\bigcup_{j=-\infty}^{-n-1}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=n+1}^{\infty}\bigcup_{k=1}^{m}g_{k}(j))+\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))$
(A6) $\displaystyle\leq\epsilon+\frac{1+\epsilon}{2},$

and

$\displaystyle P({x}-i(x)\in
G)\geq\mathbf{P}(x\in\bigcup_{j=-n}^{n}\bigcup_{k=1}^{m}g_{k}(j))>\frac{1}{2}-\epsilon,$
(A7)

since $\forall\epsilon>0$, we have a $m_{0}$ so that when $m>m_{0}$, (A6) and
(A7) hold, we finsh the proof. ∎

###  B.4 Proof of Theorem 2

To prove Theorem 2, we first prove a lemma:

######  Lemma 2.

Consider a $p$-dimensional probability distribution $F$ supported in
$\|x\|_{2}\leq R$ with continuous probability density function
$p(x_{1},x_{2},x_{3},\cdots,x_{p})$, then as $m\to\infty$,

$\displaystyle\begin{split}\mathbf{P}_{x\sim
F}(\bigcap_{k=1}^{p}A_{k})\to(\frac{1}{2})^{p},\end{split}$ (A8)

where $A_{i}\in\\{\\{x-i(x)\in G\\},\\{x-i(x)\notin G\\}\\}$

###### Proof.

Without loss of generality, we prove this result for $p=2$. The proof for
$p>2$ is similar. First, we prove that

$\displaystyle\mathbf{P}(\bigcup_{j=1}^{\infty}\\{p_{1}(x_{1})\geq\frac{1}{j}\\})=1,$
(A9)

where $p_{1}$ is the marginal distribution of $x_{1}$. This is because

$\displaystyle\mathbf{P}(\bigcup_{j=1}^{\infty}\\{p_{1}(x_{1})\geq\frac{1}{j}\\}\bigcup\\{p_{1}(x_{1})=0\\})=1,$
(A10)

while $\mathbf{P}(p_{1}(x_{1})=0)=0$. Then by applying Lemma 1 to
$p_{1}(x_{1})$, we have

$\displaystyle\lim_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{\infty}\\{p_{1}(x_{1})\geq\frac{1}{j}\\})=\lim_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\in
G)=\frac{1}{2}.$ (A11)

Since the sequence $\\{\
\bigcup_{j=1}^{N}\\{p_{1}(x_{1})\geq\frac{1}{j}\\},N=1,2,\cdots\\}$
monotonically increases and converges to
$\bigcup_{j=1}^{\infty}\\{p_{1}(x_{1})\geq\frac{1}{j}\\}$, we have

$\displaystyle\mathbf{P}(\bigcup_{j=1}^{N}\\{p_{1}(x_{1})\geq\frac{1}{j}\\})\to\mathbf{P}(\bigcup_{j=1}^{\infty}\\{p_{1}(x_{1})\geq\frac{1}{j}\\})=1,as\
N\to\infty.$ (A12)

Therefore, for any $\delta>0$,there exists $M_{0}$ and $N_{0}$, such that when
$m>M_{0}$,

$\displaystyle\mathbf{P}(x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\})\geq\frac{1}{2}-\delta.$
(A13)

We further have

$\displaystyle\begin{split}&\mathbf{P}(x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\},x_{2}-i(x_{2})\in
G)\\\ =&\int_{x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\}}p_{1}(x_{1})dx_{1}\int_{x_{2}-i(x_{2})\in
G}p_{2}(x_{2}|x_{1})dx_{2}.\end{split}$ (A14)

We can check for $\forall x_{2}^{{}^{\prime}},x_{2}^{{}^{\prime\prime}}$ and
$x_{1}$ such that $p(x_{1})\geq\frac{1}{N_{0}}$,

$\displaystyle|p_{2}(x_{2}^{{}^{\prime}}|x_{1})-p_{2}(x_{2}^{{}^{\prime\prime}}|x_{1})|=|\frac{p(x_{1},x_{2}^{{}^{\prime}})-p(x_{1},x_{2}^{{}^{\prime\prime}})}{p_{1}(x_{1})}|\leq
N_{0}|p(x_{1},x_{2}^{{}^{\prime}})-p(x_{1},x_{2}^{{}^{\prime\prime}})|.$ (A15)

By the result that a continuous function in a compact set is uniformly
continuous, there exists a $M_{1}$, such that
$|p(x_{1},x_{2}^{{}^{\prime}})-p(x_{1},x_{2}^{{}^{\prime\prime}})|\leq\frac{\delta}{2N_{0}R}$,
$\forall(x_{1},x_{2}^{{}^{\prime}}),(x_{1},x_{2}^{{}^{\prime\prime}})\in
B(0,R)$ and
$|x_{2}^{{}^{\prime}}-x_{2}^{{}^{\prime\prime}}|\leq\frac{1}{M_{1}}$.
Consequently, using the similar arguments as in Section B.3, if $m\geq
2M_{1}$,

$\displaystyle|\int_{x_{2}-i(x_{2})\in
G}p_{2}(x_{2}|x_{1})dx_{2}-\int_{x_{2}-i(x_{2})\notin
G}p_{2}(x_{2}|x_{1})dx_{2}|$
$\displaystyle\leq\max_{|a-b|\leq\frac{1}{M_{1}}}|p_{2}(a|x_{1})-p_{2}(b|x_{1})|\times
2R$ (A16) $\displaystyle\leq N_{0}\frac{\delta}{2N_{0}R}\times 2R$
$\displaystyle\leq\delta,$

which implies

$\displaystyle\int_{x_{2}-i(x_{2})\in
G}p_{2}(x_{2}|x_{1})dx_{2}\geq\frac{1}{2}-\frac{\delta}{2},$ (A17)

$\forall x_{1}$ such that $p_{1}(x_{1})\geq\frac{1}{N_{0}}$. Therefore

$\displaystyle\begin{split}&\mathbf{P}(x_{1}-i(x_{1})\in G,x_{2}-i(x_{2})\in
G)\\\ \geq&\mathbf{P}(x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\},x_{2}-i(x_{2})\in
G)\\\ =&\int_{x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\}}p_{1}(x_{1})dx_{1}\int_{x_{2}-i(x_{2})\in
G}p_{2}(x_{2}|x_{1})dx_{2}\\\ \geq&\int_{x_{1}-i(x_{1})\in
G\bigcap\bigcup_{j=1}^{N_{0}}\\{p_{1}(x_{1})\geq\frac{1}{j}\\}}p_{1}(x_{1})dx_{1}(\frac{1}{2}-\frac{\delta}{2})\\\
\geq&(\frac{1}{2}-\delta)(\frac{1}{2}-\frac{\delta}{2})\geq\frac{1}{4}-\delta\end{split}$
(A18)

given that $\delta<\frac{1}{2}$ when $m>\max\\{M_{0},M_{1}\\}$. Since we could
choose $\delta$ arbitrarily, we have

$\displaystyle\liminf_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\in
G,x_{2}-i(x_{2})\in G)\geq\frac{1}{4},$ (A19)

similarly, we have

$\displaystyle\liminf_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\in
G,x_{2}-i(x_{2})\notin G)\geq\frac{1}{4},$ (A20)
$\displaystyle\liminf_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\notin
G,x_{2}-i(x_{2})\in G)\geq\frac{1}{4},$ (A21)
$\displaystyle\liminf_{m\to\infty}\mathbf{P}(x_{1}-i(x_{1})\notin
G,x_{2}-i(x_{2})\notin G)\geq\frac{1}{4}.$ (A22)

However, the sum of (A19) to (A22) is 1. This implies that the limitations in
(A19) to (A22) are all $\frac{1}{4}$, which finishes the proof. ∎

Now we are ready to prove Theorem 2.

###### Proof.

$\displaystyle\mathbf{P}(\bigcap_{k=1}^{p}A_{k})$
$\displaystyle=\mathbf{P}(\|x\|_{2}\leq
R)\mathbf{P}(\bigcap_{k=1}^{p}A_{k}|\|x\|_{2}\leq
R)+\mathbf{P}(\|x\|_{2}>R)\mathbf{P}(\bigcap_{k=1}^{p}A_{k}||\|x\|_{2}>R).$
(A23)

We can choose $R$ such that

$\displaystyle|\mathbf{P}(\|x\|_{2}\leq R)-1|<\epsilon.$ (A24)

Also by Lemma 2, there exists $M$, such that when $m>M$,

$\displaystyle|\mathbf{P}(\bigcap_{k=1}^{p}A_{k}|\|x\|_{2}\leq
R)-\frac{1}{2}|<\epsilon.$ (A25)

Therefore when $m>M$,

$\displaystyle|\mathbf{P}(\bigcap_{k=1}^{p}A_{k})-\frac{1}{2}|$
$\displaystyle\leq|\mathbf{P}(\|x\|_{2}\leq
R)||\mathbf{P}(\bigcap_{k=1}^{p}A_{k}|\|x\|_{2}\leq
R)-\frac{1}{2}|+\mathbf{P}(\|x\|_{2}>R)(1-\frac{1}{2})$ (A26)
$\displaystyle\leq\epsilon+\frac{1}{2}\epsilon<2\epsilon.$

Since $\epsilon$ is arbitrary, we know that the convergence holds. ∎

###  B.5 Proof of Theorem 3

To prove this result, we consider a lemma from [29].

######  Lemma 3.

(c.f. Theorem 1.1 in [29]) Let $\mathbf{y}_{1},\ldots,\mathbf{y}_{n}$ be
independent $p$-dimensional random vectors with a common mean
$\mathbf{E}\mathbf{y}_{j}=0$. Write
$S_{Y}=\mathbf{y}_{1}+\cdots+\mathbf{y}_{n}$. Throughout we assume that
$S_{Y}$ has a nondegenerated distribution in the sense that the covariance
operator, say $C^{2}=\operatorname{Cov}S_{Y}$, is invertible ( $C$ stands for
the positive root of $\left.C^{2}\right)$. Let $Z$ be a Gaussian random vector
such that $\mathrm{E}Z=0$ and $\operatorname{Cov}S_{Y}$ and
$\operatorname{Cov}Z$ are equal. Write

$\beta=\beta_{1}+\cdots+\beta_{n},\quad\beta_{k}=\mathbf{E}\left|C^{-1}\mathbf{y}_{k}\right|_{2}^{3},$

and

$\Delta(\mathcal{C})=\sup_{A\in\mathcal{C}}|\mathbf{P}\\{S_{Y}\in
A\\}-\mathbf{P}\\{Z\in A\\}|$

where $\mathcal{C}$ stands for the class of all convex subsets of
$\mathbf{R}^{p}$. Then there exists an absolute positive constant $c$, such
that

$\Delta(\mathcal{C})\leq cp^{1/4}\beta$

Now we are ready to prove Theorem 3.

###### Proof.

Note that

$\displaystyle(T_{1}-\frac{n}{2},T_{2}-\frac{n}{2},\cdots,T_{p}-\frac{n}{2})\overset{d}{=}\sum_{j=1}^{n}\mathbf{y}_{j},$
(A27)

where $\\{\mathbf{y}_{j},j=1,2,\cdots n\\}$ are i.i.d. random vectors, with
each of them having independent components with mean $0$ and variance
$\frac{1}{4}$. Then using the same notations as in Lemma 3 and the
monotonicity of $l_{p}$ norm,

$\displaystyle\beta_{k}=\mathbf{E}\left|C^{-1}\mathbf{y}_{k}\right|_{2}^{3}\leq\left\\{\mathbf{E}\left|C^{-1}\mathbf{y}_{k}\right|_{2}^{2}\right\\}^{\frac{3}{2}}=8p^{\frac{3}{2}}\frac{1}{n^{\frac{3}{2}}},$
(A28)

and

$\displaystyle\beta=\sum_{j=1}^{n}\beta_{j}\leq
8\frac{p^{\frac{3}{2}}}{n^{\frac{1}{2}}},$ (A29)

therefore

$\displaystyle\Delta(\mathcal{C})=\sup_{A\in\mathcal{C}}|\mathbf{P}\\{S_{Y}\in
A\\}-\mathbf{P}\\{Z\in A\\}|\leq 8c\frac{p^{\frac{7}{4}}}{n^{\frac{1}{2}}},$
(A30)

which implies if $p=o(n^{\frac{2}{7}})$, $\Delta(\mathcal{C})\to 0$ as
$n\to\infty$. Note that $\mathcal{C}$ stands for the class of all convex
subsets of $\mathbf{R}^{p}$, we further have

$\displaystyle\sup_{r\geq 0}|\mathbf{P}\\{\|2{n}^{-\frac{1}{2}}S_{Y}\|_{2}\leq
r\\}-\mathbf{P}\\{\|2{n}^{-\frac{1}{2}}Z\|_{2}\leq r\\}|\to 0,$ (A31)

which further implies

$\displaystyle\sup_{r\geq
0}|\mathbf{P}\\{\|2{n}^{-\frac{1}{2}}S_{Y}\|^{2}_{2}\leq
r\\}-\mathbf{P}\\{\|2{n}^{-\frac{1}{2}}Z\|^{2}_{2}\leq r\\}|\to 0,$ (A32)

note that
$\|2{n}^{-\frac{1}{2}}S_{Y}\|^{2}_{2}=\sum_{j=1}^{p}\left[2\sqrt{n}\left(\frac{T_{j}}{n}-\frac{1}{2}\right)\right]^{2}$
and $\|2{n}^{-\frac{1}{2}}Z\|^{2}_{2}\sim\chi^{2}_{p}$, we finish the proof. ∎

###  B.6 Proof of Theorem 5

###### Proof.

Without loss of generality, we assume that the probability $x_{ij}$ is
attacked successfully is $\frac{1}{2}$, $\forall i,j$, we use $k_{i}$ to
denote the number of elements moved out of the green list in $ith$ column,
then according to Hoeffding’s inequality (c.f. Theorem 2.2.6 in [30]),

$\displaystyle\mathbf{P}(\sum_{j=1}^{p}k_{j}\leq(1+\delta)(\frac{1}{2}\sum_{j=1}^{p}\widehat{k}_{j}))\geq
1-e^{-\frac{2\delta^{2}(\sum_{j=1}^{p}\frac{1}{2}\widehat{k}_{j})^{2}}{\sum_{j=1}^{p}\widehat{k}_{j}}}=1-e^{-\frac{1}{2}\delta^{2}\sum_{j=1}^{p}\widehat{k}_{j}},$
(A33)

$\forall\delta>0$. Take $\delta=\frac{1}{{(np)}^{\frac{1}{4}}}$, we will have
as long as

$\displaystyle\sum_{j=1}^{p}\widehat{k}_{j}\leq\frac{1}{1+\frac{1}{(np)^{\frac{1}{4}}}}(np-\sqrt{np}\sqrt{\mathcal{X}_{p}^{2}(1-\alpha)}),$
(A34)

with a probability at least

$\displaystyle
1-e^{-\frac{1}{2}(\sqrt{np}-\sqrt{\mathcal{X}_{p}^{2}(1-\alpha)})},$ (A35)

we have

$\displaystyle\sum_{j=1}^{p}k_{j}\leq\frac{1}{2}(np-\sqrt{np}\sqrt{\mathcal{X}_{p}^{2}(1-\alpha)}),$
(A36)

and therefore the attack fails. ∎

##  Appendix C Python-Style Pseudo-Code

We provide python-style pseudocode to facilitate understanding of the proposed
watermark. During testing, one can count the number of elements in the $j$-th
column falling inside the “green list” intervals as $t_{j}$, and perform
binomial or chi-square hypothesis-testing.

Listing 1: Tabular data watermark.

⬇

import numpy as np

def getGreenList(lo=0, hi=1, m=1000):

"""␣return␣a␣list␣of␣tuple,␣representing␣the␣green␣list␣intervals

␣␣␣␣"""

waymarks = np.linspace(lo, hi, m + 1)

green_list = []

for i in range(0, m, 2):

# randomly select one interval from each pair

if np.random.uniform() > .5:

i += 1

green_list.append([waymarks[i], waymarks[i + 1]])

return green_list

"""

␣␣␣␣Watermarking␣a␣p-column␣table:

␣␣␣␣step␣1:␣generate␣p␣green␣lists

␣␣␣␣step␣2:␣for␣each␣column,␣call

␣␣␣␣␣␣␣␣␣␣␣␣‘singleColumnWatermark(arr,␣green_list)‘

␣␣␣␣␣␣␣␣␣␣␣␣to␣watermark␣the␣column␣vector.

"""

def singleColumnWatermark(arr, green_list):

arr_wm = arr.copy()

for i in range(arr_wm):

# offset elem to [0, 1]

e_flr = np.floor(arr_wm[i])

e = arr_wm[i] - e_flr

# find the nearest interval in the “green list” intervals

g = findNearestInterval(e, green_list)

if e > g[1] or e < g[0]:

# if x[i] falls outside of the range, then

# we re-sample the elem. from a uniform dist.

arr_wm[i] = np.random.uniform(g[0], g[1]) + e_flr

return arr_wm

Listing 2: Finding nearest interval with O(1) complexity.

⬇

def findNearestInterval(e, green_list, m):

"""␣return␣the␣nearest␣interval␣to␣the␣given␣element␣e

␣␣␣␣"""

min_dist, min_indx = np.inf, -1

# offset elem to [0, 1]

e = e - np.floor(e)

# find the nearest pair of intervals

idx_c = int(e // (2 / m))

# neighboring indices

idx_l0, idx_r0 = max(0, idx_c - 1), \

min(idx_c + 1, len(green_list) - 1)

idx_l1, idx_r1 = max(0, idx_c - 2), \

min(idx_c + 2, len(green_list) - 1)

# local green lists with possible candidates

# including the closest interval

local_g_list = [green_list[idx_l1], green_list[idx_l0],

green_list[idx_c], green_list[idx_r0],

green_list[idx_r1]]

for i, intv in enumerate(local_g_list):

cur_dist = np.abs(e - (intv[0] + intv[1]) / 2)

if cur_dist < min_dist:

min_dist = cur_dist

min_indx = i

return local_g_list[min_indx]

##  Appendix D Experiment Settings

###  D.1 Synthetic Datasets

For synthetic datasets, we set $m=1000$, which we find sufficient for all the
experiments. For watermark detection without additive noise attacks, we vary
the row and column number of the tabular data within the range
$\\{10,100,1000\\}$, resulting in tables of sizes within the range of
$\\{10,100,1000\\}\times\\{10,100,1000\\}$. For each set-up of the tabular
data size, we create $1000$ watermarked and unwatermarked tables to calculate
the detection rate (true positive rate) and specificity (true negative rate)
with the significance level of $\alpha=.005$; the tabular data is from
standard zero-mean multivariate Gaussian distribution. The specificity in all
settings remain 1. We repeat the experiments for 3 independent runs to
calculate the error bars in LABEL:subfig:chi_sing_col and
LABEL:subfig:chi_mult_col.

For watermark detection with additive noise attacks, we set the tabular data
size as $5000\times 100$ as a representative and vary the variance of additive
zero-mean Gaussian noise within the range $\\{0.001,0.01,0.1,1,10\\}$. To
verify our results in Theorem 5, we vary the proportion of elements in the
table being modified prp within the range $\\{0.50,0.75,0.90,0.95\\}$.
Similarly, we create $1000$ watermarked and unwatermarked tables to calculate
the detection rate (true positive rate) and specificity (true negative rate)
with $\alpha=.005$. The specificity in all settings remain 1. We repeat the
experiments for 3 independent runs to calculate the error bars in
LABEL:subfig:chi_sing_col_atck and LABEL:subfig:chi_mult_col_atck.

###  D.2 Real-World Datasets

#### Dataset

The full list of datasets and their properties are presented in Table A1.

Table A1: List of datasets used for the evaluation and their descriptions. Alias | Name | #Train | #Validation | #Test | #Num | #Cat | Task type
---|---|---|---|---|---|---|---
California | California Housing | 13209 | 3303 | 4128 | 8 | 0 | Regression
Gesture | Gesture Phase | 6318 | 1580 | 1975 | 32 | 0 | Multiclass
House | House 16H | 14581 | 3646 | 4557 | 16 | 0 | Regression
Wilt | Wilt | 3096 | 775 | 968 | 5 | 0 | Binclass
Higg-small | Higgs Small | 62751 | 15688 | 19610 | 28 | 0 | Binclass
Miniboone | MiniBooNE | 83240 | 20811 | 26013 | 50 | 0 | Binclass

#### Evaluation measure

To investigate the performance of our tabular watermark on real-world data, we
sample from each generative model a generated dataset with the size of a real
training set as in Table A1. For each set-up in evaluating fidelity, accuracy
and robustness, we create $50$ watermarked and unwatermarked training sets
(_i.e_., $n\times p$ tables) to measure the wasserstein distance and ROC-AUC
scores. For utility evaluation, we create $50$ watermarked and unwatermarked
training sets to train CatBoost models [20] for classification and regression
tasks, which are then evaluated on the real testing sets. In our experiments,
classification performances are evaluated by the F1 score, and regression
performance is evaluated by the R2 score.

#### Tunning process of tab. generators

We follow [15] and use the Optuna library [31] to tune the hyperparameters of
the tabular data generators. The tuning process is guided by the values of the
ML efficiency (with respect to Catboost) of the generated synthetic data on a
hold-out validation dataset (the score is averaged over five different
sampling seeds). We refer to [15] for search spaces for all hyperparameters of
the tab. generators. We run the experiments on a A6000 GPU. Training and
evaluation process typically finishes within 24 hrs.

##  Appendix E Additional Experiment Results

#### Additional results on simulated tables

We additionally provide the ROC-AUC scores on simulated results for
watermarking a single column corresponding with LABEL:subfig:chi_sing_col in
Table A2. The ROC-AUC scores for watermarking all columns are 1.

Table A2: Detection results on watermarking a single column in simulated tables. $n\times p$ | $10\times 10$ | $10\times 100$ | $10\times 1000$
---|---|---|---
AUC | $0.850$ | $0.700$ | $0.580$
$n\times p$ | $100\times 10$ | $100\times 100$ | $100\times 1000$
AUC | $1.000$ | $1.000$ | $0.970$
$n\times p$ | $1000\times 10$ | $1000\times 100$ | $1000\times 1000$
AUC | $1.000$ | $1.000$ | $1.000$

#### Results on simulated high-dim. tables

We provide simulation results on high dimensional tables, where the number of
columns $p$ exceeds the row numbers $n$ in Table A3. The tabular data is from
standard Gaussian. We observe similar results with tabular data from
5-component randomly initialized gaussian mixture models, which mimic
multimodal distributions.

Table A3: Detection results on simulated high dimensional tables. We report the true postive (TPR) and true negative rates (TNR) as well as ROC-AUC scores. We create $100$ watermarked and unwatermarked tables to calculate the scores. $n\times p$ | $100\times 100$ | $100\times 1000$ | $100\times 10000$
---|---|---|---
TPR/TNR | $1.000/1.000$ | $1.000/1.000$ | $1.000/1.000$
AUC | $1.000$ | $1.000$ | $1.000$

#### Additional results on simulated attacks

We additionally provide the ROC-AUC scores after simulated attacks
corresponding with watermarking a single column
(LABEL:subfig:chi_sing_col_atck) in Table A4. The ROC-AUC scores corresponding
with watermarking all columns are 1.

Table A4: Detection results after attacks on watermarking a single column in simulated tables. s represents the variances of additive noises; p represents the proportions of elements being modified by the attacks. | $s=0.001$ | $s=0.1$ | $s=1$ | $s=10$
---|---|---|---|---
$p=0.50$ | $1.000$ | $1.000$ | $1.000$ | $1.000$
$p=0.75$ | $1.000$ | $1.000$ | $1.000$ | $1.000$
$p=0.90$ | $1.000$ | $0.970$ | $0.990$ | $0.870$
$p=0.95$ | $1.000$ | $0.780$ | $0.850$ | $0.690$

#### Results on Column Selection

We provide number of columns selected in Table A5 for each generated dataset
before and after applying our heuristic smoothness check method.

Table A5: Number of columns selected for each generated dataset. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
TVAE | 8/8 | 32/32 | 16/16 | 5/5 | 24/28 | 50/50
CTABGAN | 8/8 | 32/32 | 16/16 | 5/5 | 24/28 | 50/50
TabDDPM | 5/8 | 32/32 | 7/16 | 5/5 | 24/28 | 27/50

#### Additional results on data fidelity

We provide additional results of data fidelity for TVAE and CTABGAN, shown in
Tables A6 and A7.

Table A6: Wasserstein-1 distance between TVAE generated data and watermarked data distributions. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
Orig2Gen | 0.1327 | 0.1198 | 0.0658 | 0.0906 | 0.1797 | 0.6720
Gen2Watermarked | 0.0004 | 0.0004 | 0.0004 | 0.0003 | 0.0003 | 0.0004
$m$ | 1000 | 1000 | 1000 | 1000 | 1000 | 1000
$1/m$ | 0.001 | 0.001 | 0.001 | 0.001 | 0.001 | 0.001
Table A7: Wasserstein-1 distance between CTABGAN generated data and watermarked data distributions. | California | Gesture | House | Wilt | Higgs-small | Miniboone
---|---|---|---|---|---|---
Orig2Gen | 0.1683 | 0.1771 | 0.0926 | 0.1003 | 0.0606 | 0.6471
Gen2Watermarked | 0.0004 | 0.0004 | 0.0004 | 0.0004 | 0.0004 | 0.0004
$m$ | 1000 | 1000 | 1000 | 1000 | 1000 | 2500
$1/m$ | 0.001 | 0.001 | 0.001 | 0.001 | 0.001 | 0.0004

#### Examples of ill-shaped column data distributions

We provide examples of ill-shaped column distributions in Fig. 4. We can see
these distributions have spikes concentrated on certain values (especially in
the left subfig), with undesirable smoothness violating our assumption in
Lemma 1.

Figure A0: Histogram of spiky column data distributions. Examples generated by
TabDDPM.

##  Appendix F Limitations and Future work

One potential limitation of our framework is that it primarily addresses
continuous variables, leaving the watermarking of discrete variables as an
area for future exploration. It would be worthwhile to investigate whether a
similar technique involving “green list” and “red list” intervals can be
effectively applied to discrete variables. Additionally, the specific choice
of $m$ (the number of “green list” intervals) is closely tied to the
smoothness of the data distribution. For instance, if the distribution under
the null hypothesis is not smooth and exhibits characteristics such as spikes,
a larger $m$ would be necessary to ensure that the probability of a sample
point falling within a “green list” interval approaches $\frac{1}{2}$. These
aspects highlight the need for further refinement and adaptation of our
framework to accommodate a broader range of data types and distributional
properties.

##  Appendix G Broader Impacts

This work contributes to enhancing the security of both synthetic and real-
world datasets, which is critical in the context of AI and machine learning
applications. Specifically, generative models could be misused for
disinformation or faking profiles. Our work focuses on watermarking generative
data, which can facilitate the reliable detection of synthetic content, and
could be important to address such harms from generative models. We consider
our work to be foundational and not tied to particular applications or
deployments. It is possible that future works may involve malicious uses of
this technique that we are unaware of for now.


# Bubble Universe from Flat Spaces

Eduardo Guendelman<EMAIL_ADDRESS>Department of Physics, Ben-Gurion
University of the Negev, Beer-Sheva, Israel
Frankfurt Institute for Advanced Studies, Giersch Science Center, Campus
Riedberg, Frankfurt am Main, Germany
Bahamas Advanced Studies Institute and Conferences, 4A Ocean Heights, Hill
View Circle, Stella Maris, Long Island, The Bahamas  Jacov Portnoy
<EMAIL_ADDRESS>Bahamas Advanced Studies Institute and Conferences, 4A
Ocean Heights, Hill View Circle, Stella Maris, Long Island, The Bahamas
<EMAIL_ADDRESS>Department of Physics, Ben-Gurion University of the Negev,
Beer-Sheva, Israel.
Frankfurt Institute for Advanced Studies (FIAS), Ruth-Moufang-Strasse 1, 60438
Frankfurt am Main, Germany.
Bahamas Advanced Study Institute and Conferences, 4A Ocean Heights, Hill View
Circle, Stella Maris, Long Island, The Bahamas.

###### Abstract

We show by matching two flat spaces one in Minkowski coordinates ( empty
space) and the other in Minkowski coordinates after a special conformal
transformation (also empty space) through a bubble with positive and constant
surface tension, that the motion of the bubble is hyperbolic. If the surface
tension is very big the initial size of the bubble is as small as we wish, so
that we can indeed obtain an infinite universe out of empty spaces. The
induced space in the bubble is de Sitter type.

##  I Introduction

There are many interesting situations where space time is flat everywhere,
except for some lines or surfaces, may be the most famous example being the
cosmic string Cosmic Strings , where space is flat everywhere except on a
line, the string, where a conical singularity resides.

Naturally one may ask if instead of a line, we may have a surface matching two
flat spaces, expressed nevertheless in different coordinate systems. This
seems interesting and fundamental because it may shed light into the vacuum
structure of the theory, and finding novel ways to connect different vacuum
states. The resulting solutions also hint to new ways to generate universes
from nothing when continued to euclidean space.

We will study here the matching of Flat Minkowski space and Flat Minkowski
space after a special conformal Transformation and then compare with results
obtained from considerations of string matter and of braneworlds in the
context of string theories with dynamical tension.

##  II Flat Minkowski space and Flat Minkowski space after a special conformal
Transformation

The flat spacetime in Minkowski coordinates is,

$ds_{1}^{2}=\eta_{\alpha\beta}dx^{\alpha}dx^{\beta}$ (1)

where $\eta_{\alpha\beta}$ is the standard Minkowski metric, with
$\eta_{00}=1$, $\eta_{0i}=0$ and $\eta_{ij}=-\delta_{ij}$. This is of course a
solution of the vacuum Einstein´s equations.

We now consider the conformally transformed metric

$ds_{2}^{2}=\Omega(x)^{2}\eta_{\alpha\beta}dx^{\alpha}dx^{\beta}$ (2)

where the conformal factor coincides with that obtained from the special
conformal transformation

$x\prime^{\mu}=\frac{(x^{\mu}+a^{\mu}x^{2})}{(1+2a_{\nu}x^{\nu}+a^{2}x^{2})}$
(3)

for a certain D vector $a_{\nu}$. which gives
$\Omega^{2}=\frac{1}{(1+2a_{\mu}x^{\mu}+a^{2}x^{2})^{2}}$ In summary, we have
two solutions for the Einstein´s equations,
$g^{1}_{\alpha\beta}=\eta_{\alpha\beta}$ and

$g^{2}_{\alpha\beta}=\Omega^{2}\eta_{\alpha\beta}=\frac{1}{(1+2a_{\mu}x^{\mu}+a^{2}x^{2})^{2}}\eta_{\alpha\beta}$
(4)

These two spaces can be matched at the surfaces where $\Omega^{2}=1$, where
$\Omega^{2}=\frac{1}{(1+2a_{\mu}x^{\mu}+a^{2}x^{2})^{2}}$. We will consider
the cases where $a^{2}\neq 0$. Let us by consider the case where $a^{\mu}$ is
time like (for $a^{\mu}$ spacelike similar results are obtained), then without
loosing generality we can take $a^{\mu}=(A,0,0,...,0)$. The two solutions of
$\Omega^{2}=1$ are , considering the cases $\Omega=1$ and $\Omega=-1$ ,

$2a_{\mu}x^{\mu}+a^{2}x^{2}=0$ (5)

and

$2+2a_{\mu}x^{\mu}+a^{2}x^{2}=0$ (6)

Then for $a^{\mu}=(A,0,0,...,0)$, the above condition implies that,

$(2a_{\mu}x^{\mu}+a^{2}x^{2})(2+2a_{\mu}x^{\mu}+a^{2}x^{2})=(2At+A^{2}(t^{2}-x^{2}))(2+2At+A^{2}(t^{2}-x^{2}))$
(7)

This condition, if $A\neq 0$ implies then the more specific condition,

$x^{2}_{1}+x^{2}_{2}+x^{2}_{3}.....+x^{2}_{D-1}-(t+\frac{1}{A})^{2}=-\frac{1}{A^{2}}$
(8)

bya similar analysis, the other surface that satisfies the conformal
transformation factor is $1$, is given by

$x^{2}_{1}+x^{2}_{2}+x^{2}_{3}.....+x^{2}_{D-1}-(t+\frac{1}{A})^{2}=\frac{1}{A^{2}}$
(9)

since (7) represents a surface that does not exists for all times, and it can
represent propagation with speed greater than light, we will restrict to the
surface (9) which does exist for all times, and represents hyperbolic motion
with time like propagation, in the next section we will look at the surface
tension as given by the Israel matching conditions.

##  III surface tension as given by the Israel matching conditions in four
space-time dimensions

Let us consider now $D=4$, defining $r=\sqrt{x^{2}_{1}+x^{2}_{2}+x^{2}_{3}}$,
then, taking the space (4) outside, the standard Israel matching conditions
Israel matching conditions  apply,

$K^{+}_{\theta\theta}-K^{-}_{\theta\theta}=4\pi G\sigma r^{2}$ (10)
$K^{+}_{\theta\theta}=\frac{1}{2}\xi^{\mu}\partial_{\mu}(r^{2}\Omega^{2})$
(11) $K^{-}_{\theta\theta}=\frac{1}{2}\xi^{\mu}\partial_{\mu}(r^{2})$ (12)
$K^{+}_{\theta\theta}-K^{-}_{\theta\theta}=\frac{1}{2}[\xi^{\mu}\partial_{\mu}(r^{2}\Omega^{2})-\xi^{\mu}\partial_{\mu}(r^{2})]\Big{|}_{\Omega^{2}=1}=\frac{1}{2}\xi^{\mu}\Omega^{2}\partial_{\mu}(r^{2})+\frac{1}{2}\xi^{\mu}r^{2}\partial_{\mu}(\Omega^{2})-\frac{1}{2}\xi^{\mu}\partial_{\mu}(r^{2})\Big{|}_{\Omega^{2}=1}$
(13)
$=\frac{1}{2}\xi^{\mu}r^{2}\partial_{\mu}\Omega^{2}\Big{|}_{\Omega^{2}=1}=4\pi
G\sigma r^{2}$ (14)

$\Omega^{2}=\frac{1}{(1+2a_{\mu}x^{\mu}+a^{2}x^{2})^{2}}$ (15)

$\xi_{\mu}=\frac{\partial_{\mu}(\Omega^{2})}{\sqrt{|(\partial_{\mu}(\Omega^{2})(\partial_{\mu}(\Omega^{2})|}}$
(16)
$\sigma=\frac{1}{8\pi}\sqrt{|(\partial_{\mu}(\Omega^{2})(\partial_{\mu}(\Omega^{2})|}$
(17) $\sigma=\frac{|A|}{4\pi}\sqrt{|1+2a^{\mu}x_{\mu}+x^{2}|}$ (18)

and using (5) or (6) we obtain

$\sigma=\frac{|A|}{4\pi}$

Notice however that the surface (8) moves with velocity bigger than light,
while (9) moves with velocity less than light, so, we must choose (9) as the
physical alternative. Using equation $\sigma=\frac{|A|}{4\pi}$ we can express
the motion of the surface separating the two vacuum solutions $\Omega^{2}=1$
in terms of the surface tension,

$x^{2}_{1}+x^{2}_{2}+x^{2}_{3}.-(t+\frac{1}{A})^{2}=\frac{1}{16\pi^{2}\sigma^{2}}$
(19)

so in the limit of very large surface tensions we obtain that the minimum
radius of the bubble becomes very small. This shows similar features with
results in universefromalmostnothing , but here there are stronger, since we
do not just talk about Universes out of almost empty space, but Universes out
of exactly empty space, already at the classical level.

##  IV Euclidean extension and the Quantum Creation of a Baby Universe from
Nothing

The surface $\Omega^{2}=1$, solved according to (9) allows an Euclidean
extension, by defining an Euclidean time $(t_{E}+1/A)=-i(t+1/A)$, which
replaced into $\Omega^{2}=1$ gives the spherical euclidean region

$x^{2}_{1}+x^{2}_{2}+x^{2}_{3}.....+x^{2}_{D-1}+(t_{E}+\frac{1}{A})^{2}=\frac{1}{A^{2}}$
(20)

The euclidean and real time regions defined above of the surface
$\Omega^{2}=1$ can be smoothly matched at $(t_{E}+1/A)=(t+1/A)=0$. The quantum
mechanical interpretation of the euclidean region is the tunneling region that
eventually leads by matching to the creation of the baby universe. The first
surface (8) cannot be extended to Euclidean space and it starts at $t=0$ from
zero size in real space.

##  V Discussion and Conclusions

We have seen that the matching between two patches of flat space, one
described by flat space in standard Minkowski coordinates and the other by
flat space obtained after a special conformal transformation from the standard
Minkowski coordinates. The two spaces can be made to match at the locations
where the conformal transformation equals the identity, which gives two
different possible motions for the surface separating the two spaces, we
choose the solution which is manifestly time like, we can calculate the
surface tension of the wall separating the two spaces and it turns out to be a
constant.

These type of situation, where we consider two flat spaces, one in Minkowski
pace and the other in flat space obtained after a special conformal
transformation from the standard Minkowski coordinates and the surfaces where
the conformal transformation is equal to one plays a special role in the case
of string theories with dynamical tension, and these hypersurfaces are in
higher dimensions in this case, these surfaces appear as surfaces where the
string tensions go to infinity causing an effective braneworld scenario
braneworlds in string theories with dynamical tension . The approach here is a
bit different, we do not rely on any ¨microscopic¨ theory, like string theory
with dynamical tension, and just simply match the two given spacetimes,
obtaining nevertheless very similar situations in this way as well. Notice
that although we have started just from flat spaces, the induced space in the
bubble is a de Sitter type space time.

##  VI Acknowledgements

, We want to thank The Bahamas Advanced Study Institute and Conferences
(BASIC) and Ben Gurion University for support of this project.

## References

  * (1) Cosmic Strings A. Vilenkin, Published in: Phys.Rev.D 24 (1981) 2082-2089
  * (2) Singular hypersurfaces and thin shells in general relativity, W. Israel, Published in: Nuovo Cim.B 44S10 (1966) 1, Nuovo Cim.B 48 (1967) 463 (erratum), Nuovo Cim.B 44 (1966) 1
  * (3) Universes out of almost empty space Stefano Ansoldi, Eduardo I. Guendelman, Published in: Prog.Theor.Phys. 120 (2008) 985-993 • e-Print: 0706.1233 [gr-qc], Almost classical creation of a universe, E.I. Guendelman, J. Portnoy, Published in: Mod.Phys.Lett.A 16 (2001) 1079-1087
  * (4) Light like segment compactification and braneworlds with dynamical string tension Eduardo Guendelman, Published in: Eur.Phys.J.C 81 (2021) 10, 886 • e-Print: 2107.08005 [hep-th], From Homogeneous and Isotropic Universes to Braneworlds with Dynamical Tension Strings, E.I. Guendelman, Published in: Phys.Part.Nucl. 54 (2023) 5, 913-918, Life of the homogeneous and isotropic universe in dynamical string tension theories, E.I. Guendelman, Published in: Eur.Phys.J.C 82 (2022) 10, 857, Relieving string tension by making baby universes in a dynamical string tension braneworld model, Eduardo I. Guendelman, Zeeya Merali, Published in: Int.J.Mod.Phys.D 31 (2022) 14, 2242014 • e-Print: 2205.05261 [hep-th], Brane world creation from flat or almost flat space in dynamical tension string theories, E.I. Guendelman, J. Portnoy, Published in: Eur.Phys.J.C 82 (2022) 4, 336 • e-Print: 2202.10457 [hep-th]