# On the privacy of federated Clustering: A Cryptographic View

###### Abstract

The privacy concern in federated clustering has attracted considerable
attention in past decades. Many privacy-preserving clustering algorithms
leverage cryptographic techniques like homomorphic encryption or secure
multiparty computation, to guarantee full privacy, i.e., no additional
information is leaked other than the final output. However, given the
iterative nature of clustering algorithms, consistently encrypting
intermediate outputs, such as centroids, hampers efficiency. This paper delves
into this intricate trade-off, questioning the necessity of continuous
encryption in iterative algorithms. Using the federated K-means clustering as
an example, we mathematically formulate the problem of reconstructing input
private data from the intermediate centroids as a classical cryptographic
problem called hidden subset sum problem (HSSP)– extended from an NP-complete
problem called subset sum problem (SSP). Through an in-depth analysis, we show
that existing lattice-based HSSP attacks fail in reconstructing the private
data given the knowledge of intermediate centroids, thus it is secure to
reveal them for the sake of efficiency. To the best of our knowledge, our work
is the first to cast federated clustering’s privacy concerns as a
cryptographic problem HSSP such that a concrete and rigorous analysis can be
conducted.

Index Terms—  Privacy, federated learning, lattice attack, K-means clustering,
hidden subset sum problem

##  1 Introduction

Clustering is a popular unsupervised learning technique that plays a crucial
role in data processing and analysis. By categorizing data into subgroups with
similar properties, it provides a powerful means to discover hidden patterns
and group similar entities. While clustering techniques are effective, their
full potential can only be harnessed when they are applied to comprehensive
data sets. In the age of digitalization, datasets often reside across
multiple, distributed databases. Federated clustering addresses this challenge
by operating directly on decentralized nodes, with each retaining a fragment
of the overall dataset [1]. However, as data becomes more dispersed, so do
concerns about its privacy. The process of clustering, even in a federated
setup, poses potential risks of revealing sensitive information. For instance,
for certain small or distinct clusters, individual entities might be
identifiable. Thus, there is an emerging need for privacy-preserving
clustering, which not only allows for decentralized data pattern discovery but
also ensures that individual data points remain confidential.

Existing privacy-preserving federated clustering predominantly fall under two
categories: differential privacy (DP) approaches which insert noise to achieve
a rigorous privacy guarantee [2, 3, 4] and secure computation approaches [5,
6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] which employ cryptographic tools such
as homomorphic encryption (HE) [17] or secure multiparty computation (SMPC)
[18] to allow computation among distrust parties. Typically, DP-based
approaches compromise utility for privacy while secure computation requires
higher complexity. Comprehensive surveys of these approaches can be found in
[19, 20].

In the realm of clustering algorithms, except the private data, intermediate
outputs such as cluster centroids, cluster assignments, and cluster sizes,
emerge potential privacy risks. As highlighted in [20], it is very difficult
to concretely determine whether leaking intermediate information would breach
privacy or not, thus it is better to ensure full privacy, i.e., no information
can be leaked except what the final output. However, full privacy incurs very
high complexities as it requires protection for each and every update over the
whole iterative process, thereby hindering efficiency and scalability. This
has spurred the exploration of alternative approaches that improve efficiency
by allowing disclosure of some intermediate data, such as cluster centroids
[9, 10, 11, 12, 13, 14] or the cluster assignments [15, 16]. This raises an
imperative question: Is there an inevitable trade-off between privacy and
efficiency? Moreover, does the disclosure of intermediate updates gravely
jeopardize privacy? To answer these questions, one of the fundamental
challenges stems from the intricacies involved in quantitatively assessing the
privacy effect of such disclosures. In this paper, we take the first step to
conduct a rigorous analysis of this problem in the context of federated
K-means clustering. Our main contributions are summarized as follows:

  * •

We analyze the privacy effect of revealing intermediate centroids in federated
K-means clustering and mathematically formulate it a cryptographic problem
known as HSSP. To the best of our knowledge, this is the first work in this
context.

  * •

With the lattice-based tools tailored for HSSP, we demonstrate a rigorous
analysis of the privacy effect. Our findings show that it is very difficult
for the adversary to reconstruct the private data given intermediate
centroids. This suggests that disclosing intermediate centroids might not
inherently jeopardize privacy, thus suggesting that efficiency may not need to
sacrifice privacy.

##  2 Preliminaries

This section reviews necessary fundamentals for the rest of the paper.

###  2.1 Federated K-means clustering

In a federated setting with $n$ nodes/agents/participants, each and every node
of them, denote by $i$, possesses private data $x_{i}$111For simplicity, we
assume $x_{i}$ is a scalar and the results can easily be generalized to
arbitrary dimensions.. The goal of federated K-means clustering is to
partition the private data $x_{i}$’s of all nodes into K clusters, the cluster
labels are denoted by $\mathcal{K}=\\{1,2,...,k\\}$, with each cluster being
represented by its center $\mu_{j},j\in\mathcal{K}$. Let $l_{i}^{(t)}$ denote
the cluster index of node $i$ at iteration $t$, and $\mu_{j}^{(t)}$ denote the
center of the $j$-th cluster. Let $t_{\max}$ denote the maximum number of
iterations and $\mathcal{T}=\\{1,2,\ldots,t_{\max}\\}$. For each iteration
$t\in\mathcal{T}$, federated K-means clustering consists of two steps:

1) Local cluster assignment: Every node computes locally, determining which
cluster it belongs to based on the distance to the current centroids:

$\displaystyle
l_{i}^{(t)}=\arg\min_{j}\|x_{i}-\mu_{j}^{(t)})\|_{2}^{2},j\in\mathcal{K},$ (1)

where $\|\cdot\|_{2}$ denotes the Euclidean norm. For notation simplicity, we
will omit the subscript in subsequent discussions.

2) Centroid aggregation: Each node computes its local centroid update. These
local updates are then sent to a central coordinator to update the global
centroids:

$\displaystyle\mu_{j}^{(t+1)}=\frac{1}{n_{j}}\sum_{x_{i}\in{\cal
C}_{j}^{(t)}}x_{i},j\in\mathcal{K},$ (2)

where ${\cal C}_{j}^{(t)}=\\{x_{i}|l_{i}^{(t)}=j\\}$ denotes the set of all
data points within the $j$-th cluster at the $t$-th iteration. The size of
this set is given by $n_{j}=|{\cal C}_{j}^{(t)}|$.

###  2.2 Threat model

We assume that the central server is semi-honest (also known as passive or
honest-but-curious), it would not change the model parameters maliciously but
it can collect information through the learning process. Assume the central
server only has the knowledge of all intermediate centroids, its goal is to
reconstruct the input data samples given the available information.

###  2.3 Hidden subset sum problem

We now introduce two classical cryptographic problems that are closely related
to federated K-means clustering, as we will show later.

######  Definition 1.

Subset Sum Problem (SSP) Let $n$ be an integer. Given
$x_{1},\ldots,x_{n}\in\mathbb{Z}$ and $t\in\mathbb{Z}$, compute
$a_{1},\ldots,a_{n}\in\\{0,1\\}$ such that

$t=a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}$

if they exist.

Note that SSP is a well-known NP-complete problem, thus currently it is
unknown if a deterministic polynomial algorithm exists [21].

######  Definition 2.

Hidden Subset Sum Problem (HSSP) Let $Q$ be an integer, and let
$x_{1},\ldots,x_{n}$ be integers in $\mathbb{Z}_{Q}$. Let
$\bm{a}_{1},\ldots,\bm{a}_{n}\in\mathbb{Z}^{m}$ be vectors with components in
$\\{0,1\\}$. Let $\bm{h}=\left(h_{1},\ldots,h_{m}\right)\in$ $\mathbb{Z}^{m}$
satisfying:

$\displaystyle\bm{h}=\bm{a}_{1}x_{1}+\bm{a}_{2}x_{2}+\cdots+\bm{a}_{n}x_{n}\quad(\bmod~{}Q)$
(3)

Given the modulus $Q$ and the sample vector $\bm{h}$, recover the vector
$\bm{x}=\left(x_{1},\ldots,x_{n}\right)$ and the vectors $\bm{a}_{i}$’s, up to
a permutation of the $x_{i}$’s and $\bm{a}_{i}$’s.

