# On the Linear Capacity of Conditional Disclosure of Secrets

Zhou Li and Hua Sun

###### Abstract

Conditional disclosure of secrets (CDS) is the problem of disclosing as
efficiently as possible, one secret from Alice and Bob to Carol if and only if
the inputs at Alice and Bob satisfy some function $f$. The information
theoretic capacity of CDS is the maximum number of bits of the secret that can
be securely disclosed per bit of total communication. All CDS instances, where
the capacity is the highest and is equal to $1/2$, are recently characterized
through a noise and signal alignment approach and are described using a graph
representation of the function $f$. In this work, we go beyond the best case
scenarios and further develop the alignment approach to characterize the
linear capacity of a class of CDS instances to be $(\rho-1)/(2\rho)$, where
$\rho$ is a covering parameter of the graph representation of $f$.

††Zhou Li (email<EMAIL_ADDRESS>and Hua Sun (email<EMAIL_ADDRESS>are
with the Department of Electrical Engineering at the University of North
Texas.

##  1 Introduction

The conditional disclosure of secrets (CDS) problem is a classical
cryptographic primitive with rich connections to many other primitives such as
symmetric private information retrieval [1] and secret sharing [2, 3]. For
more background and applications of CDS, we refer to the introduction section
of [4] and references therein. The goal of the CDS problem is to find the most
efficient way for Alice and Bob to disclose a common secret to Carol if and
only if the inputs at Alice and Bob satisfy some function $f$ (see Fig. 1).
The CDS problem was initially studied in the setting where the secret is one
bit long, and the cost of a CDS scheme is measured by the worst case total
amount of communication over all functions $f$, typically as order functions
of the input size [1, 5, 6, 7, 8, 9]. That is, the focus is on the scaling law
of the communication complexity as the input size grows to infinity. What is
pursued in this work is the traditional Shannon theoretic formulation, where
the secret size is allowed to be arbitrarily large, and the communication rate
is the number of bits of the secret that can be securely disclosed per bit of
total communication. The aim is to characterize the maximum rate, termed the
capacity of CDS, for a fixed function $f$.

Figure 1: 1). Alice and Bob (with secret $S$, noise variable $Z$, respective
inputs $x,y$) wish to disclose the secret $S$ to Carol if and only if
$f(x,y)=1$ for a binary function $f$, through signals $A_{x},B_{y}$. 2) An
example of $f(x,y)$ in graph representation. From pair of nodes connected by a
solid black edge (i.e., $f(x,y)=1$), Carol can decode $S$; from pair of nodes
connected by a dashed red edge (i.e., $f(x,y)=0$), Carol learns nothing about
$S$ in the information theoretic sense.

In [4], we obtain a complete characterization for all functions $f$ where the
CDS capacity is the highest, and is equal to $1/2$. In describing this result,
we find it convenient to represent the function $f$ by a bipartite graph,
where each node denotes a possible signal for certain input and two types
(colors) of edges are used to denote whether $f$ is $1$ or $0$ (see Fig. 1.2).
We will use this graph representation of functions $f$ throughout this work.
The feasibility condition for capacity $1/2$ is then stated in terms of the
graphic properties of $f$. Furthermore, this result is obtained using a novel
noise and signal alignment approach, which guides the proof of both
(information theoretic) impossibility claims and (linear) protocol designs.

Beyond the best rate scenarios, the simplest uncovered case is also considered
in [4] (see Theorem 2), where the linear capacity111It turns out that the
linear capacity, i.e., the highest rate achievable by linear schemes, does not
match the best converse bound produced by only Shannon information
inequalities, i.e., sub-modularity of entropy functions [4]. has been found
and this is our starting point. Our goal in this work is to further develop
the alignment approach to characterize the linear capacity of a larger class
of CDS instances. As our first main result (see Theorem 1), we obtain a
general converse bound for linear CDS schemes, which applies to any CDS
instance, is parameterized by a covering parameter $\rho$ of the graph
representation of $f$, and is equal to $(\rho-1)/(2\rho)$. As our second main
result (see Theorem 2), we show that the above converse bound is achievable
for a class of graphs, i.e., CDS instances, through a vector linear code based
achievable scheme with matching rate. While we find that the converse bound
appears to be achievable for more graphs (by verifying a number of examples),
an explicit condition of a larger class and a universal code design that
applies generally remain elusive. As our final result, we show through an
example that the above converse bound is not tight in general and we establish
the linear capacity for that example (see Theorem 3). Interestingly, all
results are obtained through a more refined view of the alignment approach.

##  2 Problem Statement and Preliminaries

Consider a binary function $f(x,y)$, where $(x,y)$ is from some set
$\mathcal{I}\subset\\{1,2,\cdots,X\\}\times\\{1,2,\cdots,Y\\}$ and its
characteristic undirected bipartite graph $G_{f}=(V,E)$, where the node set
$V=\\{A_{1},\cdots,A_{X}$, $B_{1},\cdots,B_{Y}\\}$ and the edge set $E$ is
comprised of the unordered pairs $\\{A_{x},B_{y}\\}$ such that
$(x,y)\in\mathcal{I}$. The edges have two types: if $f(x,y)=1$,
$\\{A_{x},B_{y}\\}$ is a solid black edge and is referred to as a qualified
edge; if $f(x,y)=0$, $\\{A_{x},B_{y}\\}$ is a dashed red edge and is referred
to as an unqualified edge (see Fig. 1.2 for an example).

The variable $x$ ($y$) denotes the input available only to Alice (Bob) and
$A_{x}$ ($B_{y}$) denotes the signal sent from Alice (Bob) to Carol for
securely disclosing the secret $S$, which is comprised of $L$ i.i.d. uniform
symbols from a finite field $\mathbb{F}_{p}$. In addition to the secret $S$,
Alice and Bob also hold an independent common noise variable $Z$ (to assist
with the secure disclosure task) that is comprised of $L_{Z}$ i.i.d. uniform
symbols from $\mathbb{F}_{p}$. In $p$-ary units,

$\displaystyle H(S)=L,~{}H(Z)=L_{Z},~{}H(S,Z)=H(S)+H(Z)=L+L_{Z}.$ (1)

Each signal $A_{x}$ ($B_{y}$) is assumed to be comprised of $N$ symbols from
$\mathbb{F}_{p}$ and must be determined by information available to Alice
(Bob).

$\displaystyle H(A_{x},B_{y}|S,Z)=0.$ (2)

The disclosure task is said to be successful if the following conditions are
satisfied. From a qualified edge, Carol can recover $S$ with no error; from an
unqualified edge, Carol must learn nothing about $S$. For all
$(x,y)\in\mathcal{I}$, we have

$\displaystyle[\mbox{Correctness}]~{}~{}H(S|A_{x},B_{y})=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}\mbox{if}~{}f(x,y)=1;$
(3)
$\displaystyle[\mbox{Security}]~{}~{}~{}~{}~{}~{}H(S|A_{x},B_{y})=H(S),~{}~{}~{}\mbox{otherwise}~{}f(x,y)=0.$
(4)

The collection of the mappings from $x,y,S,Z$ to $A_{x},B_{y}$ as specified
above is called a CDS scheme.

The CDS rate $R$ characterizes how many symbols of the secret are securely
disclosed per symbol of total communication and is defined as follows.

$\displaystyle R=\frac{L}{2N}.$ (5)

A rate $R$ is said to be achievable if there exists a CDS scheme, for which
the correctness and security constraints (3), (4) are satisfied and the rate
is greater than or equal to $R$. The supremum of achievable rates is called
the capacity of CDS, $C$.

In this work, we focus mainly on the metric of capacity $C$ and allow as much
noise as needed, i.e., the randomness size $L_{Z}$ is unconstrained.

###  2.1 Graph Definitions

We will use some graphic notions of $G_{f}=(V,E)$ to state our results, which
are defined as follows. Without loss of generality, we assume that for any
node $v\in V$, there exists some node $u\in V$ such that $\\{u,v\\}\in E$ is
an unqualified edge (otherwise, for any $v$ that is connected to only
qualified edges, we can set $v$ to be the secret $S$ and then eliminate $v$
and its edges).

######  Definition 1 (Qualified/Unqualified Path/Component)

A sequence of distinct connecting qualified (unqualified) edges is called a
qualified (unqualified) path. A qualified (unqualified) connected component is
a maximal induced subgraph of $G_{f}$ such that any two nodes in the subgraph
are connected by a qualified (unqualified) path.

For example, in Fig. 1.2,
$P=\left\\{\\{A_{1},B_{2}\\},\\{B_{2},A_{3}\\},\\{A_{3},B_{1}\\}\right\\}$ is
an unqualified path; as the graph is connected, it is a qualified component.

######  Definition 2 (Internal Qualified Edge)

A qualified edge that connects two nodes in an unqualified path is called an
internal qualified edge.

For example, in Fig. 1.2, the edge $e=\\{A_{1},B_{1}\\}$ is an internal
qualified edge that connects the two nodes $A_{1},B_{1}$ in the unqualified
path
$P=\left\\{\\{A_{1},B_{2}\\},\\{B_{2},A_{3}\\},\\{A_{3},B_{1}\\}\right\\}$.

######  Definition 3 (Connected Edge Cover)

Consider an internal qualified edge $e$ in an unqualified path $P$ and the
node set of $P$ is denoted as $V_{P}\subset V$. A connected edge cover of
$V_{P}$ is a set of connected222That is, any two nodes in $M$ are connected by
a qualified path. qualified edges $M\subset E$ such that each node in $V_{P}$
is covered by at least one qualified edge in $M$ and $e\in M$. The size of a
connected edge cover for $(e,P)$ is the number of edges in $M$ and is denoted
as $\rho(e,P)$. If no such $M$ exists, then $\rho(e,P)$ is defined as
$+\infty$. Further, $\rho\triangleq\min_{e,P}\rho(e,P)$.

For example, in Fig. 1.2, consider the internal qualified edge
$e=\\{A_{1},B_{1}\\}$ in the unqualified path
$P=\left\\{\\{A_{1},B_{2}\\},\\{B_{2},A_{3}\\},\\{A_{3},B_{1}\\}\right\\}$,
then the nodes in $P$ are $V_{P}=\\{A_{1},B_{2},A_{3},B_{1}\\}$ and a
connected edge cover of $V_{P}$ is
$M=\\{\\{A_{4},B_{1}\\},\\{A_{4},B_{2}\\},\\{A_{4},B_{3}\\},\\{A_{1},B_{1}\\},\\{A_{3},B_{3}\\}\\}$.
In this case, $\rho(e,P)=5$ as $M$ contains $5$ edges and we can verify that
the minimum value of $\rho(e,P)$ over all internal qualified edges and their
associated unqualified path pairs $(e,P)$ is $\rho=5$.

It can be verified that in general, $\rho$ can be any integer that is at least
$5$. Also note that as $\rho$ is defined to be the minimum over all $e,P$, so
the connected edge cover $M$ that attains the value of $\rho$ corresponds to
one that has the minimal cardinality.

###  2.2 Linear Feasibility

We characterize the feasibility condition of a linear CDS scheme.

Linear Scheme: For a feasible linear CDS scheme, each signal (equivalently,
each node $v\in V$)

$\displaystyle v={\bf F}_{v}S+{\bf H}_{v}Z,~{}{\bf
F}_{v}\in\mathbb{F}_{p}^{N\times L},{\bf H}_{v}\in\mathbb{F}_{p}^{N\times
L_{Z}}$ (6)

is specified by two precoding matrices, ${\bf F}_{v}$ for the secret
$S\in\mathbb{F}_{p}^{L\times 1}$ and ${\bf H}_{v}$ for333Without loss of
generality, we assume that ${\bf H}_{v}$ has full row rank, i.e.,
$\mbox{rank}({\bf H}_{v})=N$, because each $v$ is assumed to connect to at
least an unqualified edge so that $I(v;S)=0$, then the linearly dependent rows
of ${\bf H}_{v}$ in $v$ must be linearly dependent as well (thus redundant).
the noise $Z\in\mathbb{F}_{p}^{L_{Z}\times 1}$ such that the following
properties are satisfied.

  * •

Consider any edge $\\{v,u\\}$ and identify the overlap of their noise spaces,
i.e., the row space of ${\bf H}_{v}$ and ${\bf H}_{u}$. That is, find matrices
${\bf P}_{v}$ and ${\bf P}_{u}$ such that

$\displaystyle{\bf P}_{v}{\bf H}_{v}$ $\displaystyle=$ $\displaystyle{\bf
P}_{u}{\bf H}_{u},$ $\displaystyle\mbox{rank}({\bf P}_{v})$ $\displaystyle=$
$\displaystyle\mbox{rank}({\bf P}_{u})=\mbox{dim}(\mbox{rowspan}({\bf
H}_{v})\cap\mbox{rowspan}({\bf H}_{u})),$ (7)

then the secret spaces satisfy

$\displaystyle[\mbox{Correctness}]~{}~{}\mbox{rank}({\bf P}_{v}{\bf
F}_{v}-{\bf P}_{u}{\bf F}_{u})=L,~{}~{}~{}\mbox{if $\\{u,v\\}$ is qualified};$
(8) $\displaystyle[\mbox{Security}]~{}~{}~{}~{}~{}~{}{\bf P}_{v}{\bf
F}_{v}={\bf P}_{u}{\bf
F}_{u},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mbox{otherwise
$\\{u,v\\}$ is unqualified}.$ (9)

The correctness constraint (8) and the security constraint (9) for linear
schemes imply the entropic versions (3), (4). For correctness, note that ${\bf
P}_{v}v-{\bf P}_{u}u=({\bf P}_{v}{\bf F}_{v}-{\bf P}_{u}{\bf F}_{u})S$, so $S$
can be decoded with no error if ${\bf P}_{v}{\bf F}_{v}-{\bf P}_{u}{\bf
F}_{u}$ has full rank. For security, note that ${\bf P}_{v}{\bf H}_{v},{\bf
P}_{u}{\bf H}_{u}$ contains all the overlaps so that the remaining vectors are
orthogonal. That is,

$\displaystyle({\bf H}_{v};{\bf H}_{u})\overset{\mbox{\scriptsize
invertible}}{\longleftrightarrow}({\bf P}_{v}{\bf H}_{v};{\bf Q}_{v}{\bf
H}_{v};{\bf Q}_{u}{\bf H}_{u})$ (10)

where $\mbox{rowspan}({\bf P}_{v}{\bf H}_{v}),~{}\mbox{rowspan}({\bf
Q}_{v}{\bf H}_{v}),~{}\mbox{rowspan}({\bf Q}_{u}{\bf H}_{u})$ are linearly
independent. Then we have