We note that HSSP is an extension of SSP, as in SSP, only the weights
$a_{i}$’s are hidden. While in HSSP, both the mixturing weights $\bm{a}_{i}$
’s and input $x_{i}$ ’s are hidden. In fact, it is shown that, under certain
parameter settings, an HSSP-solver could be used to attack SSP [22], e.g.,
when an HSSP instance having a unique solution can be generated, solving such
HSSP is sufficient for solving SSP.

##  3 Lattice-based HSSP attacks

In this section, we will first introduce the necessary fundamentals of
lattices and then introduce the Nguyen-Stern attack (NS attack), which is the
very first HSSP attack raised by Nguyen and Stern [23]. Note that there are
also two improved attacks based on NS attack, we refer readers to [24, 25] for
more details.

###  3.1 Fundamentals of lattices

A lattice is a discrete subgroup of $\mathbb{R}^{m}$, which can be defined as
follows [26].

######  Definition 3.

Lattice Given $n$ linearly independent vectors $\bm{b}_{1},\dots,\bm{b}_{n}$
in $\mathbb{R}^{m}$, the lattice generated by the basis
$\bm{b}_{1},\dots,\bm{b}_{n}$ is defined as the set

$\mathcal{L}(\bm{b}_{1},\dots,\bm{b}_{n})=\left\\{\sum_{i=1}^{n}x_{i}\bm{b}_{i}|x_{i}\in\mathbb{Z},i=1,\dots,n\right\\},$

where $m$ denotes the dimension of the lattice $\mathcal{L}$, denoted as
$\dim(\mathcal{L})$ and $n$ denotes its rank. In this paper, we generally
consider integer lattices, i.e., the lattices belonging to $\mathbb{Z}^{m}$.

######  Definition 4.

Orthogonal lattice Let $\mathcal{L}\subseteq\mathbb{Z}^{m}$ be a lattice. Its
orthogonal lattice is given as

$\mathcal{L}^{\bot}:=\\{\bm{y}\in\mathbb{Z}^{m}\arrowvert\forall\bm{x}\in\mathcal{L},\langle\bm{x},\bm{y}\rangle=0\\},$

where $\langle\ ,\ \rangle$ is the inner product of $\mathbb{R}^{m}$. Its
orthogonal lattice modulo $Q$ is given as

$\mathcal{L}_{Q}^{\bot}:=\\{\bm{y}\in\mathbb{Z}^{m}\arrowvert\forall\bm{x}\in\mathcal{L},\langle\bm{x},\bm{y}\rangle\equiv
0\mod Q\\}.$

Note that $(\mathcal{L}^{\bot})^{\bot}$ contains the original lattice
$\mathcal{L}$.

The so-called LLL and BKZ algorithms are important building blocks for
designing HSSP attacks. A brief introduction about them is given as follows:

  * •

LLL: The LLL algorithm [27] is a polynomial time lattice reduction algorithm
with a basis of a lattice $\mathcal{L}$ as input and output a basis which is
LLL-reduced, meaning that the basis is short and nearly orthogonal.

  * •

BKZ: The BKZ algorithm [28] is also a lattice reduction algorithm. Increasing
the block-size parameter of the algorithm improves the accuracy, at the cost
of a longer computation time. Namely, BKZ-2 can produce an LLL-reduced basis
in polynomial time, while with full block-size one can retrieve the shortest
vector of the lattice in exponential time.

###  3.2 NS attack

The whole process of the NS attack could be divided into two steps:

  * •