$\displaystyle I(S;v,u)$
$\displaystyle\overset{(\ref{eq:proj})(\ref{eq:sec})}{=}$ $\displaystyle
I(S;{\bf P}_{v}{\bf F}_{v}S+{\bf P}_{v}{\bf H}_{v}Z,{\bf Q}_{v}{\bf
F}_{v}S+{\bf Q}_{v}{\bf H}_{v}Z,{\bf Q}_{u}{\bf F}_{u}S+{\bf Q}_{u}{\bf
H}_{u}Z)$ (12) $\displaystyle\overset{(\ref{sz_ind})}{=}$ $\displaystyle
H({\bf P}_{v}{\bf F}_{v}S+{\bf P}_{v}{\bf H}_{v}Z,{\bf Q}_{v}{\bf F}_{v}S+{\bf
Q}_{v}{\bf H}_{v}Z,{\bf Q}_{u}{\bf F}_{u}S+{\bf Q}_{u}{\bf H}_{u}Z)$
$\displaystyle~{}-H({\bf P}_{v}{\bf H}_{v}Z,{\bf Q}_{v}{\bf H}_{v}Z,{\bf
Q}_{u}{\bf H}_{u}Z)$ $\displaystyle\leq$ $\displaystyle\mbox{rank}({\bf
P}_{v}{\bf H}_{v};{\bf Q}_{v}{\bf H}_{v};{\bf Q}_{u}{\bf
H}_{u})-\mbox{rank}({\bf P}_{v}{\bf H}_{v};{\bf Q}_{v}{\bf H}_{v};{\bf
Q}_{u}{\bf H}_{u})=0$ (13)

where (12) follows from the fact that ${\bf P}_{v}{\bf F}_{v}S+{\bf P}_{v}{\bf
H}_{v}Z={\bf P}_{u}{\bf F}_{u}S+{\bf P}_{u}{\bf H}_{u}Z$ (see (7), (9)) and
linear transformation to identify the overlap is invertible (see (10)). In the
last step, the first term follows from counting the number of variables and
the property that uniform distribution maximizes entropy, and the second term
follows from the fact the symbols in $Z$ are i.i.d. and uniform. Conversely,
any feasible linear scheme must satisfy (8), (9). Such a linear feasibility
framework has appeared in related problems, e.g., index coding [10] and secure
groupcast [11].

To facilitate later use, we summarize some useful properties of feasible
linear schemes in the following lemma. A detailed proof can be found in Lemma
6 and Lemma 7 of [4].

###### Lemma 1

For any linear scheme as defined above and any edge $\\{v,u\\}$, we have

$\displaystyle[\mbox{Noise Alignment}]~{}~{}\mbox{dim}(\mbox{rowspan}({\bf
H}_{v})\cap\mbox{rowspan}({\bf H}_{u}))\geq L,~{}~{}~{}\mbox{if $\\{u,v\\}$ is
qualified};$ (14) $\displaystyle[\mbox{Signal
Alignment}]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\bf P}_{v}{\bf F}_{v}={\bf
P}_{u}{\bf
F}_{u},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mbox{if
$\\{u,v\\}$ is unqualified}.$ (15)

The intuition of the lemma is as follows. (14) follows from the correctness
constraint (8), which requires the overlap of the noise spaces to have at
least $L$ dimensions as decoding is only possible over the overlapping space
(so referred to as ‘noise alignment’) and other spaces are covered by
independent noise variables. (15) follows from the security constraint (9),
which says that over the overlapping noise space, the secret space must also
be fully overlapping (so referred to as ‘signal alignment’ since both noise
and secret fully align in this space) as otherwise the unqualified edge can
reveal some linear combination of the secret symbols, violating the security
constraint.

In the remainder of this paper, we use (8) and (9) to verify the correctness
and security of a linear scheme. To illustrate how it works, let us consider
again the CDS instance in Fig. 1.2 (reproduced in Fig. 2). We show that rate
$R=2/5$ is achievable, through presenting a vector linear scheme with
$L=4,N=5$. That is, the secret has $L=4$ symbols over $\mathbb{F}_{3}$
($S=(s_{1};s_{2};s_{3};s_{4})$), and each signal has $N=5$ symbols over
$\mathbb{F}_{3}$. The assignment of the signals is given in Fig. 2. Suppose
$Z=(z_{1};\cdots;z_{9})$, where each $z_{i}$ is uniform and i.i.d. over
$\mathbb{F}_{3}$.

Figure 2: A CDS instance and the vector linear achievable scheme of rate
$R=2/5$.

Let us verify that the above scheme is correct and secure. For simplicity, we
do not write out explicitly the precoding matrices ${\bf F}_{v}$ and ${\bf
H}_{v}$ for a signal $v$ as the dimension is relatively large. Instead, we
will directly find the overlap by inspection. Consider qualified edge
$\\{A_{3},B_{3}\\}$. $A_{3},B_{3}$ both contain
$(z_{1}+z_{2};z_{4};z_{5};z_{8})$ (noise overlaps) and can then obtain $4$
equations of the secret symbols, $(-s_{1}+s_{2};s_{4};s_{3}+s_{4};s_{1})$,
which can recover $S=(s_{1};s_{2};s_{3};s_{4})$. Other cases of qualified
edges can be verified similarly. Consider the unqualified edge
$\\{A_{3},B_{2}\\}$. $(z_{1}+z_{2};z_{5})$ lies in the overlap of the noise
spaces and the secret symbols projecting to this space are both
$(s_{1}+s_{2};s_{3}+s_{4})$, thus no information is leaked. Other unqualified
edges follow similarly. The rate achieved is thus $L/(2N)=4/10=2/5$.

##  3 Results

Our first result is a general converse bound of linear CDS schemes,
parameterized by the minimum connected edge cover number of internal qualified
edges, $\rho$ and stated in Theorem 1.

###### Theorem 1

For any CDS instance, the following converse bound holds for all linear
schemes.

$\displaystyle R_{\mbox{\scriptsize linear}}\leq\frac{\rho-1}{2\rho}.$ (16)

###### Remark 1

When $\rho=+\infty$, we have that for any internal qualified edge $e$, there
is no set of connected edges that can cover all nodes in the unqualified path
containing $e$ (refer to Definition 3). This is equivalent to that there is no
internal qualified edge within any qualified component, which reduces to the
feasibility condition of capacity $1/2$ from Theorem 1 of [4].

The proof of Theorem 1 is presented in Section 4.

To illustrate the idea, let us consider the CDS instance in Fig. 2. Note that
$e=\\{A_{1},B_{1}\\}$ is an internal qualified edge in unqualified path
$P=\left\\{\\{A_{1},B_{2}\\},\\{B_{2},A_{3}\\},\\{A_{3},B_{1}\\}\right\\}$,
with node set $V_{P}=\\{A_{1},B_{2},A_{3},B_{1}\\}$, where $V_{P}$ is covered
by a connected edge cover
$M=\\{\\{A_{4},B_{1}\\},\\{A_{4},B_{2}\\},\\{A_{4},B_{3}\\}$,
$\\{A_{1},B_{1}\\},\\{A_{3},B_{3}\\}\\}$ so that $\rho(e,P)=|M|=5$ and this
edge cover number turns out to be the minimum, i.e., $\rho=5$. Then Theorem 1
indicates that $R_{\mbox{\scriptsize linear}}\leq(\rho-1)/(2\rho)=2/5$. As
rate $2/5$ is linearly achievable (see Fig. 2), the linear capacity of this
CDS instance is $2/5$.

The intuition of the linear converse is as follows. (14) in Lemma 1 gives a
lower bound on the dimension of the pairwise noise overlap of the two nodes in
a qualified edge. We will start from this pairwise overlap to obtain a lower
bound on the dimension of the overlap of all nodes in $M$, i.e.,
$\mbox{rowspan}({\bf H}_{A_{4}})\cap\mbox{rowspan}({\bf
H}_{B_{1}})\cap\mbox{rowspan}({\bf H}_{B_{2}})\cap\mbox{rowspan}({\bf
H}_{B_{3}})\cap\mbox{rowspan}({\bf H}_{A_{1}})\cap\mbox{rowspan}({\bf
H}_{A_{3}})$, which is the overlap of all pairwise overlaps of the edges in
$M$, i.e., $\left(\mbox{rowspan}({\bf H}_{A_{4}})\cap\mbox{rowspan}({\bf
H}_{B_{1}})\right)\cap\cdots\cap\left(\mbox{rowspan}({\bf
H}_{A_{3}})\cap\mbox{rowspan}({\bf H}_{B_{3}})\right)$. For example, consider
the first two edges in $M$.

$\displaystyle\dim\big{(}\mbox{rowspan}({\bf
H}_{A_{4}})\cap\mbox{rowspan}({\bf H}_{B_{1}})\cap\mbox{rowspan}({\bf
H}_{B_{2}})\big{)}$ (18) $\displaystyle=$
$\displaystyle\dim\big{(}\left(\mbox{rowspan}({\bf
H}_{A_{4}})\cap\mbox{rowspan}({\bf
H}_{B_{1}})\right)\cap\left(\mbox{rowspan}({\bf
H}_{A_{4}})\cap\mbox{rowspan}({\bf H}_{B_{2}})\right)\big{)}$
$\displaystyle\geq$ $\displaystyle\dim\big{(}\mbox{rowspan}({\bf
H}_{A_{4}})\cap\mbox{rowspan}({\bf
H}_{B_{1}})\big{)}+\dim\big{(}\mbox{rowspan}({\bf
H}_{A_{4}})\cap\mbox{rowspan}({\bf H}_{B_{2}})\big{)}$
$\displaystyle~{}-\dim\big{(}\mbox{rowspan}({\bf H}_{A_{4}})\big{)}$
$\displaystyle\overset{(\ref{eq:noise})}{\geq}$ $\displaystyle L+L-N$ (19)

where (18) follows from the sub-modularity of linear rank functions and the
direct sum (the space spanned by the union of the two sets of vectors) of the
two pairwise overlaps is contained in $\mbox{rowspan}({\bf H}_{A_{4}})$ as
each pairwise overlap involves $\mbox{rowspan}({\bf H}_{A_{4}})$. The last
step follows from the pairwise overlap constraint (14) and the fact that the
rank of ${\bf H}_{A_{4}}$ is $N$. We have now transformed the pairwise overlap
of dimension $L$ to $3$-wise overlap of $2L-N$, where a term of $L-N$ is
added. Next as the edges are connected, we may apply sub-modularity repeatedly
and find the overlap of all noise spaces in $M$ by including one connected
edge at one time, whose dimension turns out to be no less than
$L+(\rho-1)(L-N)=5L-4N$, i.e., the $L-N$ term is added $\rho-1$ times (from
pairwise overlap to $\rho$-wise overlap). Then by (15) in Lemma 1, we know
that such noise overlap leads to signal overlap for all nodes
$V_{P}=\\{A_{1},B_{2},A_{3},B_{1}\\}$ in the unqualified path $P$, in
particular including the two nodes $A_{1},B_{1}$ in the internal qualified
edge $e$. As overlapping signal contributes no information for decoding, such
overlap shall not exist (when the noise overlap of $A_{1},B_{1}$ is exactly
$L$ in (14) and this will be relaxed in the general proof), i.e., $\rho
L-(\rho-1)N\leq 0$, and $R_{\mbox{\scriptsize
linear}}=L/(2N)\leq(\rho-1)/(2\rho)$.

Next, we proceed to our second result, which shows that the linear converse in
Theorem 1 is tight for a class of CDS instances and is stated in Theorem 2.

###### Theorem 2

For any CDS instance where the qualified edges in each qualified component
form either a path or a cycle555A cycle is a path where the first node is the
same as the last node. If the qualified edges form either a path or a cycle,
equivalently, we have that each node is connected to at most two qualified
edges., the linear capacity is $C_{\mbox{\scriptsize
linear}}=(\rho-1)/(2\rho)$.

Note that Theorem 2 only places constraints on the structure of qualified
edges and works for any possible configuration of unqualified edges.

The proof of Theorem 2 is presented in Section 5.

We give an example here to illustrate the idea. Consider the CDS instance in
Fig. 3 and we show that the linear capacity is $C_{\mbox{\scriptsize
linear}}=5/12$. Theorem 2 can be applied as the instance contains two
qualified components, where the qualified edges form a path in one qualified
component and form a cycle in the other qualified component. $\rho=6$, because
for the left qualified component, there is an internal qualified edge
$e=\\{A_{1},B_{1}\\}$ (see the blue circle) in unqualified path
$P=\\{\\{A_{1},B_{2}\\},\\{B_{2},A_{4}\\},\\{A_{4},B_{1}\\}\\}$ (see the red
circles), which is then covered by a qualified path with $6$ edges
$M=\\{\\{A_{1},B_{1}\\},\\{B_{1},A_{2}\\},\\{A_{2},B_{2}\\},\\{B_{2},A_{3}\\},\\{A_{3},B_{3}\\},\\{B_{3},A_{4}\\}\\}$.
It can be verified that this $M$ has the minimum cardinality, so $\rho=6$.
Then the converse bound follows from Theorem 1.

Figure 3: A CDS instance where each qualified component is either a path or a
cycle. For each qualified component, an internal qualified edge $e$ is put in
a blue circle and the nodes $V_{P}$ in the unqualified path $P$ are put in red
circles. Then the connected edge cover $M$ is the qualified path that connects
to all nodes in $V_{P}$. For the left qualified component, $\rho(e,P)=6$ (the
path from $A_{1}$ to $A_{4}$); for the right qualified component,
$\rho(e,P)=7$ (the path from $B_{9}$ to $A_{7}$). The unqualified edges
connecting two nodes from different qualified components are not drawn and can
be arbitrary.

We now consider the achievable scheme. We will consider each qualified
component one by one and use independent noise variables. Let us start from
the left qualified component (a qualified path from $A_{1}$ to $B_{4}$), where
the assignment of each signal is given in Fig. 4.

Figure 4: A linear capacity achieving scheme for the left qualified component.

The uniform and i.i.d. noise variables are assigned sequentially to the nodes
in the path following a sliding window manner, where the first node $A_{1}$
uses $z_{0},z_{1},\cdots,z_{5}$, the second node uses $z_{1},\cdots,z_{6}$,
and so on (every two consecutive nodes share $L=5$ common noise variables).
Note that this noise assignment does not depend on the structure of the
unqualified edges (which is a key property that simplifies the scheme design).
The secret symbols $s_{1},\cdots,s_{5}$ are assigned cyclicly to the noise
variables, i.e., $(s_{1},\cdots,s_{5})$ are assigned to
$(z_{1},\cdots,z_{5})$, $(z_{6},\cdots,z_{10})$ etc. (i.e., $s_{j}$ is
assigned to $z_{5B+j}$ for any integer $B$). The coefficients of $s_{j}$ are
the only left and most important part. To this end, focus on each $z_{i}$ in
an arbitrary order and consider only the nodes that contain $z_{i}$. For
example, consider $z_{6}$, which appears in $6$ nodes
$B_{1},A_{2},B_{2},A_{3},B_{3},A_{4}$ and consider the subgraph induced by
these $6$ nodes. For the induced subgraph, consider each unqualified component
sequentially (any order will work and one node that connects to no unqualified
edge is a trivial unqualified component) and assign the same signal to each
node in the unqualified component. So here first consider the unqualified path
$\\{\\{B_{1},A_{4}\\},\\{A_{4},B_{2}\\}\\}$ and assign $s_{1}+z_{6}$ to
$B_{1},A_{4},B_{2}$; second consider the unqualified path $\\{A_{2},B_{3}\\}$
and assign $2s_{1}+z_{6}$ to $A_{2},B_{3}$; lastly consider $A_{3}$ and assign
$3s_{1}+z_{6}$ to $A_{3}$. All other $z_{i}$ can be treated in the same manner
(essentially for each $z_{i}$, we apply the scheme from Theorem 1 of [4]).
This completes the description of the scheme.

The security and correctness of the scheme follow from the assignment in a
straightforward manner. For security, note that for each unqualified edge, the
signal for overlapping noise is set to be the same so that the security
constraint (9) is satisfied. For correctness, we note that in the qualified
path, every two consecutive nodes are connected by a qualified edge and share
$L$ noise symbols. For each shared noise symbol, the secret symbols have
different coefficients by noting that the connected edge cover number
$\rho>\rho-1$ and each $z_{i}$ appears in consecutive $\rho-1$ edges.

After completing the left qualified component, we proceed to the right
component (a qualified cycle from $A_{5}$ to $B_{10}$ and back to $A_{5}$),
whose assignment is given in Fig. 5.

Figure 5: A linear capacity achieving scheme for the right qualified
component.

The assignment for a cycle is similar to that of a path and we only highlight
the differences here. To cope with the fact that the first and last node is
the same for a cycle, the sliding window based noise assignment needs to wrap
back as well (see the $z_{1}^{\prime},\cdots,z_{5}^{\prime}$ symbols in Fig.
5). Also, the secrets associated with nodes near the front and end need to be
coded and generic (one linear combination of secret symbols
$s_{1},\cdots,s_{5}$ is denoted by $l_{i}$ in Fig. 5) so that when combined
with any blocks of $s_{i}$, all secret symbols can be decoded as long as the
collective number is sufficient. For example, consider the qualified edge
$\\{A_{10},B_{9}\\}$, where we need to recover $S=(s_{1},\cdots,s_{5})$ from
$(s_{1},s_{2},l_{1},l_{2},l_{3})$. We will use Cauchy matrix to realize
$l_{i}$ over a sufficiently large field. The other elements for the cycle case
are the same as those for a path, i.e., consider each $z_{i}$ sequentially and
set each unqualified component to have the same signal that contains $z_{i}$
in the induced subgraph. Details are deferred to the general proof.

Lastly, we consider the unqualified edges connecting two nodes from different
qualified components, which are not drawn in Fig. 3. The presence of any
number of such unqualified edges will not change the result - for the
converse, $\rho$ is not influenced; for the achievability, security is
preserved as independent noises are used (i.e., $z_{i},z_{i}^{\prime}$ in Fig.
4 and Fig. 5, respectively) for different qualified components. The rate
achieved is $R=L/(2N)=5/12$ as the secret has $L=5$ symbols and each signal
has $N=6$ symbols.

The techniques from Theorem 1 and Theorem 2 are not sufficient in general. Our
third result is the linear capacity characterization of a CDS instance in Fig.
6 that goes beyond previous theorems.

Figure 6: A CDS instance whose linear capacity is $7/18$. The converse bound
from Theorem 1 is not tight.

###### Theorem 3

The linear capacity of the CDS instance in Fig. 6 is $C_{\mbox{\scriptsize
linear}}=7/18$.

The proof of Theorem 3 is presented in Section 6. The converse from Theorem 1
is not tight as $\rho=5$ and the converse bound is $R_{\mbox{\scriptsize
linear}}\leq 2/5$, which is strictly larger than $7/18$, the linear capacity.
The converse proof of $R_{\mbox{\scriptsize linear}}\leq 7/18$ requires a
highly non-trivial analysis of the noise and space spaces involved such that
it goes well beyond the techniques from Theorem 1 and does not appear to admit
a simple explanation (so we are not yet able to generalize it further). Once
the converse bound is found, the achievable scheme follows by its guidance and
falls in the general linear feasibility framework presented in Section 2.2.

##  4 Proof of Theorem 1

The proof of Theorem 1 follows similarly from that of the CDS instance in Fig.
2 considered in the previous section. We first simplify a notation that will
be frequently used. For nodes $v_{1},\cdots,v_{i}$, denote the dimension of
the overlap of their noise spaces as $\alpha_{v_{1}\cdots v_{i}}$, i.e.,

$\displaystyle\alpha_{v_{1}\cdots v_{i}}\triangleq\dim(\mbox{rowspan}({\bf
H}_{v_{1}})\cap\cdots\cap\mbox{rowspan}({\bf H}_{v_{i}})).$ (20)

Consider any CDS instance $G_{f}(V,E)$, where $\rho\neq+\infty$ and focus on
an internal qualified edge $e$ in an unqualified path $P$ such that
$\rho(e,P)=\rho$. Then the connected edge cover $M$ for nodes $V_{P}$ in $P$
contains $\rho$ edges and $\rho+1$ nodes, denoted as
$V_{M}=\\{v_{1},v_{2},\cdots,v_{\rho+1}\\}\subset V$. Note that such $e,P,M$
are guaranteed to exist as $\rho\neq+\infty$ and according to the definition
of $\rho$, the connected edge cover $M$ attains the minimal cardinality so
that $M$ is a spanning tree of the nodes $V_{M}$.

Start with the internal qualified edge $e$ in $M$, say
$e=\\{v_{i_{1}},v_{i_{2}}\\}\subset M,i_{1},i_{2}\in\\{1,2,\cdots,\rho+1\\}$.
As $M$ is connected, there must exist a node $v_{i_{3}}\in
V_{M},i_{3}\notin\\{i_{1},i_{2}\\}$ and a node
$u_{1}\in\\{v_{i_{1}},v_{i_{2}}\\}$ such that $\\{u_{1},v_{i_{3}}\\}$ is a
qualified edge. Then from sub-modularity, we have

$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}v_{i_{3}}}\geq\alpha_{v_{i_{1}}v_{i_{2}}}+\alpha_{u_{1}v_{i_{3}}}-N.$
(21)

Then we proceed similarly to find $v_{i_{4}}\in
V_{M},i_{4}\notin\\{i_{1},i_{2},i_{3}\\}$ such that $\\{u_{2},v_{i_{4}}\\}$ is
a qualified edge, where $u_{2}\in\\{v_{i_{1}},v_{i_{2}},v_{i_{3}}\\}$. Again
from sub-modularity, we have

$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}v_{i_{3}}v_{i_{4}}}$
$\displaystyle\geq$
$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}v_{i_{3}}}+\alpha_{u_{2}v_{i_{4}}}-N$
(22) $\displaystyle\overset{(\ref{eq:a123})}{\geq}$
$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}}+\alpha_{u_{1}v_{i_{3}}}+\alpha_{u_{2}v_{i_{4}}}-2N.$
(23)

Continue this procedure, i.e., we include one node $v_{i_{j}}\in
V_{M},i_{j}\notin\\{i_{1},\cdots,i_{j-1}\\},j\in\\{5,\cdots,\rho+1\\}$ at one
time such that $\\{u_{j-2},v_{i_{j}}\\}\in M$ and
$u_{j-2}\in\\{v_{i_{1}},\cdots,v_{i_{j-1}}\\}$. Then we have

$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}\cdots v_{i_{\rho+1}}}$
$\displaystyle\geq$ $\displaystyle\alpha_{v_{i_{1}}\cdots
v_{i_{\rho}}}+\alpha_{u_{\rho-1}v_{i_{\rho+1}}}-N$ (24) $\displaystyle\geq$
$\displaystyle\cdots$ (25) $\displaystyle\geq$
$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}}+\alpha_{u_{1}v_{i_{3}}}+\alpha_{u_{2}v_{i_{4}}}+\cdots+\alpha_{u_{\rho-1}v_{i_{\rho+1}}}-(\rho-1)N.$
(26)

Note that $i_{1},\cdots,i_{\rho+1}$ are distinct so that
$V_{M}=\\{v_{1},\cdots,v_{\rho+1}\\}=\\{v_{i_{1}},\cdots,v_{i_{\rho+1}}\\}$.

As the $\rho+1$ noise spaces have an overlap of dimension
$\alpha_{v_{i_{1}}v_{i_{2}}\cdots v_{i_{\rho+1}}}$, there exist $\rho+1$
projection matrices ${\bf P}^{\cap}_{v_{i_{1}}},\cdots,{\bf
P}^{\cap}_{v_{i_{\rho+1}}}$ of rank $\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}}$ each such that

$\displaystyle{\bf P}^{\cap}_{v_{i_{1}}}{\bf H}_{v_{i_{1}}}={\bf
P}^{\cap}_{v_{i_{2}}}{\bf H}_{v_{i_{2}}}=\cdots={\bf
P}^{\cap}_{v_{i_{\rho+1}}}{\bf H}_{v_{i_{\rho+1}}}.$ (27)

Next, switch focus to the unqualified path $P$. Consider the nodes
$V_{P}\subset V_{M}$ and denote
$V_{P}=\\{v_{i_{1}},v_{j_{1}},v_{j_{2}},\cdots,v_{j_{|V_{P}|-2}},v_{i_{2}}\\}\subset\\{v_{i_{1}},v_{i_{2}},\cdots,v_{i_{\rho+1}}\\}=V_{M}$
such that $\\{v_{i_{1}},v_{j_{1}}\\}$, $\\{v_{j_{1}},v_{j_{2}}\\}$, $\cdots$,
$\\{v_{j_{|V_{P}|-2}},v_{i_{2}}\\}$ are unqualified edges. By (15), i.e., the
signal alignment constraint from Lemma 1, and (27), we have

$\displaystyle{\bf P}^{\cap}_{v_{i_{1}}}{\bf F}_{v_{i_{1}}}={\bf
P}^{\cap}_{v_{j_{1}}}{\bf F}_{v_{j_{1}}}=\cdots={\bf
P}^{\cap}_{v_{j_{|V_{P}|-2}}}{\bf F}_{v_{j_{|V_{P}|-2}}}={\bf
P}^{\cap}_{v_{i_{2}}}{\bf F}_{v_{i_{2}}}$ (28) $\displaystyle\Rightarrow$
$\displaystyle{\bf P}^{\cap}_{v_{i_{1}}}{\bf F}_{v_{i_{1}}}={\bf
P}^{\cap}_{v_{i_{2}}}{\bf F}_{v_{i_{2}}}.$

Finally, consider the internal qualified edge $e=\\{v_{i_{1}},v_{i_{2}}\\}$
and identify the noise overlap through matrices ${\bf P}_{v_{i_{1}}},{\bf
P}_{v_{i_{2}}}$ that have rank $\alpha_{v_{i_{1}},v_{i_{2}}}$, i.e., ${\bf
P}_{v_{i_{1}}}{\bf H}_{v_{i_{1}}}={\bf P}_{v_{i_{2}}}{\bf H}_{v_{i_{2}}}$.
Noting that $\mbox{rowspan}({\bf P}^{\cap}_{v_{i_{1}}})$ is a subspace of
$\mbox{rowspan}({\bf P}_{v_{i_{1}}})$, we set

$\displaystyle{\bf P}^{\cap}_{v_{i_{1}}}={\bf
P}_{v_{i_{1}}}(1:\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}},:),~{}~{}{\bf P}^{\cap}_{v_{i_{2}}}={\bf
P}_{v_{i_{2}}}(1:\alpha_{v_{i_{1}}v_{i_{2}}\cdots v_{i_{\rho+1}}},:)$ (29)

without loss of generality, i.e., the first $\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}}$ rows of ${\bf P}_{v_{i_{1}}}$ are ${\bf
P}^{\cap}_{v_{i_{1}}}$. Then from the correctness constraint (8) for qualified
edge $e=\\{v_{i_{1}},v_{i_{2}}\\}$, we have

$\displaystyle L$ $\displaystyle\overset{(\ref{eq:dec})}{=}$
$\displaystyle\mbox{rank}\left({\bf P}_{v_{i_{1}}}{\bf F}_{v_{i_{1}}}-{\bf
P}_{v_{i_{2}}}{\bf F}_{v_{i_{2}}}\right)$
$\displaystyle\overset{(\ref{eq:v1v2})(\ref{eq:s2})}{=}$
$\displaystyle\mbox{rank}\left({\bf
P}_{v_{i_{1}}}(\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}}+1:\alpha_{v_{1}v_{2}},:){\bf F}_{v_{i_{1}}}-{\bf
P}_{v_{i_{2}}}(\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}}+1:\alpha_{v_{1}v_{2}},:){\bf F}_{v_{i_{2}}}\right)$
$\displaystyle\leq$
$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}}-\alpha_{v_{i_{1}}v_{i_{2}}\cdots
v_{i_{\rho+1}}}$ (32) $\displaystyle\overset{(\ref{eq:v1v2v3vp})}{\leq}$
$\displaystyle\alpha_{v_{i_{1}}v_{i_{2}}}-\left(\alpha_{v_{i_{1}}v_{i_{2}}}+\alpha_{u_{1}v_{i_{3}}}+\alpha_{u_{2}v_{i_{4}}}+\cdots+\alpha_{u_{\rho-1}v_{i_{\rho+1}}}-(\rho-1)N\right)$
(33) $\displaystyle=$
$\displaystyle(\rho-1)N-\left(\alpha_{u_{1}v_{i_{3}}}+\alpha_{u_{2}v_{i_{4}}}+\cdots+\alpha_{u_{\rho-1}v_{i_{\rho+1}}}\right)$
(34) $\displaystyle\overset{(\ref{eq:noise})}{\leq}$
$\displaystyle(\rho-1)N-(\rho-1)L$ (35) $\displaystyle\Rightarrow~{}\rho L$
$\displaystyle\leq$
$\displaystyle(\rho-1)N~{}~{}~{}\Rightarrow~{}~{}R_{\mbox{\scriptsize
linear}}=L/(2N)~{}\leq(\rho-1)/(2\rho).$ (36)

The proof of the linear converse bound in Theorem 1 is thus complete.

##  5 Proof of Theorem 2

In this section, we present a vector linear CDS scheme that achieves rate
$(\rho-1)/(2\rho)$ as long as each qualified component of the CDS instance is
either a path or a cycle. Recall that $\rho$ is the minimum connected edge
cover number defined in Definition 3. Specifically, we set $L=\rho-1$, i.e.,
each secret has $L$ symbols $S=(s_{1},\cdots,s_{\rho-1})$ from
$\mathbb{F}_{p}$ and $N=\rho$, i.e., each signal (node) $v$ has $N$ symbols
from $\mathbb{F}_{p}$. We assume that $p$ is a prime number that is no smaller
than $2\rho-2$.

To prepare for the achievable scheme, we first define $L=\rho-1$ generic
linear combinations $l_{1},\cdots,l_{\rho-1}$ of the secret symbols.

$\displaystyle(l_{1};\cdots;l_{\rho-1})_{(\rho-1)\times 1}$ $\displaystyle=$
$\displaystyle{\bf
C}_{(\rho-1)\times(\rho-1)}\times(s_{1};\cdots,s_{\rho-1})_{(\rho-1)\times 1}$
$\displaystyle{\bf C}_{(\rho-1)\times(\rho-1)}(i,j)$ $\displaystyle=$
$\displaystyle\frac{1}{x_{i}-y_{j}},i,j\in\\{1,\cdots,\rho-1\\}$ (37)