Step 1: The first step is based on orthogonal lattice attack. As the only
known information in (3) is $\bm{h}$, the orthogonal lattice attack starts
with computing the orthogonal lattice of $\bm{h}$ modulus $Q$, i.e.,
$\mathcal{L}_{Q}^{\bot}(\mathbf{h})$. As $\bm{h}$ is a linear combination of
the hidden weight vectors $\\{\bm{a}_{i}\\}_{i=1}^{n}$, the orthogonal lattice
of $\bm{A}$, i.e., $\mathcal{L}^{\bot}(\bm{A})$, is then contained in
$\mathcal{L}_{Q}^{\bot}(\mathbf{h})$. Based on the fact that $\bm{a}_{i}$’s
are binary, the goal is to ensure the first $m-n$ short vectors of the LLL
basis of $\mathcal{L}_{Q}^{\bot}(\mathbf{h})$ form a basis of
$\mathcal{L}^{\bot}(\bm{A})$. After obtaining $\mathcal{L}^{\bot}(\bm{A})$,
then compute its orthogonal $(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$ using the
LLL algorithm again, as $(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$ contains our
target lattice $\mathcal{L}(\bm{A})$. Note that the LLL algorithm is applied
twice. The first time is to compute the LLL-reduced basis of
$\mathcal{L}^{\bot}_{Q}(\bm{h})$; the second time is to compute the orthogonal
lattice of $\mathcal{L}^{\bot}(\bm{A})$ [29, 30].

  * •

Step 2: The second step is to recover the binary vectors $\bm{a}_{i}$’s from a
LLL-reduced basis of $(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$, after that the
hidden private data vector $\bm{x}$ can then be recovered. Since the short
vectors found by Step 1 may not be short enough, thus the BKZ algorithm is
applied in Step 2 to find shorter vectors. Denote $\\{\bm{v}_{i}\\}_{i=1}^{n}$
as the obtained short vectors in $(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$. Assume
that the $\bm{a}_{i}$’s are the only binary vectors in
$(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$, it could be proved with high
possibility that $\bm{v}_{i}$’s are either $\bm{a}_{i}$’s or
$\\{\bm{a}_{i}-\bm{a}_{j}\\}$’s. Thus, take $n$ binary vectors in
$\mathcal{L}(\\{\bm{v}_{i}\\}_{i=1}^{n})$ as $\bm{a}_{i}$’s. After obtaining
$\bm{A}$, pick up a $n\times n$ sub-matrix $\bm{A}^{\prime}$ from $\bm{A}$
with non-zero determinant modulus $Q$. Then
$\bm{A}^{\prime}\cdot\bm{x}\equiv\bm{h}^{\prime}\mod Q$. Hence, the hidden
private data can be recovered as
$\bm{x}\equiv\bm{A}^{\prime-1}\bm{h}^{\prime}\mod Q.$

|  Random instance of HSSP:$~{}\bm{h}=\bm{A}\bm{x}$ |  K-means instance of HSSP:$~{}\bm{c}=\bm{W}\bm{x}$
---|---|---
Adversary’s knowledge | $\bm{h}=\bm{a}_{1}x_{1}+\ldots+\bm{a}_{n}x_{n}\in\mathbb{Z}^{m}_{Q}$ | $\bm{c}=\bm{w}_{1}x_{1}+\ldots+\bm{w}_{n}x_{n}\in\mathbb{R}^{m}$
Hidden private data | $\bm{x}\in\mathbb{Z}^{n}_{Q}$ | $\bm{x}\in\mathbb{R}^{n}$
Hidden weight matrix | $\bm{A}\in\\{0,1\\}^{m\times n}$ | $\bm{W}\in\\{0,1\\}^{m\times n}$
$\operatorname{Rank}(\bm{A})=n$ | $\operatorname{Rank}(\bm{W})\leq n$
$\mathbb{E}(\|\bm{a}_{i}\|_{1})=\frac{m}{2}$ | $\|\bm{w}_{i}\|_{1}=\frac{m}{k}$
Short vectors | $\\{\bm{v}_{i}\\}_{i=1}^{n}\subset(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$ | $\\{\bm{u}_{i}\\}_{i=1}^{n}\subset(\mathcal{L}^{\bot}(\bm{W}))^{\bot}$
Recovered binary vectors | $\\{\hat{\bm{v}}_{i}\\}\subset\mathcal{L}(\\{\bm{v}_{i}\\}_{i=1}^{n})\cap\\{0,1\\}^{m}$ | $\\{\hat{\bm{u}}_{i}\\}\subset\mathcal{L}(\\{\bm{u}_{i}\\}_{i=1}^{n})\cap\\{0,1\\}^{m}$
Attack result | $\\{\bm{a}_{i}\\}_{i=1}^{n}\cap\\{\hat{\bm{v}}_{i}\\}=\\{\bm{a}_{i}\\}_{i=1}^{n}$ | $\\{\bm{w}_{i}\\}_{i=1}^{n}\cap\\{\hat{\bm{u}}_{i}\\}=\emptyset$
Table 1: Comparisons of random instances and K-means instances of HSSP in
terms of a number of key properties.

##  4 Analysis of NS attack in Federated K-means clustering

We now delve into the above-described NS attack, focusing on its application
in federated K-means clustering. We will show that given the knowledge of the
intermediate clustering centers $\bm{c}$ in (6), existing HSSP attacks are
likely to fail in recovering the hidden private data $x_{i}$’s. This
limitation predominantly stems from the fact that existing HSSP attacks
require certain assumptions on the characteristics of the hidden weight
vectors. However, such assumption is not satisfied in Federated K-means
clustering.

###  4.1 Privacy of federated K-means clustering as a HSSP

We first characterize (2) with the following representation:

$\displaystyle\forall j\in\mathcal{K}:c_{j}^{(t+1)}=\bm{w}_{j}^{(t)}\bm{x}$
(4)

where $\\{\bm{w}_{j}^{(t)}\in\\{0,1\\}^{1\times
n}\\}_{t\in\mathcal{T},j\in\mathcal{K}}$ is referred to as the weight vector
characterizing the node selection process, i.e., the $i$-th entry of
$\bm{w}_{j}^{(t)}$ is set to $1$ if node $i$ is assigned to cluster $j$, i.e.,
$l_{i}^{(t)}=j$, otherwise it is zero. $c_{j}^{(t+1)}$ is the sum of all
$x_{i}$’s assigned to cluster $j$. Note that revealing the sum $c_{j}^{(t+1)}$
can provide more information (and hence be riskier) than revealing the average
$\mu_{j}^{(t+1)}$. This is because if an adversary knows the number of
samples, it can compute the average from the sum, but the reverse isn’t
necessarily true. Given this, in what follows we will focus on
$c_{j}^{(t+1)}$’s and show that even with the knowledge of these values, the
private data is protected. Stacking the observed information across all
clusters and all iterations, i.e.,
$\\{c_{j}^{(t)}\\}_{t\in\mathcal{T},j\in\mathcal{K}}$ together we obtain

$\displaystyle\begin{bmatrix}c_{1}^{(1)}\\\ \vdots\\\
c_{k}^{(t_{\max})}\end{bmatrix}=\begin{bmatrix}\bm{w}_{1}^{(1)}\\\ \vdots\\\
\bm{w}_{k}^{(t_{\max})}\end{bmatrix}\begin{bmatrix}x_{1}\\\ \vdots\\\
x_{n}\end{bmatrix},$ (5)

Further define
$\bm{c}=[c_{1}^{(1)},\ldots,c_{k}^{(t_{\max})}]^{T}\in\mathbb{R}^{kt_{\max}}$,
$\bm{W}=[\bm{w}_{1}^{(1),T},\\\
\ldots,\bm{w}_{k}^{(t_{\max}),T}]^{T}\in\\{0,1\\}^{kt_{\max}\times n}$ and
$\bm{x}=[x_{1},x_{2},...,x_{n}]^{T}\in\mathbb{R}^{n}$. The above becomes

$\displaystyle\bm{c}=\bm{W}\bm{x}$ (6)

The problem then becomes _Given the knowledge of $\bm{c}$ in (6), can the
adversary recover the hidden private data $x_{i}$’s?_

###  4.2 Random instances of HSSP

Existing HSSP solvers predominantly focus on what is termed ’ random instances
of HSSP’ [23, 24, 25, 31], which is defined as

######  Definition 5.

A random instance of HSSP Let $x_{1},\ldots,x_{n}$ be integers sampled
uniformly at random in $\mathbb{Z}_{Q}$ and
$\bm{a}_{1},\ldots,\bm{a}_{n}\in\mathbb{Z}^{m}$ be vectors with independent
entries sampled uniformly over $\\{0,1\\}$. They satisfy (3) and the goal is
to recover the hidden $x_{i}$’s and $\bm{a}_{i}$’s given $Q$ and $\bm{h}$,
according to Definition 2.

A direct implication of the above definition is that the statistical
expectation of the $L_{1}$ norm of each $\bm{a}_{i}$ should be $m/2$, i.e.,
$\forall~{}i=\\{1,\ldots,n\\}:~{}\mathbb{E}(\|\bm{a}_{i}\|_{1})=m/2$ where
$\|\bm{\cdot}\|_{1}$ denotes $L_{1}$ norm.

Recall that it is explicitly stated in Step 2 of Section 3.2: _Assume that the
$\bm{a}_{i}$’s are the only binary vectors in
$(\mathcal{L}^{\bot}(\bm{A}))^{\bot}$, it could be proved with a high
possibility that $\bm{v}_{i}$’s are either $\bm{a}_{i}$’s or
$\\{\bm{a}_{i}-\bm{a}_{j}\\}$’s._ We now explain in detail why $\bm{v}_{i}$’s
are likely to be the target hidden weight vectors $\bm{a}_{i}$’s themselves or
a linear combination of two of them. The main reason stems from the fact that
the probability, of using linear combination of over two vectors in
$\\{\bm{a}_{i}\\}$ to construct a vector in $\\{-1,0,1\\}^{m}$, is very low.
Take the linear combination of three vectors as an example, the following
result holds [22].

######  Proposition 1.

Let $\\{\bm{a}_{1},\bm{a}_{2},\ldots,\bm{a}_{n}\\}$ be a set of $n$ binary
vectors with dimension $m$ and all entries has equal probability being $0$ or
$1$, i.e., $\bm{a}_{i}\in\\{0,1\\}^{m}$ and
$\mathbb{E}(\|\bm{a}_{i}\|_{1})=m/2$. Take three vectors
$\bm{a}_{i},\bm{a}_{j},\bm{a}_{k}$ and denote
$\bm{v}=\bm{a}_{i}+\bm{a}_{j}-\bm{a}_{k}$ as a linear combination of them.
Thus, the probability that $\bm{v}\in\\{-1,0,1\\}^{m}$ is given by

$\displaystyle\operatorname{Pr}\big{(}\bm{v}\in\\{-1,0,1\\}^{m}\big{)}=(\frac{7}{8})^{m}$
(7)

For a small $\epsilon\in(0,1)$, a sufficient condition to guarantee the
expectation of $\bm{v}\in\\{-1,0,1\\}^{m}$ is less than $\epsilon$ is given by

$\displaystyle m\geq 16\log n-6\log\epsilon.$ (8)

###### Proof.

Since all elements in $\bm{a}_{i}$’s are either $0$ or $1$, each with $1/2$
probability, for an arbitrary element in $\bm{v}$, it is of probability $7/8$
that it belongs to $\\{-1,0,1\\}$. As $\bm{v}$ is of length $m$, the
probability of $\bm{v}\in\\{-1,0,1\\}^{m}$ is thus $(\frac{7}{8})^{m}$. Since
there are at most $n^{3}$ triplets of
$\\{\bm{a}_{i},\bm{a}_{j},\bm{a}_{k}\\}$’s, to guarantee
$n^{3}(\frac{7}{8})^{m}<\epsilon$ it requires $3\log
n+m(\log(\frac{7}{8}))<\log\epsilon\rightarrow m>(-3\log
n+\log\epsilon)/\log(\frac{7}{8})$. As $-3/(\log\frac{7}{8})<16$ and
$1/(\log\frac{7}{8})>-6$ thus (8) holds. ∎

Thus, it is of high probability that $\bm{v}_{i}$’s are either $\bm{a}_{i}$’s
or $\\{\bm{a}_{i}-\bm{a}_{j}\\}$’s. Conversely, $\bm{a}_{i}$’s can be
determined using linear combinations of $\bm{v}_{i}$’s combined with the fact
that $\bm{a}_{i}$ is binary. This can be formulated as the intersection
$\mathcal{L}(\\{\bm{v}_{i}\\}_{i=1}^{n})\cap\\{0,1\\}^{m}$. Hence, we conclude
that if $\bm{a}_{i}$ follows Definition 5, it is of high probability that

$\displaystyle\\{\bm{a}_{i}\\}_{i=1}^{n}\cap\mathcal{L}(\\{\bm{v}_{i}\\}_{i=1}^{n})\cap\\{0,1\\}^{m}=\\{\bm{a}_{i}\\}_{i=1}^{n}.$
(9)

(a) Number of recovered binary vectors: $\hat{\bm{u}}_{i}$ and
$\hat{\bm{v}}_{i}$

(b) Averaged $L_{1}$ norm of $\|\hat{\bm{u}}_{i}\|_{1}$,
$\|\hat{\bm{v}}_{i}\|_{1}$ and corresponding true vectors
$\|\bm{w}_{i}\|_{1}$, $\|\bm{a}_{i}\|_{1}$

(c) Number of true vectors among recovered vectors:
$|\\{\hat{\bm{u}}_{i}\\}\cap\\{\bm{w}_{i}\\}|$ and
$|\\{\hat{\bm{v}}_{i}\\}\cap\\{\bm{a}_{i}\\}|$

Fig. 1: Comparisons of random instance and K-means instance of HSSP in terms
of three properties over 100 Monte Carlo runs.

###  4.3 K-means instances of HSSP

Compare (6) in K-means clustering to (3), we can see that the input private
data $x_{i}$’s in the former are real numbers while in the latter they are
defined within the modular ring $\mathbb{Z}_{Q}$. However, this discrepancy
can be addressed by transforming $x_{i}$ into $\mathbb{Z}_{Q}$, where floating
points can be scaled to integers and the modulo additive inverse can be used
for representing negative numbers. The modulo operation will not make a
difference if a sufficiently large $Q$ is considered. We now proceed to
discuss the property of the weight matrix $\bm{W}\in\\{0,1\\}^{m\times n}$
(assuming $m=kt_{\max}$) in K-means clustering. Let
$\bm{w}_{1},\ldots,\bm{w}_{n}$ denote the column vectors of $\bm{W}$. Given
that each element in $\bm{w}_{i}$ signifies whether the $i$-th input sample
$x_{i}$ is grouped into the corresponding cluster or not, if two samples say
$x_{i}$ and $x_{j}$ belong to the same cluster at the end of the iteration
process, it’s unlikely that their cluster assignments would frequently
oscillate during the execution of the algorithm. Such result will enforce the
following property of the corresponding $\bm{w}_{i}$ and $\bm{w}_{j}$:

$\displaystyle\|\bm{w}_{i}-\bm{w}_{j}\|_{1}\ll m/k.$ (10)

This essentially suggests that the differences in the cluster assignments
across all iterations are generally much less than the average length of
cluster assignments.

Due to the nature of clustering, the number of clusters is typically much
smaller than the number of samples being grouped. Thus, there will be numerous
pairs satisfying (10). A direct implication is that $\bm{W}$ is likely to be
rank deficient because of dependencies between $\bm{w}_{i}$’s. We define the
K-means variant of HSSP as follows:

######  Definition 6.

A K-means instance of HSSP Let $x_{1},\ldots,x_{n}$ be independently integers
sampled in $\mathbb{Z}_{Q}$. Let $k$ denote the number of clusters and
$\bm{w}_{1},\ldots,\bm{w}_{n}\in\\{0,1\\}^{m}$ be vectors satisfying
$\|\bm{w}_{i}\|_{1}=m/k$. They satisfy (6) and there exists a number of pairs
$\bm{w}_{i}$ and $\bm{w}_{j}$ satisfying (10). The goal is to recover the
hidden $x_{i}$’s and $\bm{w}_{i}$’s given $\bm{c}$, according to Definition 2.

Let $\\{\bm{u}_{i}\\}_{i=1}^{n}$ be the short vectors of
$(\mathcal{L}^{\bot}(\bm{W}))^{\bot}$ founded by the BKZ algorithm. We note
that it is of high probability that

$\displaystyle\\{\bm{w}_{i}\\}_{i=1}^{n}\cap\mathcal{L}(\\{\bm{u}_{i}\\}_{i=1}^{n})\cap\\{0,1\\}^{m}=\emptyset.$
(11)

The rationale is described as follows: since
$\mathcal{L}(\bm{W})\subseteq(\mathcal{L}^{\bot}(\bm{W}))^{\bot}$, it follows
that for any pair of $i$ and $j$ where $i\neq j$,
$\bm{w}_{i}-\bm{w}_{j}\in(\mathcal{L}^{\bot}(\bm{W}))^{\bot}$. For those pairs
$(\bm{w}_{i},\bm{w}_{j})$ satisfying (10), the lengths of
$\bm{w}_{i}-\bm{w}_{j}$ and some of their linear combinations will be shorter
than $\\{\bm{w}_{i}\\}_{i=1}^{n}$. This essentially indicates that there’s a
plethora of binary vectors within the lattice
$\mathcal{L}(\\{\bm{u}_{i}\\}_{i=1}^{n})$ that are shorter than
$\\{\bm{w}_{i}\\}_{i=1}^{n}$, i.e., (11) will hold with high probability. In
the coming section, we will give empirical validations to substantiate this
claim.

To have a clear overview of random instances and K-means instances of HSSP, we
summarize their key properties in Tab. 1.

##  5 Experimental validations and discussions

We now proceed to consolidate our results with experimental validations. We
deploy the widely used Iris dataset which comprises 150 samples, each has four
attributes and there are three categories of flower types [32]. We set the
number of clusters $k=3$ and the maximum iteration number as 100. Fig. 1
demonstrates the attack results of both random instances and K-means instances
of HSSP over 100 Monte Carlo runs. In each experiment, we randomly subsample
$n=10$ samples and $m=60$ observations from the obtained centroids data to
ensure the feasibility of completing 100 Monte Carlo runs. By inspecting plots
(a) and (b) we can see that in the K-means case, the algorithm identifies
numerous short binary vectors but unfortunately their $L_{1}$ norm often
deviates from the true length $m/3$ given $k=3$. In contrast, in the random
instance of HSSP, the $L_{1}$ norm of discovered short binary vectors
$\bm{v}_{i}$ aligns well with the expected value $m/2$. Consequently, the
number of true recovered vectors in the K-means case is often zero out of a
total of $n=10$. On the other hand, for the case of the random instance, a
consistent full recovery is observed, as emphasized in plot (c). Hence, the
results in (9) and (11) are empirically verified, confirming our claim that
_given the knowledge of the intermediate centroids, NS attack is not able to
the hidden weight vector $\bm{w}_{i}$’s, thus also private data $x_{i}$’s_.

Two remarks are in place here. Firstly, the attack results of the other two
HSSP attacks [24, 25] will also fail in recovering the true hidden vector
$\bm{w}_{i}$’s as there exist lots of false positive binary vectors which are
more readily recoverable than the true ones. Secondly, even if $\bm{w}_{i}$’s
are successfully recovered, it is still difficult for the adversary to
determine what is the true private data $x_{i}$’s. This is because there will
be infinitely many solutions of $x_{i}$’s given that the hidden weight matrix
$\bm{W}$ is rank-deficient. Hence, overall we conclude that given the
knowledge of all intermediate centroids it is infeasible for the adversary to
reconstruct the private data $x_{i}$’s.

##  6 Conclusion

In this paper we delved deep into the privacy implications of revealing
intermediate centroids in federated K-means clustering. Our novel approach
casts this privacy challenge within a cryptographic lens, specifically the
hidden subset sum problem (HSSP). Our rigorous analysis suggests that
adversaries are unlikely to reconstruct private data given intermediate
centroids, which implies their disclosure might not breach privacy. This
insight potentially paves the way for efficient federated clustering
algorithms without compromising privacy.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proc. Int. Conf. Artif. Intell. Statist._ PMLR, 2017, pp. 1273–1282.
  * [2] U. Stemmer, “Locally private k-means clustering,” _The Journal of Machine Learning Research_ , vol. 22, no. 1, pp. 7964–7993, 2021.
  * [3] M.-F. Balcan, T. Dick, Y. Liang, W. Mou, and H. Zhang, “Differentially private clustering in high-dimensional euclidean spaces,” in _International Conference on Machine Learning_. PMLR, 2017, pp. 322–331.
  * [4] D. Su, J. Cao, N. Li, E. Bertino, M. Lyu, and H. Jin, “Differentially private k-means clustering and a hybrid approach to private optimization,” _ACM Transactions on Privacy and Security (TOPS)_ , vol. 20, no. 4, pp. 1–33, 2017.
  * [5] P. Bunn and R. Ostrovsky, “Secure two-party k-means clustering,” in _Proceedings of the 14th ACM conference on Computer and communications security_. ACM, 2007, pp. 486–497.
  * [6] P. Mohassel, M. Rosulek, and N. Trieu, “Practical privacy-preserving k-means clustering,” _Cryptology ePrint Archive_ , 2019.
  * [7] H.-J. Kim and J.-W. Chang, “A privacy-preserving k-means clustering algorithm using secure comparison protocol and density-based center point selection,” in _2018 IEEE 11th International Conference on Cloud Computing (CLOUD)_. IEEE, 2018, pp. 928–931.
  * [8] X. Meng, D. Papadopoulos, A. Oprea, and N. Triandopoulos, “Private two-party cluster analysis made formal & scalable,” _arXiv preprint arXiv:1904.04475 v2_ , 2019.
  * [9] S. Jha, L. Kruger, and P. McDaniel, “Privacy preserving clustering,” in _European Symposium on Research in Computer Security_. Springer, 2005, pp. 397–417.
  * [10] Z. Erkin, T. Veugen, T. Toft, and R. L. Lagendijk, “Privacy-preserving user clustering in a social network,” in _2009 First IEEE International Workshop on Information Forensics and Security (WIFS)_. IEEE, 2009, pp. 96–100.
  * [11] S. Samet, A. Miri, and L. Orozco-Barbosa, “Privacy preserving k-means clustering in multi-party environment.” in _SECRYPT_ , 2007, pp. 381–385.
  * [12] D. Liu, E. Bertino, and X. Yi, “Privacy of outsourced k-means clustering,” in _Proceedings of the 9th ACM symposium on Information, computer and communications security_ , 2014, pp. 123–134.
  * [13] Z. L. Jiang, N. Guo, Y. Jin, J. Lv, Y. Wu, Z. Liu, J. Fang, S.-M. Yiu, and X. Wang, “Efficient two-party privacy-preserving collaborative k-means clustering protocol supporting both storage and computation outsourcing,” _Information Sciences_ , vol. 518, pp. 168–180, 2020.
  * [14] Q. Li, J. S. Gundersen, K. Tjell, R. Wisniewski, and M. G. Christensen, “Privacy-preserving distributed expectation maximization for gaussian mixture model using subspace perturbation,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 4263–4267.
  * [15] J. Sakuma and S. Kobayashi, “Large-scale k-means clustering with user-centric privacy-preservation,” _Knowledge and Information Systems_ , vol. 25, no. 2, pp. 253–279, 2010.
  * [16] J. Yuan and Y. Tian, “Practical privacy-preserving mapreduce based k-means clustering over large-scale dataset,” _IEEE transactions on cloud computing_ , vol. 7, no. 2, pp. 568–579, 2017.
  * [17] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in _EUROCRYPT, pp. 223–238_ , 1999.
  * [18] R. Cramer, I. B. Damgrd, and J. B. Nielsen, _Secure Multiparty Computation and Secret Sharing_ , 1st ed. New York, NY, USA: Cambridge University Press, 2015.
  * [19] F. Meskine and S. N. Bahloul, “Privacy preserving k-means clustering: a survey research.” _Int. Arab J. Inf. Technol._ , vol. 9, no. 2, pp. 194–200, 2012.
  * [20] A. Hegde, H. Möllering, T. Schneider, and H. Yalame, “Sok: Efficient privacy-preserving clustering,” _Cryptology ePrint Archive_ , 2021.
  * [21] S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, _Algorithms_. McGraw-Hill Higher Education New York, 2008.
  * [22] A. Gini, “On the hardness of the hidden subset sum problem: algebraic and statistical attacks,” Ph.D. dissertation, University of Luxembourg, Luxembourg, 2022.
  * [23] P. Nguyen and J. Stern, “The hardness of the hidden subset sum problem and its cryptographic implications,” in _Crypto_ , vol. 99. Springer, 1999, pp. 31–46.
  * [24] J. Coron and A. Gini, “A polynomial-time algorithm for solving the hidden subset sum problem,” in _Advances in Cryptology–CRYPTO 2020_. Springer, 2020, pp. 3–31.
  * [25] ——, “Provably solving the hidden subset sum problem via statistical learning,” _Mathematical Cryptology_ , vol. 1, no. 2, pp. 70–84, 2021.
  * [26] J. Cassels, _An introduction to the geometry of numbers (Reprint)_ , ser. Classics in mathematics. Springer-Verlag, Berlin, 1997.
  * [27] A. Lenstra, H. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” _Mathematische annalen_ , vol. 261, no. ARTICLE, pp. 515–534, 1982.
  * [28] Y. Chen and P. Nguyen, “Bkz 2.0: Better lattice security estimates,” in _Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17_. Springer, 2011, pp. 1–20.
  * [29] P. Nguyen and J. Stern, “Merkle-hellman revisited: a cryptanalysis of the qu-vanstone cryptosystem based on group factorizations,” in _Advances in Cryptology—CRYPTO’97: 17th Annual International Cryptology Conference Santa Barbara, California, USA August 17–21, 1997 Proceedings_. Springer, 2006, pp. 198–212.
  * [30] J. Chen, D. Stehlé, and G. Villard, “Computing an lll-reduced basis of the orthogonal latice,” in _Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation_ , 2018, pp. 127–133.
  * [31] V. Lyubashevsky, A. Palacio, and G. Segev, “Public-key cryptographic primitives provably as secure as subset sum,” in _Theory of Cryptography Conference_. Springer, 2010, pp. 382–400.
  * [32] R. A. Fisher, “The use of multiple measurements in taxonomic problems,” _Annals of Eugenics_ , vol. 7, no. 2, pp. 179–188, 1936.


# Shape Entropy of a Reconfigurable “Isigami” Surface

Benjamin N. Katz<EMAIL_ADDRESS>Pennsylvania State University  Lev Krainov
<EMAIL_ADDRESS>Pennsylvania State University  Vincent Crespi<EMAIL_ADDRESS>Pennsylvania State University

(August 28, 2024)

###### Abstract

Disclinations in a 2D sheet create regions of Gaussian curvature whose
inversion produces a reconfigurable surface with many distinct metastable
shapes, as shown by molecular dynamics of a disclinated graphene monolayer.
This material has a near-Gaussian “density of shapes” and an effectively
antiferromagnetic interaction between adjacent cones. A $\sim$10 nm patch has
hundreds of distinct metastable shapes with tunable stability and topography
on the size scale of biomolecules. As every conical disclination provides an
Ising-like degree of freedom, we call this technique Isigami.

###### pacs:

61.48.-c, 62.25.-g, 68.55.Jk, 68.65.Pq

††preprint: APS/123-QED

Techniques arising from papercraft – origami and kirigami – inspire efforts to
impart three-dimensional shapes to two-dimensional materials [1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13]. Origami and kirigami both work by imposing one-
dimensional modifications (folds or cuts) into surfaces. Here we investigate
an alternative method of shape control that inserts zero-dimensional objects –
isolated disclinations – into an atomically thin sheet. Inversion of bistable
conical disclinations provides a means to control the shape of the surface,
with tunable topgraphy down to the length-scale of protein secondary/tertiary
structure and energy barriers against shape change that are tunable from below
room temperature to values much larger. A tunable topography in a biologically
relevant size regime suggests that reconfigurable shape-driven binding
interactions may be possible with such sheets.

A disclination removes or adds a wedge of material in the lattice of a two-
dimensional sheet, yielding a conical or hyperbolic local region; in a
hexagonal lattice the least costly such defects are 5 and 7-member rings.
Since a cone (in a continuum approximation) has a local $C_{\infty}$ symmetry
for rotations about its apex, its mechanical states are anticipated to be
particularly simple: just “up” and “down”, related by a local inversion. The
reduced rotational symmetry of the saddle suggests more complex behavior, as
it may be able to assume more than one in-plane orientation depending on the
local mechanical environment. Here we investigate a sheet containing multiple
disclinations balanced between positive and negative (i.e. asymptotically
flat) and determine the multiplicity and character of the shape metastability
thereby instilled in the 2D layer. Anticipating our conclusions, the sheet’s
conformational freedom is dominated by Ising-like bistable cone degrees of
freedom; hence we call this means of shape control Isigami.

To create such a surface, we begin with a so-called Haeckelite [14, 15]
structure and “inflate” each ring with a penumbra of hexagons, similar to
inflation of larger fullerenes from $\text{C}_{\text{60}}$ [16, 17]. We choose
a Haeckelite in which the pentagonal rings form a slightly deformed kagome
lattice (Fig. 1) [18], speculating that this may cause mechanical frustration
which brings the set of possible shapes closer to mutual degeneracy, since
this surface has no obvious pairings of opposite disclinations. Other
disclination patterns are also possible, and those formed by phase field
crystal methods have been examined independently for their effect on sheet
toughness in an interesting work by Zhang, Li and Gao [19]. We choose graphene
as an archetype, since its mechanical response is reasonably well-studied and
methods exist to functionalize the surface to control mechanical stiffness,
interfacial energetics, and hydrophilicity [20, 21, 22]. Since the behavior
described below is largely geometrical in origin, conclusions derived from
graphene Isigami should generalize to other atomically thin two-dimensional
materials.

Figure 1: Three versions of a graphene-based Isigami sheet with different
disclination spacings. The first, with adjoining defects, is a Haeckelite
known from [14]. The second and third have two- and six-hexagon wide buffers
between pairs of disclinations. Sheets are color-coded by height, whose
variation grows for wider buffers (the first sheet being perfectly flat). Blue
lines delineate a twisted kagome lattice of pentagonal disclinations. The
larger unit cell marked on the third sheet shows the size of system most
closely studied (in either periodic or finite-patch geometries), containing 12
pentagonal and 12 heptagonal disclinations.

We construct both periodic and finite-patch regions of material hosting twelve
cones and twelve saddles on a kagome lattice as depicted in Fig. 1 and model
the mechanical response using the AIREBO potential [23] as implemented in
LAMMPS (Large-scale Atomic/Molecular Massively Parallel Simulator [24], as it
is well-validated for the mechanical response of nanoscale sp2 carbon [25, 26,
27, 28, 29]. We first examine a finite sheet whose disclinations are all
separated by six hexagons ($\sim$20 Å) from the nearest neighboring
disclinations; the edges are terminated by hydrogen. This separation is large
enough that even cones on the edge of the sheet have two well-defined
metastable “up” and “down” orientations. Shape variance is most dramatic in a
finite patch of material, as the periodic boundary constraint is absent. The
patch is systematically forced into every possible set of cone orientations by
mechanically inverting various sets of cones with external forces. To this
end, a force of $\pm 1.7$ eV/Å is applied to the five atoms at the apices of
various cones according to the desired up/down states and the system is then
allowed to evolve for 500 femtoseconds while the atoms are constrained to move
no more than $0.1$Å each timestep. A constraint force is also applied evenly
across every atom in the system to zero-out the net force. The structure is
then relaxed either through a thermal bath at 300 K for 50 ps followed by a
linear ramp anneal over 30 ps from 300 K to 3 K, or (for the periodic systems
described below) through a shorter 1 ps thermal bath followed by a series of
conjugate gradient minimizations where the unit cell geometry is allowed to
relax during alternate optimization steps. These methods both produce well-
converged energy minima (converged to less than 100 meV in systems with
thousands of atoms), but the anneal method performs better for the finite
patch in avoiding local minima.

For every initial choice of the twelve up/down cone configurations, the system
relaxes into a distinct metastable shape, i.e. all $2^{12}$ nominal Isigami
configurations are accessible. Fig. 2 shows some examples of these shapes,
labeled by the cone configuration: the different shapes that are metastably
assumed by the same sheet can be dramatically different. Several of these
configurations, including the five highest in energy, were simulated at 800 K
in an NPT ensemble for one nanosecond, with the sheet maintaining its original
Ising state. This high-temperature “challenge” anneal was also applied to a
subset of configurations that were repeated to create a larger $2\times 2$
supercell patch, providing assurance that shape metastability is preserved for
larger patch sizes as well.

Figure 2: Representative shapes for a 12-cone patch, as a demonstration of the
multiplicity of metastable shapes. The shapes are displayed in their minimum
energy states, and are hydrogen-terminated (yellow atoms) with the carbon
atoms in gray. A bitstring of cone states in the sheet is displayed below each
example; this labeling follows the order shown at center.

Collapsing the reflection symmetry about the sheet midplane, we actually
obtain $2^{11}$ distinct Isigami configurations for this 12-pentagon patch,
with an additional approximate reflection symmetry about the short diagonal
(broken very weakly by the detailed termination of the patch). Additional
symmetries in the periodic case further reduce the number of symmetry-distinct
configurations per unit area, but the conformational entropy of metastable
Isigami states remains extensive.

As noted earlier, whereas cones naturally have two distinct conformations
(i.e. up and down), the orientations of the principal axes of saddle-point
disclinations do not naturally fall into a binary choice; depending on the
states of nearby disclinations and other aspects of the local environment, a
given saddle point disclination could have one, two or possibly more
metastable axial orientations. We do in fact find certain conformations that
have the same set of cone orientations (i.e. the same Isigami state) but
visibly different overall shapes, sometimes differing by over an eV in energy
and stable in shape up to at least 800 K over half a nanosecond. Fig. 3
depicts two such states. While we have not exhaustively quantified the
frequency of these non-Ising states, our observations suggest that they
contribute a number of configurations equivalent to roughly one additional
Ising degree of freedom for a 12-cone sheet; i.e. they contribute only
modestly to the overall configurational entropy. Although these non-Ising
states do sometimes correspond to different orientations of the saddle
disclinations, we do not find a simple rule governing their appearance, as
reflected by the examples shown in Figure S5. Similar non-Ising states are
seen in the larger $2\times 2$ supercell patch. Simulations of this larger
patch (and larger periodic systems) reveal a similarly pervasive metastability
to Ising conformations, suggesting that the system has an extensive
conformational shape entropy.

How are these states distributed in energy? The “density of shapes” (i.e. the
number of shapes in a given energy range) for the finite 12-cone patch is
strikingly close to Gaussian, as shown in Fig. 4. It is tempting to consider
this outcome as an expression of the Central Limit Theorem for multiple nearly
independent energetic contributions from different disclinations, but the
stronger deviations from a Gaussian shape seen in a similarly-sized periodic
patch argue against a simple application of this notion. It is likely that
quasi-random finite-size effects in the finite patch, when combined with
medium-range effectively many-body elastic interactions, generate a complexity
sufficient to reproduce a roughly central-limit-like behavior.

Mechanical intuition suggests that nearby cones will have pair-wise
antiferromagnetic interactions, since opposing up/down orientations produce
compatible sidewall slopes – the prospects for generating a near-degeneracy of
conformations with such an interaction was one motivation for choosing a
frustrated kagome-like lattice for the disclinations [30]. In practice, we
find that longer-range and many-body elastic interactions between
disclinations are too strong to admit a strict frustration-derived degeneracy.
While these non-idealities (and also non-Isigami states) are sufficiently
important that the sheet is not a simple nearest-neighbor antiferromagnet, the
energies of different sheet configurations do reveal an overall nearest-
neighbor antiferromagnetic trend, as the energy varies systematically with the
number of oppositely-oriented nearest-neighbor cones for both the periodic-
boundary and finite-patch cases (Fig. 5). The effective $J$ of this trend is
proportionately smaller for a sheet with 1-hexagon separation between the
5-fold rings (Fig. S1). As noted in Supplementary Information, it was not
possible to describe the sheet energetics with a simple cluster expansion;
this was likely due in part to the long-range nature of elastic interactions
amongst nearby cones (i.e. when even a single cone inverts, we see significant
changes in shape across the entire patch, as shown in Figure S4) and in part
to the presence of a modest number of additional states not fully specifiable
by an Isigami state vector, as noted earlier.

Figure 3: Two periodic states with the same cone orientations but different
metastable shapes: the state on the right is 6.5 eV lower in energy. The
images are color-coded by height on the same scale, and the deformed kagome
lattice of each is shown in blue. Cones pointing up have red apices; those
pointing down are blue. Figure 4: The number of shapes of the 12-cone patches
studied versus their relaxed energy, as a fraction of the total number of
shapes examined for both finite and periodic sheets, with a normal
distribution superimposed. The error bars follow $\sqrt{N}$. Figure 5:  The
sheet energy as a function of the number of nearest-neighbor cone pairs which
are oppositely-oriented for both free (left, blue) and periodic (right,
orange) boundary conditions, with vertical axes shifted for clarity. The
overall linear trend yields similar nearest-neighbor antiferromagnetic $J$’s
for free ($-0.54$ eV) and periodic ($-0.56$ eV) cases. The large dispersion
about the linear trend reflects contributions from longer-ranged or collective
interactions and a modest admixture of non-Ising configurations. A wider range
of antiferromagnetic pairings is accessible to the free-boundary case, due to
a more forgiving boundary condition. Points are translucent to better reveal
the overall density of configurations. Figure 6: Comparison between an Isigami
sheet (at right) with a two-hexagon buffer between cones and a generic small
protein (insulin, at left) that has been smoothed using the Connolly (“rolling
ball”) method for constructing solvent-excluded surfaces, done here with a
solvent radius similar to the bending radius of the sheet to accentuate the
topography of both across the same length scale, showing it is possible to
construct Isigami sheets with reconfigurable topography on the same length
scale as protein secondary/tertiary structure.

These reconfigurable surfaces provide a means to access a multitude of
distinct sheet topographies from a single patch of multiply disclinated 2D
material: an obvious area of potential application for such an object is shape
recognition and binding of biomolecules. Ideally, such a surface would have
topography on the length scale of protein tertiary structure, a hydrophilic
surface that does not denature delicate biomolecules, and a tunable barrier
against shape change so that both dynamic ($\sim k_{B}T$) and static ($\gg
k_{B}T$) regimes can be accessed. The $\sim 0.5$ nm inter-pentagon spacing of
the sheet depicted in Fig. 6 provides topography on a biologically relevant
length-scale, as demonstrated by the comparison to insulin, a small protein,
in the same figure. The use of graphene oxide [31, 32] rather than hydrophobic
bare graphene [33, 34, 35] could introduce the needed hydrophilicity, and
perhaps also increased flexibliity [36].

The question of barrier height control requires more detailed study. The
inversion barriers of isolated graphene cones have been simulated previously
[37]; the barrier height depends on the chemical character of the conical apex
but is generally multiple electron volts for well-separated cones. Energy
barriers against cone inversion will depend on the material of the sheet, the
separation between conical disclinations, and also any structural
modifications performed on the conical apices such as functionalization [37]
to heighten the barrier or flattening to soften it (through grain boundaries
that interconnect disclinations [38, 39]). We observe in the periodic sheets
that the stability of the Ising and non-Ising states indeed varies with cone
separation, and also that the barriers against inter-conversion of the non-
Ising states are typically much lower than those between states with distinct
Ising configurations. We monitored the energy along the cone inversion pathway
for a few periodic sheets with different cone separations; although the
distribution of inversion barriers could not be exhaustively quantified, the
barriers all remained on the order of electron volts, likely lowered somewhat
(compared to isolated cones) by irreguarities in the local environment. The
typical barrier height scales roughly linearly with the separation between
pentagonal disclinations, being around 1 eV for a 1-hexagon separation and
around 6 eV for the 6-hexagon separation. At the 1-hexagon separation a
significant fraction of the Isigami states destabilize (see Figure S2) while
almost all of the non-Ising states disappear, where our criterion for
stability is surviving the room-temperature anneal mentioned earlier.

Since most of the sheets considered above often have inversion barriers much
greater than $k_{B}T$, we now consider a means to “thermalize” these barriers
even at larger disclination separations: oxidizing the sheet and etching away
the central five-membered ring and one or more surrounding rings to reduce the
mechanical deformation associated with nucleating inversion, terminating the
resulting apical multivacancy with hydrogen atoms. To this end, we oxidized a
six-hexagon-separation periodic sheet by random placement of oxygen atoms
equally onto upper and lower surfaces followed by a structural relaxation and
subsequent removal of any unreacted oxygen, yielding a functionalized sheet
with 12.6 at% oxygen (Fig. S3). These simulations used a version of the REAXFF
reactive force field [40, 41, 42] designed [43] to describe carbon, hydrogen
and oxygen [44] and updated to more precisely describe chemical properties of
C/H/O/N systems [45, 46, 47, 48]. Neither the structural relaxation following
etching (nor that which followed oxygenation) caused cone inversion, but
during a subsequent molecular dynamics simulation at 800K we observe rapid
($\sim 1$ ns) spontaneous inversion of cones; we anticipate that a similar
simulation without periodic boundary conditions would be at least as floppy.
Although these simulations were performed in the gas phase, we anticipate that
the qualitative conclusion of low, thermally accessible inversion barriers
will be robust against the introduction of aqueous conditions. In constrast,
the same system with intact (non-etched) apices shows no inversion over 1 ns
at 800 K.

The richness and reconfigurabiity of shape at the nanometer scale is a
signature element of biology, but one that is not so easily expressed in non-
biological systems. Here we have described a strategy towards expressing
richness of shape in inorganic materials by means of the non-planarity
intrinsic to the Gaussian curvature of disclinations in a 2D sheet, so that a
combinatorially large library of shapes can be expressed in a single sheet. As
this approach is purely geometrical, it should apply to any atomically thin
sheet, which could be more polar (e.g. hBN), more hydrophilic (graphene oxide
[31, 32]) or stiffer [49] than graphene. The degree of metastability of this
library of shapes is tunable from highly stable (multi-eV barriers) to
potentially room-temperature reconfigurable (for tightly spaced disclinations
in sheets that may also be intrinsically more flexile, possibly with apices
removed). Possible applications for 2D shape reconfiguration and memory
naturally center on those involving interaction with biological systems where,
for example, diverse shape libraries could be created under shape-labile
conditions and then selected for desired biological function under shape-
conserving conditions. Outside the biological regime, the presence of
disclinations (with associated geometrical phases [50]) and local strains
(with associated pseudomagnetic fields [51, 52, 53, 54]) may introduce unusual
and tunable electronic and plasmonic [55] properties as well. The behavior of
a disclinated sheet on longer length scales, where linear arrays of
disclinations could be organized to act in concert, may also be able to
recover phenomena akin to more traditional fold-based origami wherein mean
curvature plays a more prominent role.

###### Acknowledgements.

B.N.K. acknowledges training provided by the Computational Materials Education
and Training (CoMET) NSF Research Traineeship (grant number DGE-1449785).
B.N.K., L.K. and V.H.C. acknowledge support under NSF awards DMR-2011839 and
DMR-2039351. Many thanks to Dr. Malgorzata Kowalik for her assistance with ADF
and ReaxFF potentials in general.

## References

  * Blees  _et al._ [2015] M. K. Blees, A. W. Barnard, P. A. Rose, S. P. Roberts, K. L. McGill, P. Y. Huang, A. R. Ruyack, J. W. Kevek, B. Kobrin, D. A. Muller, and P. L. McEuen, Nature 524, 204 (2015).
  * Callens and Zadpoor [2018] S. J. Callens and A. A. Zadpoor, Materials Today 21, 241 (2018).
  * Cho  _et al._ [2011] J.-H. Cho, M. D. Keung, N. Verellen, L. Lagae, V. V. Moshchalkov, P. V. Dorpe, and D. H. Gracias, Small 7, 1943 (2011).
  * Dietz  _et al._ [2009] H. Dietz, S. M. Douglas, and W. M. Shih, Science 325, 725 (2009).
  * Han  _et al._ [2017] D. Han, X. Qi, C. Myhrvold, B. Wang, M. Dai, S. Jiang, M. Bates, Y. Liu, B. An, F. Zhang, H. Yan, and P. Yin, Science 358, eaao2648 (2017).
  * Hanakata  _et al._ [2016] P. Z. Hanakata, Z. Qi, D. K. Campbell, and H. S. Park, Nanoscale 8, 458 (2016).
  * Morikawa  _et al._ [2017] Y. Morikawa, S. Yamagiwa, H. Sawahata, R. Numano, K. Koida, M. Ishida, and T. Kawano, Advanced Healthcare Materials 7, 1701100 (2017).
  * Mortazavi  _et al._ [2017] B. Mortazavi, A. Lherbier, Z. Fan, A. Harju, T. Rabczuk, and J.-C. Charlier, Nanoscale 9, 16329 (2017).
  * Xu  _et al._ [2016] L. Xu, X. Wang, Y. Kim, T. C. Shyu, J. Lyu, and N. A. Kotov, ACS Nano 10, 6156 (2016).
  * Xu  _et al._ [2017] L. Xu, T. C. Shyu, and N. A. Kotov, ACS Nano 11, 7587 (2017).
  * Zhang  _et al._ [2015] Y. Zhang, Z. Yan, K. Nan, D. Xiao, Y. Liu, H. Luan, H. Fu, X. Wang, Q. Yang, J. Wang, W. Ren, H. Si, F. Liu, L. Yang, H. Li, J. Wang, X. Guo, H. Luo, L. Wang, Y. Huang, and J. A. Rogers, Proceedings of the National Academy of Sciences 112, 11757 (2015).
  * Akinwande  _et al._ [2017] D. Akinwande, C. J. Brennan, J. S. Bunch, P. Egberts, J. R. Felts, H. Gao, R. Huang, J.-S. Kim, T. Li, Y. Li, K. M. Liechti, N. Lu, H. S. Park, E. J. Reed, P. Wang, B. I. Yakobson, T. Zhang, Y.-W. Zhang, Y. Zhou, and Y. Zhu, Extreme Mechanics Letters 13, 42 (2017).
  * Wei and Yang [2018] Y. Wei and R. Yang, National Science Review 6, 324 (2018).
  * Terrones  _et al._ [2000] H. Terrones, M. Terrones, E. Hernández, N. Grobert, J.-C. Charlier, and P. M. Ajayan, Physical Review Letters 84, 1716 (2000).
  * Crespi  _et al._ [1996] V. H. Crespi, L. X. Benedict, M. L. Cohen, and S. G. Louie, Physical Review B 53, R13303 (1996).
  * Dunk  _et al._ [2012] P. W. Dunk, N. K. Kaiser, C. L. Hendrickson, J. P. Quinn, C. P. Ewels, Y. Nakanishi, Y. Sasaki, H. Shinohara, A. G. Marshall, and H. W. Kroto, Nature Communications 3, 10.1038/ncomms1853 (2012).
  * Suzuki  _et al._ [1991] T. Suzuki, Q. Li, K. C. Khemani, F. Wudl, and O. Almarsson, Science 254, 1186 (1991).
  * Sun  _et al._ [2012] K. Sun, A. Souslov, X. Mao, and T. C. Lubensky, Proceedings of the National Academy of Sciences 109, 12369 (2012).
  * Zhang  _et al._ [2014] T. Zhang, X. Li, and H. Gao, Extreme Mechanics Letters 1, 3 (2014).
  * Singh  _et al._ [2016] R. K. Singh, R. Kumar, and D. P. Singh, RSC Advances 6, 64993 (2016).
  * Wu  _et al._ [2015] R. Wu, Y. Wang, L. Chen, L. Huang, and Y. Chen, RSC Advances 5, 49182 (2015).
  * Morimoto  _et al._ [2016] N. Morimoto, T. Kubo, and Y. Nishina, Scientific Reports 6, 10.1038/srep21715 (2016).
  * Stuart  _et al._ [2000] S. J. Stuart, A. B. Tutein, and J. A. Harrison, The Journal of Chemical Physics 112, 6472 (2000).
  * [24] S. Plimpton, Journal of Computational Physics 117, 1 (1995). https://www.lammps.sandia.gov.
  * Svatek  _et al._ [2014] S. A. Svatek, O. R. Scott, J. P. Rivett, K. Wright, M. Baldoni, E. Bichoutskaia, T. Taniguchi, K. Watanabe, A. J. Marsden, N. R. Wilson, and P. H. Beton, Nano Letters 15, 159 (2014).
  * Gu and Sansoz [2013] J. Gu and F. Sansoz, Carbon 56, 351 (2013).
  * Meguid  _et al._ [2017] S. A. Meguid, A. R. Alian, and M. A. N. Dewapriya, in  _Micromechanics and Nanomechanics of Composite Solids_ (Springer International Publishing, 2017) pp. 39–70.
  * Giordanelli  _et al._ [2016] I. Giordanelli, M. Mendoza, J. S. Andrade, M. A. F. Gomes, and H. J. Herrmann, Scientific Reports 6, 10.1038/srep25891 (2016).
  * Zhang  _et al._ [2017] Z. Zhang, A. Kutana, A. Roy, and B. I. Yakobson, The Journal of Physical Chemistry C 121, 1257 (2017).
  * Yan  _et al._ [2011] S. Yan, D. A. Huse, and S. R. White, Science 332, 1173 (2011).
  * Pandit and De [2020] S. Pandit and M. De, ACS Applied Nano Materials 3, 3829 (2020).
  * Kenry  _et al._ [2016] K. Kenry, K. P. Loh, and C. T. Lim, Nanoscale 8, 9425 (2016).
  * Munz  _et al._ [2015] M. Munz, C. E. Giusca, R. L. Myers-Ward, D. K. Gaskill, and O. Kazakova, ACS Nano 9, 8401 (2015).
  * Alava  _et al._ [2013] T. Alava, J. A. Mann, C. Théodore, J. J. Benitez, W. R. Dichtel, J. M. Parpia, and H. G. Craighead, Analytical Chemistry 85, 2754 (2013).
  * Feng and Guo [2019] J. Feng and Z. Guo, Nanoscale Horizons 4, 339 (2019).
  * Poulin  _et al._ [2016] P. Poulin, R. Jalili, W. Neri, F. Nallet, T. Divoux, A. Colin, S. H. Aboutalebi, G. Wallace, and C. Zakri, Proceedings of the National Academy of Sciences 113, 11088 (2016).
  * Jordan and Crespi [2004] S. P. Jordan and V. H. Crespi, Physical Review Letters 93, 10.1103/physrevlett.93.255504 (2004).
  * Liu and Yakobson [2010] Y. Liu and B. I. Yakobson, Nano Letters 10, 2178 (2010).
  * Wang and Crespi [2017] Y. Wang and V. H. Crespi, Nano Letters 17, 5297 (2017).
  * van Duin  _et al._ [2001] A. C. T. van Duin, S. Dasgupta, F. Lorant, and W. A. Goddard, The Journal of Physical Chemistry A 105, 9396 (2001).
  * te Velde  _et al._ [2001] G. te Velde, F. M. Bickelhaupt, E. J. Baerends, C. F. Guerra, S. J. A. van Gisbergen, J. G. Snijders, and T. Ziegler, Journal of Computational Chemistry 22, 931 (2001).
  * ADF [2019] ADF 2019.3, SCM, Theoretical Chemistry, Vrije Universiteit, Amsterdam, The Netherlands, http://www.scm.com (2019).
  * Chenoweth  _et al._ [2008] K. Chenoweth, A. C. T. van Duin, and W. A. Goddard, The Journal of Physical Chemistry A 112, 1040 (2008).
  * Yang  _et al._ [2020] Z. Yang, Y. Sun, F. Ma, Y. Lu, and T. Zhao, Applied Surface Science 509, 145247 (2020).
  * Kowalik  _et al._ [2019] M. Kowalik, C. Ashraf, B. Damirchi, D. Akbarian, S. Rajabpour, and A. C. T. van Duin, The Journal of Physical Chemistry B 123, 5357 (2019).
  * Srinivasan  _et al._ [2015] S. G. Srinivasan, A. C. T. van Duin, and P. Ganesh, The Journal of Physical Chemistry A 119, 571 (2015).
  * Ashraf and van Duin [2017] C. Ashraf and A. C. van Duin, The Journal of Physical Chemistry A 121, 1051 (2017).
  * [48] Private communication from M. Kowalik provided a further optimization of the potential parameters.
  * Lai  _et al._ [2016] K. Lai, W.-B. Zhang, F. Zhou, F. Zeng, and B.-Y. Tang, Journal of Physics D: Applied Physics 49, 185301 (2016).
  * Lammert and Crespi [2004] P. E. Lammert and V. H. Crespi, Physical Review B 69, 10.1103/physrevb.69.035406 (2004).
  * Levy  _et al._ [2010] N. Levy, S. A. Burke, K. L. Meaker, M. Panlasigui, A. Zettl, F. Guinea, A. H. C. Neto, and M. F. Crommie, Science 329, 544 (2010).
  * Gill  _et al._ [2015] S. T. Gill, J. H. Hinnefeld, S. Zhu, W. J. Swanson, T. Li, and N. Mason, ACS Nano 9, 5799 (2015).
  * Zhang  _et al._ [2018] Y. Zhang, M. Heiranian, B. Janicek, Z. Budrikis, S. Zapperi, P. Y. Huang, H. T. Johnson, N. R. Aluru, J. W. Lyding, and N. Mason, Nano Letters 18, 2098 (2018).
  * Zhang  _et al._ [2019] Y. Zhang, Y. Kim, M. J. Gilbert, and N. Mason, Applied Physics Letters 115, 143508 (2019).
  * Kang  _et al._ [2018] P. Kang, K.-H. Kim, H.-G. Park, and S. Nam, Light: Science & Applications 7, 10.1038/s41377-018-0002-4 (2018).