where $x_{i},y_{j}$ are distinct elements from $\mathbb{F}_{p}$ (the existence
is guaranteed by the fact that the field size $p$ is no smaller than
$2\rho-2$), so ${\bf C}_{(\rho-1)\times(\rho-1)}$ is a Cauchy matrix whose
every square sub-matrix has full rank [12].

Consider any CDS instance $G_{f}(V,E)$ such that the minimum connected edge
cover number for any internal qualified edge is $\rho$. Suppose the instance
contains $Q$ qualified components, where each qualified component is either a
path or a cycle of qualified edges. Denote the node set of the $q$-th
qualified component by $V^{q},q\in\\{1,\cdots,Q\\}$ such that
$V=V^{1}\cup\cdots\cup V^{Q}$. For each qualified component, we will use
independent uniform i.i.d. noise symbols from $\mathbb{F}_{p}$, denoted as
$z^{q}=(z^{q}_{0},z^{q}_{1},z^{q}_{2},\cdots)$. The exact number of noise
symbols used in each $z^{q}$ will be specified when we give the scheme and is
indicated by the subscript. So $Z=(z^{1},\cdots,z^{Q})$. We are now ready to
specify the signal design.

  1. 1.

Consider each qualified component sequentially. If the $q$-th qualified
component is a path, go to 2; otherwise the $q$-th qualified component is a
cycle, go to 3.

  2. 2.

The nodes $V^{q}$ form a qualified path. Denote
$V^{q}=\\{v^{q}_{1},\cdots,v^{q}_{|V^{q}|}\\}$. Suppose
$\\{v^{q}_{1},v^{q}_{2}\\}$, $\\{v^{q}_{2},v^{q}_{3}\\}$, $\cdots$,
$\\{v^{q}_{|V^{q}|-1},v^{q}_{|V^{q}|}\\}$ are qualified edges, i.e., we
interpret $v^{q}_{1}$ as the first node and $v^{q}_{|V^{q}|}$ as the end node
of the path.

    1. (a)

Assign the noise variables in a sequential manner as follows.

$\displaystyle
v^{q}_{1}=(z^{q}_{0},z^{q}_{1},\cdots,z^{q}_{\rho-1}),v^{q}_{2}=(z^{q}_{1},z^{q}_{2},\cdots,z^{q}_{\rho}),\cdots,v^{q}_{|V^{q}|}=(z^{q}_{|V^{q}|-1},\cdots,z^{q}_{|V^{q}|+\rho-2}).$
(38)

    2. (b)

We now describe how to the include the secret symbols to each node. Consider
the nodes that contain each noise symbol
$z^{q}_{1},\cdots,z^{q}_{|V^{q}|+\rho-2}$ sequentially ($z^{q}_{0}$ will not
be used) and the induced subgraph formed by these nodes. Note that each noise
symbol $z^{q}_{j},j\in\\{1,\cdots,|V^{q}|+\rho-2\\}$ appears at no more than
$\rho$ nodes and denote the induced subgraph by $G^{q}_{j}\subset G_{f}$.
Suppose $G_{j}^{q}$ contains $K^{q}_{j}$ unqualified components666A node that
connects to no unqualified edge is a trivial unqualified component. As there
are at most $\rho$ nodes in $G^{q}_{j}$, we have that $K^{q}_{j}\leq\rho$.,
each of which is considered sequentially as follows.

For each node $v^{q}_{i}$ in the $k$-th unqualified component of
$G^{q}_{j},k\in\\{1,\cdots,K^{q}_{j}\\},$ $j\in\\{1,\cdots,|V^{q}|+\rho-2\\}$,
replace $z_{j}^{q}$ by $k\times s_{j~{}\mbox{\scriptsize
mod}~{}(\rho-1)}+z_{j}^{q}$. (39)

Note that in $s_{j~{}\mbox{\scriptsize mod}~{}(\rho-1)}$, the subscript is
defined over $\\{1,\cdots,\rho-1\\}$ as secret symbols are
$s_{1},\cdots,s_{\rho-1}$, i.e., $\\{1\\},\cdots,\\{\rho-1\\}$ are the
representative of the equivalent classes of the modulo $\rho-1$ function. The
signal assignment is complete for the path case.

  3. 3.

The nodes $V^{q}$ form a qualified cycle. Denote
$V^{q}=\\{v^{q}_{1},\cdots,v^{q}_{|V^{q}|}\\}$, and suppose
$\\{v^{q}_{1},v^{q}_{2}\\}$, $\\{v^{q}_{2},v^{q}_{3}\\}$, $\cdots$,
$\\{v^{q}_{|V^{q}|-1},v^{q}_{|V^{q}|}\\},\\{v^{q}_{|V^{q}|},v^{q}_{1}\\}$ are
qualified edges.

    1. (a)

Assign the noise variables in the following cyclic manner.

$\displaystyle
v^{q}_{1}=(z^{q}_{1},z^{q}_{2},\cdots,z^{q}_{\rho}),v^{q}_{2}=(z^{q}_{2},z^{q}_{3},\cdots,z^{q}_{\rho+1}),\cdots,$
$\displaystyle
v^{q}_{|V^{q}|-1}=(z^{q}_{|V_{q}|-1},z^{q}_{|V_{q}|},z^{q}_{1},\cdots,z^{q}_{\rho-2}),v^{q}_{|V^{q}|}=(z^{q}_{|V_{q}|},z^{q}_{1},\cdots,z^{q}_{\rho-1}).$
(40)

    2. (b)

We now describe how to the include the secret symbols to each node. Consider
the nodes that contain each noise symbol $z^{q}_{1},\cdots,z^{q}_{|V^{q}|}$
sequentially and the induced subgraph formed by these nodes. Note that each
noise symbol $z^{q}_{j},j\in\\{1,\cdots,|V^{q}|\\}$ appears at $\rho$ nodes
and denote the induced subgraph by $G^{q}_{j}\subset G_{f}$. Suppose
$G_{j}^{q}$ contains $K^{q}_{j}$ unqualified components, each of which is
considered sequentially as follows.

For each node $v^{q}_{i}$ in the $k$-th unqualified component of
$G^{q}_{j},k\in\\{1,\cdots,K^{q}_{j}\\},$ if $j\in\\{1,\cdots,\rho-1\\}$,
replace $z_{j}^{q}$ by $k\times l_{j}+z_{j}^{q}$; otherwise
$j\in\\{\rho,\cdots,|V_{q}|\\}$, replace $z_{j}^{q}$ by $k\times
s_{j~{}\mbox{\scriptsize mod}~{}(\rho-1)}+z_{j}^{q}$. (41)

Note that similar as above, $j~{}\mbox{mod}~{}(\rho-1)$ is defined over
$\\{1,\cdots,\rho-1\\}$. The signal assignment is complete for the cycle case.

After describing the signal design for all nodes, we proceed to show that the
scheme is correct and secure.

First, we prove that the correctness constraint (8) is satisfied. All
qualified edges belong to some qualified component, so it suffices to consider
each qualified component. We have two cases.

  * •

The first case is when the qualified component is a path. From the noise
assignment (38), we know that the two nodes $u,v$ in any qualified edge share
$L=\rho-1$ noise symbols with consecutive subscripts. Further, according to
the signal assignment (39), these $L$ consecutive noise symbols are each mixed
with one distinct secret symbol from the $L$ symbols in $S$. In addition, each
shared secret symbol $s_{i},i\in\\{1,\cdots,L\\}$ in $v$ and $u$ is multiplied
by different coefficients $k$ (see (39)). We prove this claim by
contradiction, i.e., suppose that the coefficients $k$ are the same. Then due
to the signal assignment (39), $e=\\{u,v\\}$ must be an internal qualified
edge in an unqualified path $P$, and we can find a connected edge cover $M$
for the nodes in $P$ and all nodes in $M$ share one same noise symbol. Recall
from Definition 3 that $M$ contains $\rho(e,P)$ edges and $\rho(e,P)\geq\rho$.
As a result, $M$ contains at least $\rho+1$ nodes and these nodes share one
same noise symbol, which is not possible because from the noise assignment
(38), each noise symbol only appears at $\rho$ nodes at most. Thus the
coefficients for the $L$ secret symbols in $v,u$ are all distinct and from
$\\{v,u\\}$ we can recover $S$ with no error.

  * •

The second case is when the qualified component is a cycle, whose proof is
similar to the path case. Similarly from the noise assignment (40), any two
nodes $u,v$ in a qualified edge share $L=\rho-1$ noise symbols with cyclicly
consecutive subscripts. Further, according to the signal assignment (41),
these $L$ noise symbols are each mixed with either one distinct secret symbol
$s_{i}$ from the $L$ symbols in $S$ or one generic linear combination $l_{j}$.
With a similar reasoning as above (due to the definition of $\rho$ and each
noise appears at $\rho$ nodes), the multiplicative coefficients $k$ for
$s_{i},l_{j}$ are distinct. As $l_{j}$ are from a Cauchy matrix (see (37)),
whose every square sub-matrix has full rank, we conclude that from $\\{v,u\\}$
we can obtain $L$ equations of form $s_{i},l_{j}$ thus recover $S$ with no
error.

Second, we prove that the security constraint (9) is satisfied. We have two
cases for an unqualified edge.

  * •

The first case is when the two nodes $u,v$ of the unqualified edge are from
the same qualified component. Security is guaranteed because in the signal
assignment (39), (41), when the noise space overlaps, the same signal equation
is assigned, i.e., signal alignment is ensured and (9) holds.

  * •

The second case is when the two nodes $u,v$ of the unqualified edge are from
two different qualified components. As the noise symbols
$z^{q},z^{q^{\prime}}$ are independent for distinct qualified components, the
noise spaces of $u,v$ have no overlap and (9) trivially holds.

The proof of Theorem 2 is now complete.

##  6 Proof of Theorem 3

We show that the linear capacity of the CDS instance in Fig. 6 is $7/18$. The
achievable scheme is given in Fig. 7. The secret symbols $s_{1},\cdots,s_{7}$
are from $\mathbb{F}_{13}$ and $l_{1},\cdots,l_{5}$ are defined as follows.

$\displaystyle(l_{1};\cdots;l_{5})_{5\times 1}$ $\displaystyle=$
$\displaystyle{\bf C}_{5\times 7}\times(s_{1};\cdots,s_{7})_{7\times 1}$
$\displaystyle{\bf C}_{5\times 7}(i,j)$ $\displaystyle=$
$\displaystyle\frac{1}{x_{i}-y_{j}},i\in\\{1,\cdots,5\\},j\in\\{1,\cdots,7\\}$
(42)

where $x_{i},y_{j}$ are distinct elements from $\mathbb{F}_{13}$ so that ${\bf
C}_{5\times 7}$ is a Cauchy matrix whose every square sub-matrix has full
rank. The correctness and security constraints (8) (9) are straightforward to
verify.

Figure 7: A linear capacity achieving scheme with rate $7/18$. $l_{i}$ is a
generic linear combination of $s_{1},\cdots,s_{7}$.

Next we provide the converse proof. Recall that $\alpha_{v_{1}\cdots v_{J}}$
denotes the dimension of the overlap of the row span of the noise precoding
matrices of $v_{1},\cdots,v_{J}$ and for each node, the rank of the noise
precoding matrix is $N$ (see Footnote 2).

We first give an upper bound for $\alpha_{A_{2},A_{3}}$, where the proof is
similar to that of Theorem 1. Consider nodes $A_{2},A_{3},B_{3},A_{4},B_{4}$.
To identify their noise overlap, we may find $5$ matrices ${\bf
P}_{A_{2}}^{\cap}$, ${\bf P}_{A_{3}}^{\cap}$, ${\bf P}_{B_{3}}^{\cap}$, ${\bf
P}_{A_{4}}^{\cap}$, ${\bf P}_{B_{4}}^{\cap}$ of rank
$\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}}$ each so that

$\displaystyle{\bf P}_{A_{2}}^{\cap}{\bf H}_{A_{2}}={\bf P}_{A_{3}}^{\cap}{\bf
H}_{A_{3}}={\bf P}_{B_{3}}^{\cap}{\bf H}_{B_{3}}={\bf P}_{A_{4}}^{\cap}{\bf
H}_{A_{4}}={\bf P}_{B_{4}}^{\cap}{\bf H}_{B_{4}}.$ (43)

Further, $\\{\\{A_{3},B_{4}\\},\\{B_{4},A_{2}\\},\\{A_{2},B_{3}\\}\\}$ is an
unqualified path. From (15) and (43), we have

$\displaystyle{\bf P}_{A_{3}}^{\cap}{\bf F}_{A_{3}}={\bf P}_{B_{4}}^{\cap}{\bf
F}_{B_{4}}={\bf P}_{A_{2}}^{\cap}{\bf F}_{A_{2}}={\bf P}_{B_{3}}^{\cap}{\bf
F}_{B_{3}}~{}\Rightarrow~{}{\bf P}_{A_{3}}^{\cap}{\bf F}_{A_{3}}={\bf
P}_{B_{3}}^{\cap}{\bf F}_{B_{3}}.$ (44)

Consider now qualified edge $\\{A_{3},B_{3}\\}$ and identify the noise overlap
through ${\bf P}_{A_{3}},{\bf P}_{B_{3}}$ of rank $\alpha_{A_{3}B_{3}}$ so
that ${\bf P}_{A_{3}}{\bf H}_{A_{3}}={\bf P}_{B_{3}}{\bf H}_{B_{3}}$. As
$\mbox{rowspan}({\bf P}^{\cap}_{A_{3}})$ is a subspace of $\mbox{rowspan}({\bf
P}_{A_{3}})$, without loss of generality we set

$\displaystyle{\bf P}^{\cap}_{A_{3}}={\bf
P}_{A_{3}}(1:\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}},:),~{}~{}{\bf
P}^{\cap}_{B_{3}}={\bf P}_{B_{3}}(1:\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}},:).$
(45)

From the correctness constraint (8), we have

$\displaystyle L$ $\displaystyle\overset{(\ref{eq:dec})}{=}$
$\displaystyle\mbox{rank}\left({\bf P}_{A_{3}}{\bf F}_{A_{3}}-{\bf
P}_{B_{3}}{\bf F}_{B_{3}}\right)$
$\displaystyle\overset{(\ref{eq:a3b3})(\ref{eq:ss2})}{=}$
$\displaystyle\mbox{rank}\left({\bf
P}_{A_{3}}(\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}}+1:\alpha_{A_{3}B_{3}},:){\bf
F}_{A_{3}}-{\bf
P}_{B_{3}}(\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}}+1:\alpha_{A_{3}B_{3}},:){\bf
F}_{B_{3}}\right)$ $\displaystyle\leq$
$\displaystyle\alpha_{A_{3}B_{3}}-\alpha_{A_{2}A_{3}B_{3}A_{4}B_{4}}$ (48)
$\displaystyle\overset{}{\leq}$
$\displaystyle\alpha_{A_{3}B_{3}}-(\alpha_{A_{2}A_{3}}+\alpha_{A_{3}B_{3}}+\alpha_{B_{3}A_{4}}+\alpha_{A_{4}B_{4}}-3N)$
(49) $\displaystyle=$ $\displaystyle
3N-(\alpha_{A_{2}A_{3}}+\alpha_{B_{3}A_{4}}+\alpha_{A_{4}B_{4}})$ (50)
$\displaystyle\Rightarrow$ $\displaystyle\alpha_{A_{2}A_{3}}\leq
3N-(\alpha_{B_{3}A_{4}}+\alpha_{A_{4}B_{4}})-L$ (51)

where (49) follows from sub-modularity and we have obtained the desired upper
bound for $\alpha_{A_{2}A_{3}}$.

We are now ready for the final step, which is a similar chain of arguments as
above. Consider $6$ nodes $A_{1},B_{1},A_{2},B_{2},A_{3},B_{3}$ and identify
their noise overlap through matrices ${\bf P}^{\cap\cap}_{A_{1}}$, ${\bf
P}^{\cap\cap}_{B_{1}}$, ${\bf P}^{\cap\cap}_{A_{2}}$, ${\bf
P}^{\cap\cap}_{B_{2}}$, ${\bf P}^{\cap\cap}_{A_{3}}$, ${\bf
P}^{\cap\cap}_{B_{3}}$ of rank $\alpha_{A_{1}B_{1}A_{2}B_{2}A_{3}B_{3}}$ each.

$\displaystyle{\bf P}_{A_{1}}^{\cap\cap}{\bf H}_{A_{1}}={\bf
P}_{B_{1}}^{\cap\cap}{\bf H}_{B_{1}}={\bf P}_{A_{2}}^{\cap\cap}{\bf
H}_{A_{2}}={\bf P}_{B_{2}}^{\cap\cap}{\bf H}_{B_{2}}={\bf
P}_{A_{3}}^{\cap\cap}{\bf H}_{A_{3}}={\bf P}_{B_{3}}^{\cap\cap}{\bf
H}_{B_{3}}$ (52) $\displaystyle\overset{}{\Rightarrow}$ $\displaystyle{\bf
P}_{A_{2}}^{\cap\cap}{\bf F}_{A_{2}}={\bf P}_{B_{2}}^{\cap\cap}{\bf
F}_{B_{2}}$ (53)

where the last step follows from the unqualified path
$\\{\\{A_{2},B_{3}\\},\\{B_{3},A_{1}\\},\\{A_{1},B_{2}\\}\\}$ and (15).

Consider qualified edge $\\{A_{2},B_{2}\\}$ and identify the noise overlap
through ${\bf P}_{A_{2}},{\bf P}_{B_{2}}$ of rank $\alpha_{A_{2}B_{2}}$ so
that ${\bf P}_{A_{2}}{\bf H}_{A_{2}}={\bf P}_{B_{2}}{\bf H}_{B_{2}}$. Then we
have

$\displaystyle\mbox{rowspan}({\bf
P}^{\cap\cap}_{A_{2}})\subset\mbox{rowspan}({\bf
P}_{A_{2}}),~{}~{}\mbox{rowspan}({\bf
P}^{\cap\cap}_{B_{2}})\subset\mbox{rowspan}({\bf P}_{B_{2}})$ (54)
$\displaystyle\Rightarrow L$ $\displaystyle\overset{(\ref{eq:dec})}{=}$
$\displaystyle\mbox{rank}({\bf P}_{A_{2}}{\bf F}_{A_{2}}-{\bf P}_{B_{2}}{\bf
F}_{B_{2}})$ (55) $\displaystyle\overset{(\ref{eq:ss0})(\ref{eq:ss4})}{\leq}$
$\displaystyle\alpha_{A_{2}B_{2}}-\alpha_{A_{1}B_{1}A_{2}B_{2}A_{3}B_{3}}$
(56) $\displaystyle\leq$
$\displaystyle\alpha_{A_{2}B_{2}}-(\alpha_{A_{1}B_{1}A_{2}B_{2}A_{3}}+\alpha_{A_{3}B_{3}}-N)$
(57) $\displaystyle\overset{}{\leq}$
$\displaystyle\alpha_{A_{2}B_{2}}-(\alpha_{A_{1}B_{1}A_{2}A_{3}}+\alpha_{A_{2}B_{2}A_{3}}-\alpha_{A_{2}A_{3}}+\alpha_{A_{3}B_{3}}-N)$
(59) $\displaystyle\overset{(\ref{eq:ss3})}{\leq}$
$\displaystyle\alpha_{A_{2}B_{2}}-\Big{(}\big{(}\alpha_{A_{1}B_{1}}+\alpha_{B_{1}A_{2}}+\alpha_{A_{3}B_{1}}-2N\big{)}+\big{(}\alpha_{A_{2}B_{2}}+\alpha_{B_{2}A_{3}}-N\big{)}$
$\displaystyle~{}-\big{(}3N-(\alpha_{B_{3}A_{4}}+\alpha_{A_{4}B_{4}})-L\big{)}+\alpha_{A_{3}B_{3}}-N\Big{)}$
$\displaystyle=$ $\displaystyle
7N-L-(\alpha_{A_{1}B_{1}}+\alpha_{B_{1}A_{2}}+\alpha_{A_{3}B_{1}}+\alpha_{B_{2}A_{3}}+\alpha_{B_{3}A_{4}}+\alpha_{A_{4}B_{4}}+\alpha_{A_{3}B_{3}})$
(60) $\displaystyle\overset{(\ref{eq:noise})}{\leq}$ $\displaystyle 7N-8L$
(61) $\displaystyle\Rightarrow$ $\displaystyle R_{\mbox{\scriptsize
linear}}=L/(2N)~{}\leq~{}7/18.$ (62)

where sub-modularity is repeatedly applied in (57), (59), (59); in (60),
$\\{v,u\\}$ is a qualified edge in every $\alpha_{vu}$ term, so (14) can be
applied to obtain (61). The converse proof and thus the linear capacity proof
of Theorem 3 is complete.

##  7 Discussion

In this work, we take a Shannon theoretic perspective at the canonical
conditional disclosure of secrets problem to seek capacity characterizations
where the secret size is allowed to approach infinity while most cryptography
work focuses on the scaling of communication cost with the input size777One
exception is recent work [13], where the amortization formulation essentially
considers the same rate metric as our work. The difference is that we focus on
each CDS instance and pursue exact linear capacity characterizations (so
impossibility claims included) while [13] aims at worst case rate
approximation for all CDS instances. [1, 5, 6, 7, 8, 9]. This Shannon
theoretic perspective follows the footsteps of recent attempts in the
information theory community on other cryptographic primitives [14, 15, 16,
17, 18, 19, 20, 21, 22, 23]. Towards this end, we further develop the noise
and signal alignment approach, which is a variation of interference alignment
originally studied in wireless communication networks [24, 25, 26] and is
introduced in [4], to characterize the linear capacity of a class of CDS
instances, which go beyond the highest capacity scenarios found in [4]. Along
the line, we identify a general linear converse bound (see Theorem 1) and a
linear feasibility framework that facilitates the design of linear schemes
once the target rate value is fixed (see Section 2.2). However, these results
are not sufficient to fully understand the linear capacity of CDS in general.
We conclude by giving an intriguing CDS instance whose linear capacity is open
(see Fig. 8). Note that this instance is only slightly changed from the solved
instance in Fig. 2.

Figure 8: A CDS instance whose linear capacity is open. The best known
converse bound is from Theorem 1 and is equal to $2/5$.

## References

  * [1] Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin, “Protecting Data Privacy in Private Information Retrieval Schemes,” in _Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing_. ACM, 1998, pp. 151–160.
  * [2] T. Liu, V. Vaikuntanathan, and H. Wee, “Towards Breaking the Exponential Barrier for General Secret Sharing,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2018, pp. 567–596.
  * [3] B. Applebaum, A. Beimel, O. Nir, and N. Peter, “Better Secret Sharing via Robust Conditional Disclosure of Secrets,” in _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , 2020, pp. 280–293.
  * [4] Z. Li and H. Sun, “Conditional Disclosure of Secrets: A Noise and Signal Alignment Approach,” _arXiv preprint arXiv:2002.05691_ , 2020.
  * [5] R. Gay, I. Kerenidis, and H. Wee, “Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption,” in _Annual Cryptology Conference_. Springer, 2015, pp. 485–502.
  * [6] B. Applebaum, B. Arkis, P. Raykov, and P. N. Vasudevan, “Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-Bounds, and Separations,” in _Annual International Cryptology Conference_. Springer, 2017, pp. 727–757.
  * [7] S. Laur and H. Lipmaa, “A New Protocol for Conditional Disclosure of Secrets and Its Applications,” in _International Conference on Applied Cryptography and Network Security_. Springer, 2007, pp. 207–225.
  * [8] B. Applebaum and P. N. Vasudevan, “Placing Conditional Disclosure of Secrets in the Communication Complexity Universe,” in _10th Innovations in Theoretical Computer Science Conference (ITCS 2019)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [9] T. Liu, V. Vaikuntanathan, and H. Wee, “Conditional Disclosure of Secrets via Non-Linear Reconstruction,” in _Annual International Cryptology Conference_. Springer, 2017, pp. 758–790.
  * [10] S. H. Dau, V. Skachek, and Y. M. Chee, “On the Security of Index Coding with Side Information,” _IEEE Transactions on Information Theory_ , vol. 58, no. 6, pp. 3975–3988, 2012.
  * [11] H. Sun, “Secure Groupcast: Extra-Entropic Structure and Linear Feasibility,” _arXiv preprint arXiv:2006.05944_ , 2020.
  * [12] S. Schechter, “On the inversion of certain matrices,” _Mathematical Tables and Other Aids to Computation_ , vol. 13, no. 66, pp. 73–77, 1959.
  * [13] B. Applebaum and B. Arkis, “On the power of amortization in secret sharing: d-uniform secret sharing and cds with constant information rate,” in _Theory of Cryptography Conference_. Springer, 2018, pp. 317–344.
  * [14] H. Sun and S. A. Jafar, “The Capacity of Private Information Retrieval,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4075–4088, 2017.
  * [15] E. J. Lee and E. Abbe, “Two Shannon-Type Problems on Secure Multi-party Computations,” in _2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, pp. 1287–1293.
  * [16] D. Data, V. M. Prabhakaran, and M. M. Prabhakaran, “Communication and Randomness Lower Bounds for Secure Computation,” _IEEE Transactions on Information Theory_ , vol. 62, no. 7, pp. 3901–3929, 2016.
  * [17] Y. Zhou, H. Sun, and S. Fu, “On the Randomness Cost of Linear Secure Computation,” in _2019 53rd Annual Conference on Information Sciences and Systems (CISS)_ , March 2019, pp. 1–6.
  * [18] Y. Zhao and H. Sun, “Expand-and-Randomize: An Algebraic Approach to Secure Computation,” _arXiv preprint arXiv:2001.00539_ , 2020.
  * [19] H. Sun, “The Capacity of Anonymous Communications,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3871–3879, 2018.
  * [20] B. Tahmasebi and M. A. Maddah-Ali, “Private Sequential Function Computation,” _arXiv preprint arXiv:1908.01204_ , 2019.
  * [21] Z. Wang, K. Banawan, and S. Ulukus, “Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective,” _arXiv preprint arXiv:1912.13501_ , 2020.
  * [22] ——, “Multi-party private set intersection: An information-theoretic approach,” _arXiv preprint arXiv:2008.07504_ , 2020.
  * [23] H. Sun, “Compound Secure Groupcast: Key Assignment for Selected Broadcasting,” _arXiv preprint arXiv:2004.14986_ , 2020.
  * [24] S. A. Jafar, “Interference Alignment - A New Look at Signal Dimensions in a Communication Network,” _Foundations and Trends in Communications and Information Theory_ , vol. 7, no. 1, pp. 1–134, 2011. [Online]. Available: http://dx.doi.org/10.1561/0100000047
  * [25] ——, “Topological Interference Management through Index Coding,” _IEEE Trans. on Inf. Theory_ , vol. 60, no. 1, pp. ”529–568”, Jan. 2014.
  * [26] H. Sun and S. A. Jafar, “Index Coding Capacity: How far can one go with only Shannon Inequalities?” _IEEE Trans. on Inf. Theory_ , vol. 61, no. 6, pp. 3041–3055, 2015.


# Constraining CP violating nucleon-nucleon long range interactions in
diatomic eEDM searches

Chaja Baruch<EMAIL_ADDRESS>Physics Department, Technion –
Israel Institute of Technology, Haifa 3200003, Israel  P. Bryan Changala
<EMAIL_ADDRESS>Center for Astrophysics $|$ Harvard &
Smithsonian, Cambridge, MA 02138, USA  Yuval Shagam<EMAIL_ADDRESS>Schulich Faculty of Chemistry, The Helen Diller Quantum Center and the Solid
State Institute, Technion – Israel Institute of Technology, Haifa, 3200003,
Israel  Yotam Soreq<EMAIL_ADDRESS>Physics Department,
Technion – Israel Institute of Technology, Haifa 3200003, Israel

###### Abstract

The searches for CP violating effects in diatomic molecules, such as
$\text{HfF}^{+}$and ThO, are typically interpreted as a probe of the
electron’s electric dipole moment (eEDM), a new electron-nucleon interaction,
and a new electron-electron interaction. However, in the case of a non-
vanishing nuclear spin, a new CP violating nucleon-nucleon long range force
will also affect the measurement. Here, we use the $\text{HfF}^{+}$eEDM search
and derive a new bound on this hypothetical interaction, which is the most
stringent from terrestrial experiments in the 1-10[k] mass range. These
multiple new physics sources motivate independent searches in different
molecular species for CP violation at low energy that result in model
independent bounds, which are insensitive to cancellation among them.

##  I Introduction

Notwithstanding its great success, the Standard Model (SM) is not a complete
description of Nature and should be extended by physics beyond the Standard
Model (BSM), which is well motivated both by observational evidence and strong
theoretical arguments, see e.g. [1]. New physics (NP) sources of CP violation
(CPV) naturally appear in a variety of extensions of the SM and may be related
to Baryogenesis. Low energy BSM searches, e.g. [2], can probe these effects.
In particular, CPV searches are sensitive to multiple NP effects, e.g.
electric dipole moments (EDMs) [3, 4, 5, 6, 7, 8]. Focusing on electron EDM
(eEDM) searches in diatomic molecules, NP CPV can arise not only in the form
of the eEDM, but also as a new CPV electron-nucleon ($eN$) or electron-
electron ($ee$) interaction [9, 10, 11, 12]. To date, the most stringent eEDM
bound is $|d_{e}|<4.1\times 10^{-30}e\,$ [13, 14], assuming no other CPV
sources. This can be translated to new physics at the scale of
$\mathcal{O}(10\,\textrm{TeV})$.

In this paper, we point out that a new CPV nucleon-nucleon ($NN$) long-range
force mediated by a spin-0 particle contributes to the eEDM frequency channel
and that this effect is probed by measurements in diatomic molecules, in the
case where one or both of the nuclei of the diatomic molecule have non-zero
spin. In addition to the eEDM, CPV can arise from long range forces between
electrons and nuclei, such that there are four NP CPV sources, namely $d_{e}$,
$eN$, $ee$ and $NN$. To constrain these four CPV sources, at least four
independent measurements are required.

The three most sensitive eEDM searches in molecules are the JILA
$\text{HfF}^{+}$ search [13], the ACME ThO search [15], and the Imperial
College London YbF search [16, 17]. Only the first and last include nuclei
with non-vanishing spins and are sensitive to $NN$. We utilize these three
searches to derive novel bounds on three NP CPV sources, i.e. $d_{e}$, $eN$
and $NN$. We note that $ee$ contributes to $d_{e}$ and directly through the
measured frequency channel. The interaction can be also probed by atomic EDM
searches [9] with decent precision. We neglect it here for simplicity and
leave this comparison for future work. Our result is the most constraining
bound on $NN$ from terrestrial experiments. Because the YbF eEDM bound is
weaker by $\mathcal{O}(100)$ compared to the other eEDM searches sensitive to
$NN$, the upcoming $\text{ThF}^{+}$experiment [18], which also contains one
nucleus with a non-zero spin, is further motivated and will lead to a 100-fold
improved sensitivity. Astrophysical bounds from stellar cooling [19] and
neutron stars [20] are stronger, see also [21]. However, these astrophysical
bounds are subject to large systematic uncertainties and moreover, can be
avoided in certain models, see below.

Figure 1: The splitting of the energy levels, $\ket{\Omega,m_{F}}$, is shown
when applying an electric field in (a), a parallel electric and magnetic field
in (b) and the additional shift due to $E_{\rm CPV}$, i.e. eEDM, $NN$ and
$eN$, is shown in (c). The relative directions are illustrated in (d). See
main text for details.

##  II Long range CPV force

We consider a new spin-0 particle, $\phi$, with mass $m_{\phi}$ and both
scalar and pseudo-scalar couplings to fermions. The effective couplings
between $\phi$, the nucleons, $N=n,p$, and the electrons are given by

$\displaystyle\mathcal{L}_{\rm
int}\subset\sum_{\psi=e,p,n}\\!\\!\\!\phi\left(g_{\rm
S}^{\psi}\overline{\psi}\psi+ig_{\rm
P}^{\psi}\overline{\psi}\gamma_{5}\psi\right)\,,$ (1)

and can be mapped to UV models. For example, see [22] and [23, 24] for a
recent review on the CPV axion. Another example is relaxion models [25, 26,
27], which induce a CPV light scalar as a result of mixing with the SM-Higgs.

The effective couplings from Eq. (1) are constrained both by terrestrial
experiments and astrophysical observations, see e.g. [21, 28]. For
$m_{\phi}\lesssim 10\,$, the most stringent bounds on the effective coupling
come from stellar cooling $g_{\rm S}^{N}<1.1\times 10^{-12}$ [19], from
cooling of hot neutron stars $g_{\rm P}^{n}<2.8\times 10^{-10}$ [20] and from
SN1987 $g_{\rm P}^{N}<6.0\times 10^{-10}$ [29]. It has been suggested that the
SN1987 bound faces substantial uncertainties, casting doubt on its robustness
[30]. All of these astrophysical bounds can be avoided in models that are
subject to environmental effects, see e.g. [31, 32, 33, 34, 35, 36] and
discussion in [21]. Moreover, at the one-loop level, the scalar and
pseudoscalar proton couplings contribute to the scalar-photon and
pseudoscalar-photon couplings. Following Ref. [37] to translate the strongest
bounds on these photon couplings, we obtain a bound of $\mathcal{O}(10^{-16})$
on $g_{S}^{p}g_{P}^{p}$. In this case, globular cluster bounds [38] are
subject to the same ambiguity as mentioned above.

Considering terrestrial experiments, the most stringent bounds arise from the
proton and neutron EDMs, $|d_{p}|<2.1\times 10^{-25}e\,$ [39] and
$|d_{n}|<1.8\times 10^{-26}e\,$ [40, 41], respectively. Following Ref. [24]
and assuming $m_{\phi}\ll\textrm{GeV}$, the bounds on the effective couplings
of Eq. (1) are $g_{\rm S}^{p}g_{\rm P}^{p}<8.4\times 10^{-10}$ and $g_{\rm
S}^{n}g_{\rm P}^{n}<1.0\times 10^{-10}$. Additional bounds via pion nucleon
coupling lead to $g_{\rm S}^{n,p}g_{\rm P}^{n,p}<10^{-9}-10^{-11}$ [42]. For
$m_{\phi}\lesssim$ there are very stringent bounds from searches with
macroscopic objects e.g. [43, 44, 45, 46, 47], see discussion in [21]. The
scalar and pseudo scalar couplings can be separately probed by CP conserving
observables, such as molecular vibrational modes e.g. [48, 49] and rare Kaon
decays e.g. [50]. The combined strongest laboratory bounds on the scalar
coupling, from neutron scattering [51, 52, 53], and pseudoscalar coupling,
from molecular HD [54], together give a constraint of $g_{\rm S}^{n}g_{\rm
P}^{n}<1.0\times 10^{-16}$ for $m_{\phi}\lesssim 1$ and $g_{\rm S}^{n}g_{\rm
P}^{n}<1.0\times 10^{-9}-10^{-10}$ for the keV range. For additional bounds,
see e.g. [55]. Bounds on the CPV scalar-photon coupling can be found in e.g.
[56]. They can be reinterpreted as a bound on the proton coupling and the
terrestrial bounds are found to be weaker than other relevant bounds in the
[k] range.

The effective monopole-dipole potential between two nuclei $i$ and $j$ is
given by [57, 58, 59]

$\displaystyle V_{\rm
SP}(r)=\alpha_{\phi}^{ij}\frac{\vec{\sigma}_{j}\cdot\hat{r}}{2\overline{m}_{N}}\left(\frac{1}{r}+m_{\phi}\right)\frac{e^{-rm_{\phi}}}{r}\,,$
(2)

where $\vec{\sigma}_{j}$ are the Pauli matrices that follow the spin of the
valance nucleon, $\overline{m}_{N}=939\,[M]$ is the average nucleon mass and
$\vec{r}$ is the inter-nuclear axis of the molecule. The NP interaction
strength is defined

$\displaystyle\alpha_{\phi}^{ij}\equiv-\frac{1}{4\pi}(Z^{i}g_{\rm
S}^{p}+N^{i}g_{\rm S}^{n})(B^{j}_{p}g_{\rm P}^{p}+B^{j}_{n}g_{\rm P}^{n})\,,$
(3)

where $Z^{i}\,(N^{i})$ is the number of protons (neutrons) in nucleus $i$. The
relation between the nucleus and the nucleon spins, as well as the proton-
neutron mass difference, is encoded in $B^{j}_{n,p}$ [58, 60], see Appendix A.
Since for molecules $r\sim 10^{-10}\,$, a $\phi$ with $m_{\phi}\lesssim 2\,$
will induce a long range force at the molecular scale.

##  III Nucleon-nucleon long range CPV force in diatomic molecules

Molecule |  $r_{\rm eq}$ [Å] | $W^{ij}_{NN}\,[[\mu]]$ | $W^{ij}_{d_{e}}\,[[\mu]/e\,[c]]$ | $W^{ij}_{eN}\,[[\mu]]$ | $E_{\rm CPV}^{ij}\,[[\mu]]$
---|---|---|---|---|---
180$\text{HfF}^{+}$ | 1.81 [61] | $1.55\times 10^{17}$ |  $5.55\times 10^{30}$ [10] |  $1.16\times 10^{22}$ [9] |  $-7.3\pm 11.9$ [13]
232ThO | 1.84 [62] | - |  $1.91\times 10^{31}$ [10] |  $1.03\times 10^{22}$ [9] |  $81.2\pm 77.2$ [15]
174YbF | 2.02 [62] | $1.24\times 10^{17}$ |  $-3.12\times 10^{30}$ [10] |  $2.21\times 10^{22}$ [9] |  $748.7\pm 1810.5$ [16]
232$\text{ThF}^{+}$ | 1.99 [63] | $1.28\times 10^{17}$ |  $9.02\times 10^{30}$ [64] |  |  $0\pm 5$ (projection) [18]
Table 1: Summary of eEDM measurements and the parameters relevant to computing
the NN coupling effect. $W^{ij}_{eN}$ and $W^{ij}_{NN}$ are given in the limit
of $m_{\phi}\ll$.

Here we briefly describe the recently reported eEDM measurement using trapped
$\text{HfF}^{+}$ molecules [13, 14], which we use as an example to illustrate
the effect. The measurement is focused on the ${}^{3}\Delta_{1}$, $J=1$,
$F=3/2$ science state. Leveraging the ${}^{3}\Delta_{1}$ state’s
$\Omega-$doubling, the state is polarized by a rotating electric field to form
states of well defined orientation, called the upper and lower doublets,
denoted by $\Omega m_{F}=\pm 3/2$, see Fig. 1 (a). Here $\Omega=\pm 1$ denotes
the quantum number of the projection of the electronic angular momentum,
$J=L+S=1$, onto the inter-nuclear axis in the molecule frame and $m_{F}$ is
the quantum number of the projection of the total angular momentum including
nuclear spin, $F=J+I$, in the rotating-frame. A bias magnetic field is aligned
or anti-aligned with the electric field to lift the remaining degeneracy
between the $m_{F}=\pm 3/2$ states of both $\Omega m_{F}=\pm 3/2$ doublets,
Fig. 1 (b). In total there are four relevant states,
$\ket{\Omega,m_{F}}=\ket{\pm 1,\pm 3/2}$.

The energy of each state is a sum of a common energy shift ($E_{0}$), a state
dependent Stark shift ($E_{\rm S}$), Zeeman shift ($E_{\rm Z}$) and a CPV
shift ($E_{\rm CPV}$), which includes the eEDM and other NP effects. In total,
we can write

$\displaystyle E_{\Omega,m_{F}}=E_{0}+E_{\rm S}+E_{\rm Z}+E_{\rm CPV}\,.$ (4)

The signs of $E_{\rm S}$, $E_{\rm Z}$ and $E_{\rm CPV}$ are proportional to
the signs of $\Omega m_{F}$, $m_{F}B_{0}$ and $\Omega m_{F}^{2}$,
respectively, where $B_{0}$ is the magnetic field. The sign of the Stark shift
follows the orientation of the molecule axis relative to the rotating-frame,
which is defined by the rotating electric field. The Zeeman shift follows the
orientation of the electron spin relative to the rotating-frame which is
aligned with the magnetic field. The CPV is proportional to both $\Omega
m_{F}\times m_{F}$, i.e. to the product of the external electric and magnetic
fields.

In an example iteration of the experiment, the molecules are prepared in the
$\ket{\pm 1,+3/2}$ states. A Ramsey spin-precession measurement is conducted
between the $m_{F}=+3/2$ and $-3/2$ states for the two doublets with the
results measured separately. Here $E_{0}$ and $E_{\rm S}$ are common to the
$m_{F}=\pm 3/2$ states and are cancelled to leading order where residual
effects are suppressed. For a positive $E_{\rm CPV}$, the two states
$m_{F}=\pm 3/2$ with opposite $\Omega$ move closer together (farther apart) in
lower, $\Omega m_{F}=-\frac{3}{2}$ (upper, $\Omega m_{F}=\frac{3}{2}$)
doublets, Fig. 1 (c). The doubly differential measurement between the results
for the two doublets as well as the aligned and anti-aligned magnetic fields
is used to isolate the CPV effects. Thus, under $(B_{0},m_{F},\Omega
m_{F})\to(-B_{0},-m_{F},-\Omega m_{F})$ (or in other words, the $f_{DB}$
channel) we are left with

$\displaystyle E_{\rm CPV}=$
$\displaystyle\frac{(E_{+1,+\frac{3}{2}}\\!-\\!E_{-1,-\frac{3}{2}})-(E_{-1,+\frac{3}{2}}\\!-\\!E_{+1,-\frac{3}{2}})}{4}\,,$
(5)

and the sign of $B_{0}$ is same as the sign of $m_{F}$. The measurements from
other experimental switches are averaged to suppress sources of systematic
uncertainty, which are not written in Eq. (4) for simplicity.

The principle of the measurement illustrated above is common to all eEDM
experiments such as $\text{HfF}^{+}$, ThO, and $\text{ThF}^{+}$where
$\Omega-$doubling is in effect. In other cases such as YbF, the electric field
direction is switched instead of comparing doublet states. In all these cases,
fully-stretched states of the total angular momentum $F$ are used to orient
the eEDM with respect to the molecule, whose strong internal electric fields
polarize to the electron. This effective electric field,
$\vec{\mathcal{E}}_{\rm eff}$, points along the $\hat{r}$ direction, i.e.
$\hat{r}\sim\Omega\,m_{F}$. This means that any non-zero nuclear spin, namely
that of 19F ($I=1/2$), will be oriented with both the eEDM and the
internuclear axis.

Next, we describe why this measurement is also sensitive to the CPV $NN$
interaction. In the eEDM experiment, the polarizing electric field $E_{\rm
rot}$ is parallel/anti-parallel to the magnetic field $B_{\rm rot}$. Moreover,
for $F=3/2$, the nuclear spin of fluorine must be oriented with $J$. Thus, for
the fully stretched $m_{F}$ states the nuclear spin points along the
internuclear axis and against the electron spin.

More explicitly, the energy shift of the eEDM
$\propto\langle\vec{\mathcal{E}}_{eff}\cdot\vec{d}_{e}\rangle\propto\langle\hat{r}\cdot\vec{S}\rangle\propto\langle\hat{r}\cdot\vec{I}\rangle\propto
V_{\rm PS}$ of Eq. (2) for each of the 4 states with $I$ the nuclei spin.
Therefore, the effect of Eq. (2) behaves as $V_{\rm
PS}\propto\langle\hat{r}\cdot\vec{I}\rangle\propto\Omega m_{F}\times
m_{F}\propto\Omega m_{F}^{2}$. This means that for the upper (lower) doublet
the states $m_{F}=\pm 3/2$ move closer together (farther apart) in energy due
the $V_{\rm PS}$ interaction for $g_{\rm P}^{N}g_{\rm S}^{N}>0$, which is
exactly the ($\mathcal{T}$-violating) behavior of the eEDM and their
contributions to the $E_{\rm CPV}$ energy cannot be distinguished. The
splitting of the energy levels when applying electromagnetic fields is shown
in Fig. 1 (a)-(b). Therefore, in addition to $d_{e}$, and CPV in $eN$ and $ee$
interactions [9, 10, 11], the diatomic eEDM searches can be affected also from
$NN$ CPV long range forces as captured by the potential of Eq. (2).

The four relevant CPV sources in the diatomic molecule $ij$ can be written as

$\displaystyle E_{\rm
CPV}^{ij}=W^{ij}_{d_{e}}d_{e}+W^{ij}_{eN}\alpha_{\phi}^{ie}+W^{ij}_{ee}\alpha_{\phi}^{ee}+W^{ij}_{NN}\alpha_{\phi}^{ij}\,,$
(6)

where the $eN$, $ee$ and $NN$ contributions are functions of $m_{\phi}$,
$\alpha_{\phi}^{ie}\equiv(Z^{i}g_{\rm S}^{p}+N^{i}g_{\rm S}^{n})g_{\rm
P}^{e}/4\pi$ and $\alpha_{\phi}^{ee}\equiv g_{\rm S}^{e}g_{\rm P}^{e}/4\pi$.
The $W^{ij}_{NN}\alpha_{\phi}^{ij}$ is the new CPV nucleon-nucleon interaction
due to the potential in Eq. (2). The relevant $W^{ij}$’s are summarized in
Table 1 with other experimental values, see also [11] for
$W^{\text{$\text{HfF}^{+}$}}_{eN}$ and $W^{\text{$\text{HfF}^{+}$}}_{ee}$.
Since the $ee$ interaction can be directly probed by atomic systems, e.g. [9],
and contributes also to the eEDM, we neglect it below, but it is
straightforward to include.

The nucleon-nucleon interaction function can be estimated by using first-order
perturbation theory

$\displaystyle W^{ij}_{NN}=\frac{\left\langle V_{\rm
SP}\right\rangle}{\alpha_{\phi}^{ij}}\approx\frac{\langle\vec{\sigma}_{j}\cdot\hat{r}_{\rm
eq}\rangle}{2\overline{m}_{N}}\left(\frac{1}{r_{\rm
eq}}+m_{\phi}\right)\frac{e^{-r_{\rm eq}m_{\phi}}}{r_{\rm eq}}\,,$ (7)

where $r_{\rm eq}$ is the equilibrium distance between the two nuclei and
$\langle\vec{\sigma}_{j}\cdot\hat{r}_{\rm eq}\rangle$ is the nuclear spin
expectation value on the internuclear axis for the state. In the fully
stretched state (maximal angular momentum),
$\langle\vec{\sigma}_{j}\cdot\hat{r}_{\rm eq}\rangle=1$. Although we have
taken the internuclear distance to be fixed to its equilibrium value, we have
verified, using the Morse anharmonic potential, that the correction from
consideration of the nuclear vibrational wave functions of the ground state is
at the few percent level for most of the relevant $m_{\phi}$ range and at most
$\mathcal{O}(1)$ for the high masses.

To further emphasize the importance of the $NN$ effect and encourage future
CPV measurements in new molecules, we estimate the possible limit that will
likely be set in the mature $\text{ThF}^{+}$measurement, assuming that a value
consistent with zero is found. To predict the limit for $\text{ThF}^{+}$, we
use the description in [18] to achieve a conservative estimate of the expected
precision assuming a shot noise limited measurement. Ref. [18] predicts a
coherence time of 20 s and Ref. [65] reports 10 ions counted per shot on the
side of the fringe in both doublets in a comparable measurement system. We
also assume the fringe contrast is 0.55 as was found for $\text{HfF}^{+}$ [13]
due to the similarities between the two systems. If a total of 600 hours of
data as in Ref. [13] are taken using the conveyor belt of ion traps
architecture mentioned in Ref. [18, 65], which would allow for a 10 Hz
repetition rate, a total of $10^{8}$ ions will be detected neglecting dead
times and early time phase measurements. Using these parameters we predict a
statistical uncertainty of $\sim 5\,\mu$Hz which we use for the projection
here, see Table 1.

##  IV Results

|  Measured ($\text{HfF}^{+}$, ThO, YbF) |  Projection ($\text{HfF}^{+}$, ThO, YbF, $\text{ThF}^{+}$)
---|---|---
| $NN$ | $NN,\,d_{e}$ | $NN,\,d_{e},\,eN$ | $NN$ | $NN,\,d_{e}$
(a) $g_{S}^{p}g_{P}^{p}$ | $2.8\times 10^{-17}$ | $7.6\times 10^{-17}$ | $3.8\times 10^{-15}$ | $8.8\times 10^{-18}$ | $7.1\times 10^{-17}$
(b) $g_{S}^{n}g_{P}^{n}$ | $2.5\times 10^{-16}$ | $6.8\times 10^{-16}$ | $3.1\times 10^{-14}$ | $7.6\times 10^{-17}$ | $6.6\times 10^{-16}$
(c) $g_{S}^{p,n}g_{P}^{p,n}$ | $1.2\times 10^{-17}$ | $3.3\times 10^{-17}$ | $1.6\times 10^{-15}$ | $3.7\times 10^{-18}$ | $3.1\times 10^{-17}$
$d_{e}$ |  | $1.1\times 10^{-29}$ | $3.6\times 10^{-28}$ |  | $8.5\times 10^{-30}$
(a) $g_{S}^{p}g_{P}^{e}$ |  |  | $8.3\times 10^{-20}$ |  |
(b) $g_{S}^{n}g_{P}^{e}$ |  |  | $5.4\times 10^{-20}$ |  |
(c) $g_{S}^{p,n}g_{P}^{e}$ |  |  | $3.3\times 10^{-20}$ |  |
Table 2: Summary of results, with 90% CL. The columns indicate which
interactions are switched on, see Eq. (6). The rows indicate the relevant
couplings, for: only proton coupling (a), only neutron coupling (b), or equal
proton and neutron couplings (c). For the eEDM the results for (a), (b), (c)
differ by less than 10 percent. Figure 2:  The bounds on long-range nucleon-
nucleon CPV interaction for: only proton interaction (a), only neutron
interaction (b), and both proton and neutron interaction (c). Bounds from
neutron and proton EDMs [24], as well as the combined strongest laboratory
bounds on the scalar coupling, from neutron scattering [51, 52, 53], and
pseudoscalar coupling, from molecular HD [54], are also shown. Projected
bounds due to a future $\text{ThF}^{+}$measurement are plotted in dashed
lines.

To set bounds on the couplings under consideration in this work, we use the
measured frequency shift of $\text{HfF}^{+}$, ThO and YbF. Additionally, we
give projected bounds when considering the future $\text{ThF}^{+}$measurement.
This improves the sensitivity for the scenario in which all interactions are
turned on by nearly two orders of magnitude.

We first consider the case of only the $NN$ interaction and set the other CPV
sources to zero. As there is only one unknown, namely $g_{\rm S}^{N}g_{\rm
P}^{N}$, it is sufficient to use only one eEDM measurement, the JILA
$\text{HfF}^{+}$. We take into account three representative cases that
illustrate the importance of the different coupling constants; $\phi$
interacts (a) only with protons, $g_{\rm S}^{n}=g_{\rm P}^{n}=0$; (b) only
with neutrons, $g_{\rm S}^{p}=g_{\rm P}^{p}=0$; and (c) equally with protons
and neutrons, $g_{\rm S}^{p}=g_{\rm S}^{n}$ and $g_{\rm P}^{p}=g_{\rm P}^{n}$.
The resulting 90 % confidence limit (CL) upper bounds for $m_{\phi}\ll$ are
given in Table 2, and bounds as a function of $m_{\phi}$ are plotted in Fig.
2. This results in the strongest terrestrial bounds, to the best of our
knowledge. For example, the bounds from the proton and neutron EDMs are weaker
by at least six orders of magnitude. However, astrophysical bounds from
stellar cooling are stronger by four or five orders of magnitude but are
subject to different systematics and are model dependent, see the above
discussion.

Figure 3:  The allowed region in the $d_{e}$–$NN$ plane, when setting the
electron-nucleon interaction to zero ($\alpha_{\phi}^{ie}=0$). The solid lines
are derived from measurements of $\text{HfF}^{+}$and ThO, and the dotted lines
are derived from the measurement of $\text{HfF}^{+}$and the projection of
$\text{ThF}^{+}$. All three cases are plotted here, as indicated in the plot.
Note that for (b), we rescaled the contour by a factor of 10 along the $g_{\rm
S}^{N}g_{\rm P}^{N}$ axis.

Second, we consider $d_{e}$ and $NN$ as CPV sources and assume vanishing
$\phi$–$e$ couplings. In this scenario, we probe $d_{e}$ and $g_{\rm
S}^{N}g_{\rm P}^{N}$. Profiling with respect to each parameter and taking the
$m_{\phi}\ll$ limit, the 90% CL intervals are given in Table 2. The allowed
region in the $g_{\rm S}^{N}g_{\rm P}^{N}$–$d_{e}$ plane is shown in Fig. 3,
with solid lines for the measurement result and dashed lines for the
projection. The translated bounds for the aforementioned cases, (a), (b), (c),
are given in Table 2.

Third, we consider three CPV sources, $d_{e}$, $NN$ and $eN$. For simplicity,
we take the limit of $m_{\phi}\ll$, generalization for higher mass is
straightforward. Profiling each time on the other parameter, the 90% CL
intervals are given in Table 2. The allowed regions in the $g_{\rm
S}^{n,p}g_{\rm P}^{e}$–$d_{e}$, $g_{\rm S}^{n,p}g_{\rm P}^{n,p}$–$d_{e}$ and
$g_{\rm S}^{n,p}g_{\rm P}^{e}$–$g_{\rm S}^{n,p}g_{\rm P}^{n,p}$ planes are
plotted in Fig. 4.

Figure 4: Contour plots for $NN$, $eN$ when profiling over $d_{e}$ (first
row), for $NN$, $d_{e}$ when profiling over $Ne$ (second row), and for
$d_{e}$, $eN$ when profiling over $NN$ (third row). All profiling is done for
the massless NP case ($m_{\phi}=0$). The results are given for the three cases
(a), (b) and (c) as indicated.

##  V Conclusions

In this work, we point out that the eEDM searches in diatomic molecules,
composed of at least one nucleus with a non-vanishing spin, are sensitive to
new long range CPV nucleon-nucleon interactions. Based on the eEDM searches in
$\text{HfF}^{+}$, ThO, and YbF, we have derived novel bounds on such a
hypothetical interaction mediated by a spin-0 particle with scalar and pseudo-
scalar couplings to nucleons. The resulting bounds are the most stringent
obtained from laboratory experiments. For example, we show that in the
presence of $eN$ and $NN$ the bound on the $d_{e}$ will be weaker by two
orders of magnitude compared to the simple case of only eEDM as a source of
CPV. We project that adding the expected $\text{ThF}^{+}$measurement will
improve the sensitivity by about two orders of magnitude.

There are two questions left for future work which we note. For eEDM searches
using polyatomic molecules that rely on $l$-doubling, the sensitivity to the
$NN$ effect needs to be determined from the direction of the nuclear spin,
e.g. [66, 67]. eEDM searches on excited rotational and vibrational states can
vary the magnitude of the $NN$ interaction contribution providing more
information within a single molecule to isolate the effect.

###### Acknowledgements.

We gratefully thank Yevgeny Stadnik for careful reading of the manuscript and
fruitful discussions. We also thank Gilad Perez, and Tomer Volansky for useful
discussions. We thank Eric Cornell, Gilad Perez, Jun Ye for comments on the
manuscript. C.B. and Y.So. are supported by grants from the NSF-BSF (grant No.
2021800), the ISF (grant No. 483/20), the BSF (grant No. 2020300) and by the
Azrieli foundation. Y.Sh. gratefully acknowledges funding by the European
Union (ERC, 2033752 – Q-ChiMP). Views and opinions expressed are however those
of the authors only and do not necessarily reflect those of the European Union
or the European Research Council Executive Agency. Neither the European Union
nor the granting authority can be held responsible for them.

##  Appendix A Nucleus to nucleon spin couplings

The pseudoscalar coupling of Eq. (3) contains both the spin-dependent part as
well as the mass difference part between the proton and neutron. We define

$\displaystyle B_{p\,(n)}=\frac{\overline{m}_{N}}{m_{p\,(n)}}b_{p\,(n)}$ (8)

where $\overline{m}_{N}$ is the average nucleon mass, $m_{p\,(n)}$ is the
proton (neutron) mass and $b_{p(n)}$ is the effective pseudoscalar proton
(neutron) coupling of the nucleus. Following [58], this effective coupling
$b_{p\,(n)}$ is obtained by parameterizing the spin couplings to new physics
in terms of an exotic atomic dipole moment, which is related to the coupling
constants for the electron, proton, and neutron. The total atomic angular
momentum is related to the electron spin ($S$) and nuclear spin ($I$) via the
Russell-Saunders LS-coupling scheme,
$\expectationvalue{F}=\expectationvalue{S}+\expectationvalue{L}+\expectationvalue{I}$,
and can then relate the exotic atom dipole moment to the coupling constants

$\displaystyle g_{A}=g_{e}\frac{\expectationvalue{S\cdot
F}}{F(F+1)}+g_{N}\frac{\expectationvalue{I\cdot F}}{F(F+1)}\,.$ (9)

The coupling constant of the nucleus $g_{N}$ is related to the proton and
neutron couplings $g_{p}$, and $g_{n}$. Generally, there are four
contributions to the nuclear spin: proton and neutron spin and orbital angular
momentum

$\displaystyle I$ $\displaystyle=b_{p}I+b_{n}I+b_{\ell,p}+b_{\ell,n}$
$\displaystyle=\expectationvalue{I_{p}}+\expectationvalue{I_{n}}+\expectationvalue{L_{p}}+\expectationvalue{L_{n}}$
(10)

for $b_{p}+b_{n}+b_{\ell,p}+b_{\ell,n}=1$. The exotic dipole moment coupling
constant thus is $g_{N}=b_{p}g_{p}+b_{n}g_{n}$.

As a first approximation (the Schmidt model) it is assumed the nucleus spin is
due only to the orbital motion and spin of a single nucleon (the valence
nucleon) and the spin and angular momentum of all other nucleons sums to zero

$\displaystyle b^{(0)}_{s}=\begin{cases}\frac{1}{2\ell+1},&\text{ for
}I=\ell+\frac{1}{2}\\\ \frac{-1}{2\ell+1},&\text{ for
}I=\ell-\frac{1}{2}\end{cases}$ (11)

and $b^{(0)}_{\ell}=1-b^{(0)}_{s}$. Here, $s=n\text{ or }p$, depending on
whether the atom has a valence neutron or proton. When measuring nuclear spin-
dependent properties, the contribution of non-valence nucleon spins cannot be
neglected due to the polarization of these nucleons by the valence nucleon
[68]. The preferred Flambaum-Tedesco (FT) model accounts for this by using the
Schmidt model as a first approximation, via
$b_{s}^{(0)}=b_{p}+b_{n},b^{(0)}_{\ell}=b_{\ell,p}+b_{\ell,n}$, and then
assuming that the total angular momentum of protons is conserved separately
from neutrons, such that

$\displaystyle b_{p}+b_{\ell p}$ $\displaystyle=\begin{cases}1&\text{ for
valence proton,}\\\ 0&\text{ for valence neutron,}\end{cases}$ $\displaystyle
b_{p}$
$\displaystyle=\begin{cases}\frac{G_{I}-G_{n}b_{s}^{(0)}-1}{G_{p}-G_{n}-1}&\text{
for valence proton,}\\\ \frac{G_{I}-G_{n}b_{s}^{(0)}}{G_{p}-G_{n}-1}&\text{
for valence neutron,}\end{cases}$ $\displaystyle b_{n}$
$\displaystyle=b^{(0)}_{s}-b_{p}\,,$ (12)

where $G$ are the spin g-factors. For all molecules discussed in this work,
only 19F carries spin, and its effective pseudoscalar coupling is

$\displaystyle g^{\rm
F}_{P}=1.08\frac{\overline{m}_{N}}{m_{p}}g_{p}^{p}-0.08\frac{\overline{m}_{N}}{m_{n}}g_{n}^{p}\,,$
(13)

where we used the fact that 19F has a valence neutron, and $g_{p,n}^{p}$ are
the pseudoscalar proton and neutron couplings, respectively. To obtain this
result, we used $G_{\rm F}=5.26$ for the spin g-factor of 19F.

## References

  * [1] R. K. Ellis et al., “Physics Briefing Book: Input for the European Strategy for Particle Physics Update 2020.” arXiv:1910.11775.
  * [2] M. S. Safronova, et al., “Search for New Physics with Atoms and Molecules,” Rev. Mod. Phys. 90 (2018) 025008 [arXiv:1710.01833].
  * [3] M. Pospelov, “CP odd interaction of axion with matter,” Phys. Rev. D 58 (1998) 097703 [hep-ph/9707431].
  * [4] J. S. M. Ginges and V. V. Flambaum, “Violations of fundamental symmetries in atoms and tests of unification theories of elementary particles,” Phys. Rept. 397 (2004) 63–154 [physics/0309054].
  * [5] M. Pospelov and A. Ritz, “Electric dipole moments as probes of new physics,” Annals Phys. 318 (2005) 119–169 [hep-ph/0504231].
  * [6] J. Engel, M. J. Ramsey-Musolf, and U. van Kolck, “Electric Dipole Moments of Nucleons, Nuclei, and Atoms: The Standard Model and Beyond,” Prog. Part. Nucl. Phys. 71 (2013) 21–74 [arXiv:1303.2371].
  * [7] T. Chupp, P. Fierlinger, M. Ramsey-Musolf, and J. Singh, “Electric dipole moments of atoms, molecules, nuclei, and particles,” Rev. Mod. Phys. 91 (2019) 015001 [arXiv:1710.02504].
  * [8] K. Gaul and R. Berger, “Global analysis of CP-violation in atoms, molecules and role of medium-heavy systems.” arXiv:2312.08858.
  * [9] Y. V. Stadnik, V. A. Dzuba, and V. V. Flambaum, “Improved Limits on Axionlike-Particle-Mediated P , T -Violating Interactions between Electrons and Nucleons from Electric Dipole Moments of Atoms and Molecules,” Phys. Rev. Lett. 120 (2018) 013202 [arXiv:1708.00486].
  * [10] T. Fleig and M. Jung, “Model-independent determinations of the electron EDM and the role of diamagnetic atoms,” JHEP 07 (2018) 012 [arXiv:1802.02171].
  * [11] S. D. Prosnyak, D. E. Maison, and L. V. Skripnikov, “Updated Constraints on ,-Violating Axionlike-Particle-Mediated Electron–Electron and Electron–Nucleus Interactions from HfF+ Experiment,” Symmetry 15 (2023) 1043 [arXiv:2304.07164].
  * [12] V. V. Flambaum, M. Pospelov, A. Ritz, and Y. V. Stadnik, “Sensitivity of EDM experiments in paramagnetic atoms and molecules to hadronic CP violation,” Phys. Rev. D 102 (2020) 035001 [arXiv:1912.13129].
  * [13] T. S. Roussy et al., “An improved bound on the electron’s electric dipole moment,” Science 381 (2023) adg4084 [arXiv:2212.11841].
  * [14] L. Caldwell et al., “Systematic and statistical uncertainty evaluation of the HfF+ electron electric dipole moment experiment,” Phys. Rev. A 108 (2023) 012804 [arXiv:2212.11837].
  * [15] ACME Collaboration, “Improved limit on the electric dipole moment of the electron,” Nature 562 (2018) 355–360.
  * [16] J. J. Hudson, et al., “Improved measurement of the shape of the electron,” Nature 473 (2011) 493–496.
  * [17] D. M. Kara, et al., “Measurement of the electron’s electric dipole moment using YbF molecules: methods and data analysis,” New J. Phys. 14 (2012) 103051 [arXiv:1208.4507].
  * [18] K. B. Ng et al., “Spectroscopy on the electron-electric-dipole-moment–sensitive states of ThF+,” Phys. Rev. A 105 (2022) 022823 [arXiv:2202.01346].
  * [19] E. Hardy and R. Lasenby, “Stellar cooling bounds on new light particles: plasma mixing effects,” JHEP 02 (2017) 033 [arXiv:1611.05852].
  * [20] M. V. Beznogov, E. Rrapaj, D. Page, and S. Reddy, “Constraints on Axion-like Particles and Nucleon Pairing in Dense Matter from the Hot Neutron Star in HESS J1731-347,” Phys. Rev. C 98 (2018) 035802 [arXiv:1806.07991].
  * [21] C. A. J. O’Hare and E. Vitagliano, “Cornering the axion with $CP$-violating interactions,” Phys. Rev. D 102 (2020) 115026 [arXiv:2010.03889].
  * [22] J. E. Moody and F. Wilczek, “NEW MACROSCOPIC FORCES?” Phys. Rev. D 30 (1984) 130.
  * [23] L. Di Luzio, H. Gisbert, G. Levati, P. Paradisi, and P. Sørensen, “CP-Violating Axions: A Theory Review.” arXiv:2312.17310.
  * [24] L. Di Luzio, G. Levati, and P. Paradisi, “The Chiral Lagrangian of CP-Violating Axion-Like Particles.” arXiv:2311.12158.
  * [25] P. W. Graham, D. E. Kaplan, and S. Rajendran, “Cosmological Relaxation of the Electroweak Scale,” Phys. Rev. Lett. 115 (2015) 221801 [arXiv:1504.07551].
  * [26] R. S. Gupta, Z. Komargodski, G. Perez, and L. Ubaldi, “Is the Relaxion an Axion?” JHEP 02 (2016) 166 [arXiv:1509.00047].
  * [27] T. Flacke, C. Frugiuele, E. Fuchs, R. S. Gupta, and G. Perez, “Phenomenology of relaxion-Higgs mixing,” JHEP 06 (2017) 050 [arXiv:1610.02025].
  * [28] C. O’Hare, “cajohare/AxionLimits: AxionLimits.” https://cajohare.github.io/AxionLimits/, 2020.  doi:10.5281/zenodo.3932430.
  * [29] P. Carenza, et al., “Improved axion emissivity from a supernova via nucleon-nucleon bremsstrahlung,” JCAP 10 (2019) 016 [arXiv:1906.11844]. [Erratum: JCAP 05, E01 (2020)].
  * [30] N. Bar, K. Blum, and G. D’Amico, “Is there a supernova bound on axions?” Phys. Rev. D 101 (2020) 123025 [arXiv:1907.05020].
  * [31] C. Burrage and J. Sakstein, “A Compendium of Chameleon Constraints,” JCAP 11 (2016) 045 [arXiv:1609.01192].
  * [32] E. Masso and J. Redondo, “Evading astrophysical constraints on axion-like particles,” JCAP 09 (2005) 015 [hep-ph/0504202].
  * [33] J. Jaeckel, E. Masso, J. Redondo, A. Ringwald, and F. Takahashi, “The Need for purely laboratory-based axion-like particle searches,” Phys. Rev. D 75 (2007) 013004 [hep-ph/0610203].
  * [34] W. DeRocco, P. W. Graham, and S. Rajendran, “Exploring the robustness of stellar cooling constraints on light particles,” Phys. Rev. D 102 (2020) 075015 [arXiv:2006.15112].
  * [35] R. Budnik, H. Kim, O. Matsedonskyi, G. Perez, and Y. Soreq, “Probing the relaxed relaxion and Higgs portal scenarios with XENON1T scintillation and ionization data,” Phys. Rev. D 104 (2021) 015012 [arXiv:2006.14568].
  * [36] I. M. Bloch, et al., “Exploring new physics with O(keV) electron recoils in direct detection experiments,” JHEP 01 (2021) 178 [arXiv:2006.14521].
  * [37] P. Escribano and A. Vicente, “Ultralight scalars in leptonic observables,” JHEP 03 (2021) 240 [arXiv:2008.01099].
  * [38] M. J. Dolan, F. J. Hiskens, and R. R. Volkas, “Advancing globular cluster constraints on the axion-photon coupling,” JCAP 10 (2022) 096 [arXiv:2207.03102].
  * [39] B. K. Sahoo, “Improved limits on the hadronic and semihadronic $CP$ violating parameters and role of a dark force carrier in the electric dipole moment of 199Hg,” Phys. Rev. D 95 (2017) 013002 [arXiv:1612.09371].
  * [40] C. Abel et al., “Measurement of the Permanent Electric Dipole Moment of the Neutron,” Phys. Rev. Lett. 124 (2020) 081803 [arXiv:2001.11966].
  * [41] J. M. Pendlebury et al., “Revised experimental upper limit on the electric dipole moment of the neutron,” Phys. Rev. D 92 (2015) 092003 [arXiv:1509.04411].
  * [42] S. Mantry, M. Pitschmann, and M. J. Ramsey-Musolf, “Distinguishing axions from generic light scalars using electric dipole moment and fifth-force experiments,” Phys. Rev. D 90 (2014) 054016 [arXiv:1401.7339].
  * [43] J. Lee, A. Almasi, and M. Romalis, “Improved Limits on Spin-Mass Interactions,” Phys. Rev. Lett. 120 (2018) 161801 [arXiv:1801.02757].
  * [44] T. Jenke, et al., “A quantized frequency reference in the short-ranged gravity potential and its application for dark matter and dark energy searches.” arXiv:1208.3875.
  * [45] K. Tullney et al., “Constraints on Spin-Dependent Short-Range Interaction between Nucleons,” Phys. Rev. Lett. 111 (2013) 100801 [arXiv:1303.6612].
  * [46] M. Guigue, D. Jullien, A. K. Petukhov, and G. Pignol, “Constraining short-range spin-dependent forces with polarized 3He,” Phys. Rev. D 92 (2015) 114001 [arXiv:1511.06993].
  * [47] Y. Feng, D. Ning, S. Zhang, Z. Lu, and D. Sheng, “Search for Monopole-Dipole Interactions at the Submillimeter Range with a Xe129-Xe131-Rb Comagnetometer,” Phys. Rev. Lett. 128 (2022) 231803 [arXiv:2205.13237].
  * [48] S. Alighanbari, G. S. Giri, F. L. Constantin, V. I. Korobov, and S. Schiller, “Precise test of quantum electrodynamics and determination of fundamental constants with HD+ ions,” Nature 581 (2020) 152–158.
  * [49] S. Alighanbari, I. V. Kortunov, G. S. Giri, and S. Schiller, “Test of charged baryon interaction with high-resolution vibrational spectroscopy of molecular hydrogen ions,” Nature Physics 19 (2023) 1263–1269.
  * [50] E. Goudzovski et al., “New physics searches at kaon and hyperon factories,” Rept. Prog. Phys. 86 (2023) 016201 [arXiv:2201.07805].
  * [51] V. V. Nesvizhevsky, G. Pignol, and K. V. Protasov, “Neutron scattering and extra short range interactions,” Phys. Rev. D 77 (2008) 034020 [arXiv:0711.2298].
  * [52] Y. Kamiya, K. Itagami, M. Tani, G. N. Kim, and S. Komamiya, “Constraints on New Gravitylike Forces in the Nanometer Range,” Phys. Rev. Lett. 114 (2015) 161101 [arXiv:1504.02181].
  * [53] C. C. Haddock et al., “Search for deviations from the inverse square law of gravity at nm range using a pulsed neutron beam,” Phys. Rev. D 97 (2018) 062002 [arXiv:1712.02984].
  * [54] M. P. Ledbetter, M. Romalis, and D. F. Jackson-Kimball, “Constraints on short-range spin-dependent interactions from scalar spin-spin coupling in deuterated molecular hydrogen,” Phys. Rev. Lett. 110 (2013) 040402 [arXiv:1203.6894].
  * [55] V. M. Mostepanenko, A. A. Starobinsky, and E. N. Velichko, eds., “The State of the Art in Constraining Axion-to-Nucleon Coupling and Non-Newtonian Gravity from Laboratory Experiments,” Universe 6 (2020) 147 [arXiv:2009.04517].
  * [56] M. Gorghetto, G. Perez, I. Savoray, and Y. Soreq, “Probing CP violation in photon self-interactions with cavities,” JHEP 10 (2021) 056 [arXiv:2103.06298].
  * [57] B. A. Dobrescu and I. Mocioiu, “Spin-dependent macroscopic forces from new particle exchange,” JHEP 11 (2006) 005 [hep-ph/0605342].
  * [58] D. F. Jackson Kimball, “Nuclear spin content and constraints on exotic spin-dependent couplings,” New J. Phys. 17 (2015) 073008 [arXiv:1407.2671].
  * [59] P. Fadeev, et al., “Revisiting spin-dependent forces mediated by new bosons: Potentials in the coordinate-space representation for macroscopic- and atomic-scale experiments,” Phys. Rev. A 99 (2019) 022113 [arXiv:1810.10364].
  * [60] V. V. Flambaum and A. F. Tedesco, “Dependence of nuclear magnetic moments on quark masses and limits on temporal variation of fundamental constants from atomic clock experiments,” Phys. Rev. C 73 (2006) 055501 [nucl-th/0601050].
  * [61] A. N. Petrov, N. S. Mosyagin, T. A. Isaev, and A. V. Titov, “Theoretical study of $\mathrm{Hf}{\mathrm{F}}^{+}$ in search of the electron electric dipole moment,” Phys. Rev. A 76 (2007) 030501.
  * [62] S. V. Khristenko, V. P. Shevelko, and A. I. Maslov, Molecular Structure, pp. 1–19.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1998.
  * [63] B. J. Barker, I. O. Antonov, M. C. Heaven, and K. A. Peterson, “Spectroscopic investigations of ThF and ThF+,” The Journal of Chemical Physics 136 (2012) 104305.
  * [64] L. V. Skripnikov and A. V. Titov, “Theoretical study of ${\mathrm{ThF}}^{+}$ in the search for $T,P$-violation effects: Effective state of a Th atom in ${\mathrm{ThF}}^{+}$ and ThO compounds,” Phys. Rev. A 91 (2015) 042504.
  * [65] K. B. Ng, The ThF+ eEDM experiment: concept, design, and characterization.  Phd thesis, University of Colorado, Boulder, CO, 2024.
  * [66] I. Kozyryev and N. R. Hutzler, “Precision Measurement of Time-Reversal Symmetry Violation with Laser-Cooled Polyatomic Molecules,” Phys. Rev. Lett. 119 (2017) 133002 [arXiv:1705.11020].
  * [67] B. L. Augenbraun, et al., “Laser-Cooled Polyatomic Molecules for Improved Electron Electric Dipole Moment Searches,” New J. Phys. 22 (2020) 022003 [arXiv:1910.11318].
  * [68] Y. V. Stadnik and V. V. Flambaum, “Nuclear spin-dependent interactions: Searches for WIMP, Axion and Topological Defect Dark Matter, and Tests of Fundamental Symmetries,” Eur. Phys. J. C 75 (2015) 110 [arXiv:1408.2184].