# BUDS: Balancing Utility and Differential Privacy by Shuffling

Poushali Sengupta1 Sudipta Paul2,3 Subhankar Mishra2,3 1Department of
Statistics, University of Kalyani Kalyani, West Bengal, India - 741235 2School
of Computer Sciences, National Institute of Science, Education and Research
Bhubaneswar India - 752050 3Homi Bhaba National Institute, Anushaktinagar,
Mumbai India - 400094<EMAIL_ADDRESS>2,3{sudiptapaulvixx,
<EMAIL_ADDRESS>
###### Abstract

Balancing utility and differential privacy by shuffling or BUDS is an approach
towards crowd sourced, statistical databases, with strong privacy and utility
balance using differential privacy theory. Here, a novel algorithm is proposed
using one-hot encoding and iterative shuffling with the loss estimation and
risk minimization techniques, to balance both the utility and privacy. In this
work, after collecting one-hot encoded data from different sources and
clients, a step of novel attribute shuffling technique using iterative
shuffling (based on the query asked by the analyst) and loss estimation with
an updation function and risk minimization produces a utility and privacy
balanced differential private report. During empirical test of balanced
utility and privacy, BUDS produces $\epsilon=0.02$ which is a very promising
result. Our algorithm maintains a privacy bound of
$\epsilon=ln[t/((n_{1}-1)^{S})]$ and loss bound of
$c^{\prime}\bigg{|}e^{ln[t/((n_{1}-1)^{S})]}-1\bigg{|}$.

Keywords: Differential privacy(DP), Shuffling, Encoding, Utility, Privacy.

##  1 Introduction

Crowd sourcing is a very powerful tool for collecting data, for example during
recent pandemic like Covid-19 all the datasets have been collected from
different hospitals, patients through this process only, for further
researches to fight the situation. This method has been widely used by the
software companies, the health service providers or the researchers in
different fields which helps to collect the necessary data easily from the
willing participants. But, maintaining the privacy of the participants in case
of a survey concerning a sensitive issue or an attack strong enough to reveal
the individual identity, has been a real challenge for a while now.
Differential privacy (DP) provides a provable solution to this privacy concern
of individual in a database with some trade offs.

Differential privacy theory acknowledges the privacy concern of both the data
analyst and the participants in a survey. DP promises that the statistically
distributed answer to the question asked by the analyst will be in the
neighbourhood of the actual answer but will not reveal the accurate one. This
promise provides enough noise in the answer such that the individual’s
information can not be leaked from the aforementioned survey databases. Also,
the analyst gets enough insight of the databases for further analysis without
being able to extract any individual’s information.

A data analyst asks the queries through a query function to the database. The
response to that query, over the entire database, is then generated using an
algorithm based on the differential privacy theory (DP algorithm) in the form
of a report. Here utility can be defined as, how much insight about that
database can be extracted from the report. To maintain individual’s privacy,
an 100% utility is not desirable at all. Therefore maintaining a proper
balance between utility and privacy is an essential characteristics for a good
and feasible DP algorithm irrespective of its two broad kinds, i.e. local
DP(LDP) and centralized DP(CDP). RAPPOR[2], PROCHLO (implementation of
ESA)[3], amplification by shuffling[4], ARA[5] are some of the standard works
accounting both the kinds LDP and CDP. But every work that is mentioned above
does not have that optimal balance of utility and privacy. Hence to
acknowledge this problem a balanced algorithm with better utility and privacy
is proposed here.

The contributions of this work are following:

  * •

The introduction of the optimal condition for the privacy parameter
$\epsilon$. It has been shown that this algorithm maintains the privacy of
$\epsilon=ln[t/((n_{1}-1)^{S})]$ , where, $\epsilon$ is the privacy parameter,
$n_{1}$ is the first batch size, $S(S>1)$ is the number of shufflers and $t$
is the number of batches.

  * •

The introduction of loss function updation to guarantee the longitudinal
privacy.

  * •

The introduction of risk function for balancing the differential trade-offs
and choosing the optimal randomization scheme.

The paper is arranged in the following manners: following an introduction the
necessary background knowledge is given in the section 2, a utility and
privacy balanced DP algorithm is proposed in the section 3 to acknowledge the
aforementioned problem, the proofs of utility and privacy for the proposed
algorithm is given consecutively in the sections 4 and 5.

##  2 Related Work

The main concern of statistical database of sensitive information has always
been to protect the ”privacy” of ”individual” from the attack of intruders. As
a starting point, Dalenius desideratum [7] gives a hard bound on this privacy
situation. the desideratum is following:
“Nothing about an individual should be learn-able from the database that could
not be learned without access to the database!”

By introducing ”Differential privacy”(DP) in 2006 Dwork showed that Dalenius
desideratum is too strong to be useful in practice. The fundamental
definitions, theorems and discussions to understand the concept of
differential privacy is given in [1]. The main motto of DP is not to protect
the entire database but to protect the sensitive data of individual of a
database from the attackers. One of the main DP approaches LDP [8] is based on
randomized technique where the noise get injected inside the data at the time
of collection. Another approach CDP is a centralized approach where a trusted
curator maintain the DP promises to the whole forest of data in a database.

The present DP models can be classified into these two broad categories.
RAPPOR[2] is currently the fastest implementation in LDP by using hash
functions in a novel manner by using bloom filters, to produce noisy reports
for a particular query. But the main drawback of RAPPOR is that the mechanism
fails to provide enough utility. In 2017, PROCHLO[3] is introduced, that uses
the Encode, Shuffle, Analyze framework to provide CDP on the data base.
Amplification by Shuffling[4] is another work on CDP in 2018 where the authors
introduced a mechanism with oblivious shuffling that provides $\epsilon$-LDP
which satisfies $\mathcal{O}(\epsilon\sqrt{\log{\frac{1}{\delta}/n},\delta})$
centralized differential privacy(CDP) guarantee. The disadvantage of this work
is the inability to guarantee the longitudinal privacy. In their work in 2020,
ARA[5] the authors describe a mechanism that provides CDP on RAPPOR reports.
Due to excessive noisy data, the main downside of this work is that the level
of utility is not more than $52.28\%$ in average, even though it is one of the
fastest implementation in CDP. To recover these aforementioned problems in
2020,[3] the work was revisited and a new approach [6] was proposed that
introduced report fragmentation to generate the final report to keep strong
privacy promises for longitudinal database with maximised utility guarantee.
But this framework involves a complex process and harder to implement. To
simplify the architecture, the authors of this paper proposed the method of
iterative shuffling that provides a significant balance between utility and
privacy. This mechanism works with minimum noise that gives an impressive
utility and privacy guarantee on the longitudinal data at the same time. This
work[11] shows that the shuffle protocols for the widely studied selection
problem requires exponentially higher sample complexity than the central model
protocols which is a direct inspiration to this work. It is a special case of
ESA framework. One of the direct inspirations was Li et al.’s paper[12]. The
main motto of this paper[12] is to balance the trade off between utility and
Privacy and it shows that the numerical nature of domain report is always a
advantage for balancing these two. It introduces square wave (SW) mechanism
and expectation maximization with smoothing (EMS) mechanism where SW exploits
the numerical nature of the domain reports and EMS is applied to aggregate the
histogram generated from SW mechanism to estimate the original distribution.
The main drawback of this paper is the entire work is on LDP. Another work by
Lecuyer et al.[10] presents the first certified defence that is biased on a
novel connection between robustness against adversarial example and DP, which
not only works for large network and dataset , but also can be applied to the
arbitrary model setup. Another work that inspires us[13], introduces the
capacity bounded differential privacy where the adversary that distinguishes
the output distribution is assumed to be not bounded in computational power.
But this work does not explore the generalization in high probability and
adaptivity in statistical generalization. This work has a future promise to
explore into the informational geometry pf adversarial divergence. Another
work on LDP[14] provides more accurate location privacy recommendation using
matrics factorization. In addition they found out the best granularity of a
location privacy preference and built a suitable method that can predict the
location privacy preference accurately which inspires us too. But it was,
solely LDP based with less utility in comparison to the normal matrix
factorization technique and has a promise to go into more granularity depth
with respect to time.

##  3 Architecture

In this work, after the collection of data from various sources with one hot
encoding, a query function is applied on the data which the attributes that
are required for generating reports and then the reported attributes tie up
together to represents a single attribute and all attributes are transmitted
to the shufflers for secret iterative shuffling. After this, finally the
report is generated. This mechanism is named as $BUDS\ :\ Balancing\ Utility\
and\ Differential\ Privacy\ by\ Shuffling$. The whole process is divided into
the following steps (figure 3):

###  3.1 Collecting Data with One-Hot Encoding

The data records are collected from various sources with one-hot encoding.
Let, for a data record $X$, the domain of the x is $D$ which is a dictionary
of elements and we want to estimate the frequency of the elements that is
contained by the record $X$ in the domain $D$. When the cardinality of $D$ is
not too large, the best way to encode data is one-hot encoding that is a group
of bits among which the legal combinations of values are only those with a
single high bit (1) and all other bits are low (0). Now, the choice of
encoding has a great impact on utility. When, the cardinality of $D$ is too
large, one may use the sketching algorithm for encoding , but in practical it
will not give a good utility as it is shown in the ESA revisited[6]. In this
architecture, the preference is one-hot encoding instead of any other encoding
to produce a result with minimum noise that always provides maximum utility
while keeping $\epsilon$-Differential Privacy.

###  3.2 Shuffling

A randomised mechanism is applied with shuffling which occurs repeatedly to
the given data for producing randomised report to a particular query. This
procedure is decomposed into two parts, in the first part the query function
is applied to the data to get the important attributes for generating the
final report and in the second part, all rows of each attributes are shuffled
by the $S\ (S>1)$ number of shuffler.

Example 1: If a database contains names, ages, heights and weights of
individuals where $name,age,\>height\>$ and$\>weight$ are four attributes and
the query is ”How many people are in database are less than 40 years old and
have name starting with letter ${}^{\prime}N^{\prime}$?”, then the attributes
’Name’ and ’Age’ will be returned as answer after applying query function
which indicates that only these two attributes are important for generating
final report to that particular query.

For general case, if there exist a dataset with $n$ rows and $k$ attributes.
Once the whole data is collected, the query function will be applied to the
data and the attributes which is required to generate answer is returned. If
$m$ number of attributes are important for generating the final report, then
these $m$ attributes will tie up together to behave like a single attribute
and the reduced number of attributes will be $g=k-m+1$. Now if $g$ is
divisible by $S$, these $g$ numbers of attributes is divided into $S$ group
with $g/S$ attributes in each groups. If $g$ is not divisible by $S$, then
extra $e$ elements will choose a group randomly without replacement[9]. Now
the whole data is divided into $t$ batches where $ith$ batch contains $n_{i}$
number of rows and $n_{i}\simeq n_{j};\forall\>1\leq i,j\leq t$ i.e number of
rows in each groups are almost equal.

Now for every batch, each group of attributes will choose a shuffler from $S$
number of shuffler randomly without replacement [9] and go for shuffling.
After shuffling of first batch, the 2nd batch along with first batch where all
$n_{1}+n_{2}\simeq 2n_{1}$ number of rows will go for shuffling. This thing
will repeat every time till the last batch where the last batch will go for
shuffling with total $n_{1}+n_{2}+...+n_{t}=tn_{1}$ rows. Every time each
batch will go for shuffling along with previous all batches and for this it is
called Cumulative Iterative Shuffling(CIS).

As a result, the author has found that it is not necessary to apply this
technique as it gives negative value of epsilon. So, here the whole
concentration is to apply another approach, where the first batch with $n_{1}$
number of rows will go for shuffling first, then the 2nd batch with $n_{2}$
number of rows will go and so on. At the end, the last batch with $n_{t}$
number of rows will go for shuffling. This is called Iterative Shuffling(IS).

Every Shuffler has separate channel for separate attributes and each shuffler
has their own shuffle technique for doing independent shuffling. The whole
architecture is given in the figure 1.

Figure 1: Architecture of BUDS

##  4 Privacy

In this section, the privacy budget for CIS and IS are derived and compared to
each other. At the last part of this section, the approach with better privacy
budget is found and the rest of the work is proceeded with this particular
value of privacy budget.

The database here is with total $n$ rows and $g$ batches and the whole
database is divided into $t$ batches. Now a randomisation function is applied
through shuffling, denoted by $\mathcal{R_{S}}$, to the data to create strong
privacy protection. The proof will be proceeded with the first approach
($CIS$) and the privacy budget of it will be derived here.

######  Theorem 1.

(Cumulative Iterative Shuffling : CIS) A randomisation function
$\mathcal{R_{S}}$ applied by $S\ (S>1)$ number of shuffler providing
cumulative iterative shuffling to a data set $X$ with $n$ rows and $g$
attributes, where the data base is divided into $1,2,...,t$ batches containing
$n_{1},n_{2},...,n_{t}$ number of rows respectively, will provide
$\epsilon$-differential privacy to the data with privacy budget-

$\epsilon=\ln{\bigg{(}\frac{1}{n_{1}-1}\bigg{)}^{S}}$ (1)

only when, $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$.

###### Proof.

Let, the data set contain $n$ rows and $g$ attributes and there exists $S$
number of shufflers. The attributes are divided into $S$ groups as described
in the previous subsection. Each row of data set contains the information of
individuals corresponding their unique ID. The data set is divided into
$1,2,...,t$ batches containing $n_{1},n_{2},...,n_{t}$ number of rows
respectively where $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$.
The first group of attributes of the first batch choose a shuffler randomly
with probability $\frac{1}{S}$, The second group of attributes of the first
batch choose a shuffler randomly with probability $\frac{1}{S-1}$ and so on.
In the similar way the last group of attributes of the first batch will choose
a shuffler only in 1 way.
After shuffling, a particular row will belong to their own unique Id i.e a row
will be in its own position and other row will shuffle in $(n_{1}-1)!$ ways.
All rows will shuffle in $n_{1}!$ ways.
The probability that a particular row of first batch will belong to its own
unique ID and will be same as it was before the shuffling was

$\displaystyle\frac{1}{S}\times\frac{(n_{1}-1)!}{n_{1}!}\times$
$\displaystyle\frac{1}{S-1}\times\frac{(n_{1}-1)!}{n_{1}!}\times...\times
1\times\frac{(n_{1}-1)!}{n_{1}!}$ (2)
$\displaystyle=\frac{1}{S!}\times\bigg{[}\frac{(n_{1}-1)!}{n_{1}!}\bigg{]}^{S}$
(3)

The probability that the row will not belong to its own ID after shuffling is

$\displaystyle\frac{1}{S!}\times\bigg{[}\frac{n_{1}-(n_{1}-1)!}{n_{1}!}\bigg{]}^{S}$
(4)

The Randomised Response Ratio($RR_{1}$) or the probability ratio for first
batch of data will be

$\displaystyle RR_{1}$ $\displaystyle=\frac{P(Row\ belongs\ to\ its\ own\
unique\ ID)}{P(Row\ does\ not\ belongs\ to\ its\ own\ unique\ ID)}$ (5)
$\displaystyle=\frac{\frac{1}{S!}\times\bigg{[}\frac{(n_{1}-1)!}{n_{1}!}\bigg{]}^{S}}{\frac{1}{S!}\times\bigg{[}\frac{n_{1}!-(n_{1}-1)!}{n_{1}!}\bigg{]}^{S}}$
(6) $\displaystyle=\frac{1}{(n_{1}-1)^{S}}$ (7)

The second batch will go for shuffling along with previous batch containing
total $n_{1}+n_{2}$ number of rows and here the probability ratio will be

$\displaystyle RR_{2}=\frac{1}{(n_{1}+n_{2}-1)^{S}}$ (8)

Similarly the probability ratio for third batch along with all previous
batches will be:

$\displaystyle RR_{3}=\frac{1}{(n_{1}+n_{2}+n_{3}-1)^{S}}$ (9)

This process will repeat for t batches and the probability ratio for the last
batch will be:

$\displaystyle RR_{t}=\frac{1}{(n_{1}+n_{2}+n_{3}+.....+n_{t}-1)^{S}}$ (10)

The total probability ratio for the whole data base will be:

$\displaystyle RR_{\infty}=$
$\displaystyle\frac{1}{(n_{1}-1)^{S}}+\frac{1}{(n_{1}+n_{2}-1)^{S}}+$ (11)
$\displaystyle...+\frac{1}{(n_{1}+n_{2}+...+n_{t}-1)^{S}}$ (12)

For, $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$ and for this we can write

$RR_{\infty}=\frac{1}{(n_{1}-1)^{S}}+\frac{1}{(2n_{1}-1)^{S}}+...+\frac{1}{(tn_{1}-1)^{S}}$
(13)

Now, we can see the $2^{\text{nd}},3^{\text{rd}},...t^{\text{th}}$ terms in
RHS of the equation are the very small fractions and we can easily ignore it.
By ignoring the small terms in the equation we get,

$RR_{\infty}=\frac{1}{(n_{1}-1)^{S}}$ (14)

Therefore, the privacy budget $\epsilon$ will be :

$\epsilon=\ln{(RR_{\infty})}=\ln{\bigg{[}\frac{1}{(n_{1}-1)^{S}}\bigg{]}}$
(15)

∎

The next theorem will provide the value of the privacy budget of another
approach using $IS$.

######  Theorem 2.

(Iterative Shuffling : IS) A randomisation function $\mathcal{R^{*}_{S}}$
applied by $S\ (S>1)$ number of shuffler providing iterative shuffling to a
data set $X$ with $n$ rows and $g$ attributes, where the data base is divided
into $1,2,...,t$ batches containing $n_{1},n_{2},...,n_{t}$ number of rows
respectively, will provide $\epsilon$-differential privacy to the data with
privacy budget-

$\epsilon=\ln{\bigg{(}\frac{t}{n_{1}-1}\bigg{)}^{S}}$ (16)

only when, $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$.

###### Proof.

The first batch of the data will go for shuffling exactly as the same of the
previous approach that we have already discussed earlier. So, the probability
ratio for the first batch will be same.
The Randomised Response Ratio($RR_{1}$) or the probability ratio for first
batch of data will be

$\displaystyle RR_{1}$ $\displaystyle=\frac{P(Row\ belongs\ to\ its\ own\
unique\ ID)}{P(Row\ does\ not\ belongs\ toits\ own\ unique\ ID)}$ (17)
$\displaystyle=\frac{1}{(n_{1}-1)^{S}}$ (18)

The second batch with $n_{2}$ rows will go for shuffling and here the
probability ratio will be

$\displaystyle RR_{1}=\frac{1}{(n_{2}-1)^{S}}$ (19)

This process will repeat for t batches and the total probability ratio for the
whole data base will be:

$\displaystyle RR_{\infty}=$
$\displaystyle\frac{1}{(n_{1}-1)^{S}}+\frac{1}{(n_{2}-1)^{S}}+.....+\frac{1}{(n_{t}-1)^{S}}$
(20)

For, $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$ and for this we can write

$RR_{\infty}=\frac{t}{(n_{1}-1)^{S}}$ (21)

Therefore, the privacy budget $\epsilon$ will be :

$\epsilon=\ln{(RR_{\infty})}=\ln{\bigg{[}\frac{t}{(n_{1}-1)^{S}}\bigg{]}}$
(22)

∎

Now, the randomised response probability ratio $RR\infty$ of $CIS$ is giving a
very small fraction which makes the value of $\epsilon$ negative and it is not
desirable at all. But, in the next part of this section a better privacy
budget can be found by using normal $IS$. This value of $\epsilon$ is giving
enough privacy guarantee to continue our work. The work will be proceeded with
$IS$ and the value of $\epsilon$ of $IS$ will be taken as the privacy
guarantee for the rest of this work.

##  5 Utility

Utility can be described as how much real information we can gain from the
data by a particular query or set of queries. In this section a discussion on
the utility that can be gained from the data by applying BUDS is done
thoroughly and a tight bound for loss function of input and output count that
have a great impact on utility is provided depending on the privacy budget. At
the end of this section, the authors have tried to find the optimized
randomization function by minimizing empirical risk function to achieve
maximum utility keeping $\epsilon$ privacy guarantee.

We have the dataset containing $n$ number of rows and $k$ number of
attributes. After applying the query function, we get a data set with reduced
set of attributes $g$. The whole data set is divided in $1,2,...,t$ batches.

Let assume, the query is ”How many people are engaged with event $E$ in a time
horizon $[d]$?” where, $E\ \epsilon\ \mathcal{E}$,
$\mathcal{E}=\\{E_{1},E_{2},...\\}$ a set of all possible events and
$[d]=\\{1,2,....,d\\}$. Now, at the time point $T$, let the input database is
$X$ and the output database is $Y$. For database $X$, that means before
shuffling of the data, if a count on the people engaged with event
$E\epsilon\mathcal{E}$ is taken, it will give : $c=\Sigma_{\text{i $\epsilon$
[t]}}\Sigma_{\text{T $\epsilon$ [d]}}X_{i}[T]$, where $i$ denotes the batch
number. $\Sigma_{\text{T $\epsilon$ [d]}}X_{i}[T]$ denotes the number of
people engaged with event $E\epsilon\mathcal{E}$ at the time horizon $[d]$ in
ith batch. The count $c$ gives the average number of people engaged to the
event $E\epsilon\mathcal{E}$ for the whole input database at the time horizon
$[d]$ which is denoted as to be actual answer of that particular query. Now,
if the same count is taken on the output database. it will give :
$c^{\prime}=\Sigma_{\text{i $\epsilon$ [t]}}\Sigma_{\text{T $\epsilon$
[d]}}Y_{i}[T]$ which is the reported answer of this mechanism. Now the main
idea is to find the distance between these two counts which actually gives a
great impact on utility measure. Now if the distance between these two counts
are really vary close, it can be said that the utility is good enough. The aim
is to minimize this distance which can be measure by the loss function.

These characteristics of BUDS hold for general cases. When the query gives $m$
number of relevant attributes, these all are also applicable in this case. For
generating report for a particular query we need to concentrate only to the
tied relevant attributes which contains no extra noise except the noise
produced by one-hot encoding to the data. This can be called the sub-database.
Now the input sub-database $D_{X}\subseteq X$ and the output sub-database
$D_{Y}\subseteq Y$ will behave like the adjacent database as the information
containing in rows of $D_{X}$ are exactly same as $D_{Y}$, only difference is
that the rows of $D_{Y}$ are shuffled, i.e each individual’s information does
not belongs to its own unique ID. Remembering this fact, for two adjacent
database $D_{X}$ and $D_{Y}$ if one wants to take the count of people engaged
to a event $E\epsilon\mathcal{E}$, the count $c^{\prime}$ of output sub-
database $D_{Y}$ will be in the neighbour-hood of the count $c$ of the the
input sub-database $D_{X}$. As, in this mechanism a minimum noise is added to
the data measure of distance between $c$ and $c^{\prime}$ will be vary close
and only differ on $e^{\text{$\epsilon$}}$, where, $\epsilon$ is the privacy
budget of the mechanism.
Thus we get the following bound:

$c\leq e^{\text{$\epsilon$}}c^{\prime}$ (23)

when $\epsilon$ = 0 $\implies$ $c=c^{\prime}$; i.e. The utility
$\mathcal{U}(X,Y)$ reaches in highest value. If we take the range of utility
$[0,1]$; when $\epsilon$ = 0 then $\mathcal{U}(X,Y)=1$. In this work,

$c\leq e^{\text{$\ln{\bigg{[}\frac{t}{(n_{1}-1)^{S}}\bigg{]}}$}}c^{\prime}$
(24)

By subtracting $c^{\prime}$ from both sides and taking absolute value of the
equation (24) we get.

$|c-c^{\prime}|\leq
c^{\prime}\bigg{|}e^{\text{$\ln{\bigg{[}\frac{t}{(n_{1}-1)^{S}}\bigg{]}}$}}-1\bigg{|}$
(25)

We define the loss function $\mathcal{L}(c,c^{\prime})$ = $|c-c^{\prime}|$ and
get

$\mathcal{L}(c,c^{\prime})\leq
c^{\prime}\bigg{|}e^{\text{$\ln{\bigg{[}\frac{t}{(n_{1}-1)^{S}}\bigg{]}}$}}-1\bigg{|}$
(26)

The Risk function will be calculated in the following with the idea to
minimize the risk for getting maximum utility. By minimizing the risk function
the optimum randomisation function will guarantee the strong privacy with
maximum utility. Obviously here a hypothesis class exists that is a space
containing all possible Randomisation function we are searching for. By the
concept of decision theory, the main idea is to minimizing the risk function
to find the best randomization function that will help us to map best from
input to output. The Risk function is denoted by $Risk(\mathcal{R(S)})$ and

$Risk(\mathcal{R(S)})=E[\mathcal{L}(X,Y)]=\int\int
P(c,c^{\prime})\mathcal{L}(c,c^{\prime})dcdc^{\prime}$ (27)

Here , $P(c,c^{\prime})$ is the distribution of sample data set containing $n$
data points that are drawn randomly from a population follows the distribution
$\mu(Z)$ over
$Z=c.c^{\prime}:(c_{1},c^{\prime}_{1}),(c_{2},c^{\prime}_{2}),....,(c_{n},c^{\prime}_{n})$
and

$P(c,c^{\prime})=P(c^{\prime}|c).P(c)$ (28)

Now the empirical risk will be,

$Risk_{\text{(emp)}}(\mathcal{R(S)})=\frac{1}{n}\Sigma_{1}^{n}L(c_{i},c^{\prime}_{i})\leq\frac{1}{n}\Sigma_{1}^{n}e^{\text{$\epsilon$}}c^{\prime}_{i}$
(29)

We will add a regularization parameter G that is included in order to impose
the complexity penalty on the loss function and prevent over fitting in the
following way:

$Risk_{\text{(emp)}}(\mathcal{R(S)})=\frac{1}{n}\Sigma_{1}^{n}L(c_{i},c^{\prime}_{i})+\lambda
G(\mathcal{R(S)})$ (30)
$Risk_{\text{(emp)}}(\mathcal{R(S)})\leq\frac{1}{n}\Sigma_{1}^{n}e^{\text{$\epsilon$}}c^{\prime}_{i}+\lambda
G(\mathcal{R(S)})$ (31)

where $\lambda$ controls the strength of complexity penalty. Let assume, we
have found the mechanism $\mathcal{R*(S)}$ that minimizes the risk, then

$\mathcal{R*(S)}=\operatornamewithlimits{argmin}_{\text{$\mathcal{R(S)}\epsilon\mathcal{H}$}}Risk_{\text{(emp)}}(\mathcal{R(S)})$
(32)

Table 1 will give the description of all the symbols that have been used in
this whole discussion.

Table 1: Descriptions of Symbols used Symbols |  Description
---|---
$n$ |  Number of rows in the data set
$K$ |  Actual number of attributes in the data set
$Q$ |  Query function
$m$ |  Number attributes relevant the query
$g$ |  Number of attributes when all relevant attributes tied up together.
$S$ |  Number of shuffler
$t$ |  The number of batches
$n_{i}$ |  Number of rows in ith batch; $i\epsilon[t]=\\{1,2,...,t\\}$
$\epsilon$ |  Privacy budget
$X$ |  Input database
$Y$ |  Output database
$D_{X}$ |  Input sub-database containing only the tied up attributes presenting a single attribute relevant to the query of the client.
$D_{Y}$ |  Output sub-database containing only the tied up attributes presenting a single attribute relevant to the query of the client.
$c$ |  Count related to query on the input data
$c^{\prime}$ |  Count related to query on the output data
$E$ |  A particular event
$\mathcal{E}$ |  A set of all possible events
$T$ |  A single time point
$[d]$ |  A time horizon, $[d]=\\{1,2,...,d\\}$
$D$ |  Domain of the input database $X$

##  6 Result and Discussion

A small example using $IS$ with $\epsilon$-DP without violating the loss
function of input-output count, is given in this section. Also an empirical
result is discussed later.

In BUDS, a query function is used on the encoded database containing
individuals information corresponding their own unique ID in each row before
shuffling and it gives us the relevant attributes name to that query so that
in the next step, these attributes can tie up together to present a single
attribute.

Example 2: Let’s take the dataset containing names, ages, heights and weights
of six individuals where $name,age,height$ and $weight$ are four attributes
and the query is ”How many people are in database are less than $40\ years$
old and have weight more than $60\ kg$?”. The query function returns the
attributes $"weight","Age"$ as the relevant attribute for generating final
report. Here these two attributes will tie up. After that, the groups of
attributes go to the shufflers for secret $IS$ where only the rows of each
attributes of each batch will shuffle in a secret technique. For this, the
relevant attribute pair(Weight:Age) always hold the person’s weight with their
own age in each row while each weight:age changes their own unique ID due to
$IS$. On the other hand, rows of other irrelevant attributes
(${}^{\prime}Name^{\prime},^{\prime}Height^{\prime}$) not only change their
unique ID but also change their belonging weights:age due to $IS$ in a way
that one can never go back to the actual database using generated report and
explore all the information related to a particular individual which is stored
in the database. So, BUDS keeps a strong privacy as it is proved in section
IV. The table 2 is showing the data base before and after shuffling.

Table 2: Empirical Scenario of Example 2 Before and After Shuffling |  Before |  IS |  |  After |  IS
---|---|---|---|---|---
Name |  Age |  Height:Weight |  Name |  Age |  Height:Weight
Riya |  20 |  5.3”:48 |  Priya |  7 |  5.3”:48
Sonal |  7 |  4.8”:42 |  Riya |  20 |  4.8”:42
Priya |  28 |  5.3”:78 |  Sonal |  28 |  5.3”:78
Sayan |  35 |  6.00”:85 |  Pranab |  17 |  6.00”:85
Pranab |  60 |  5.9”:55 |  Sayan |  60 |  6.01”:64
Ravi |  17 |  6.01”:64 |  Ravi |  35 |  5.9”:55

In BUDS, for a given query $Q$, the risk function is calculated after
generating the DP report and by minimising the risk, the best randomisation
function is found to generate final report. If the bound of loss function is
violated for any DP report, the model will take a fresh input from client
again and update the model to continue the process. In this way, the maximum
utility from the data will be gained while keeping strong privacy guarantee.
Table 3 will give an empirical insight about BUDS while varying the batch
size, database size, shuffler size etc.

Table 3: Empirical analytical results of the BUDS No. of rows | No. of batches | Avg. batch size | Shuffler | $\epsilon$
---|---|---|---|---
1000 | 130 | 7 | 3 | 0.50
11000 | 1000 | 11 | 3 | 0
100000 | 5500 | 18 | 3 | 0.11
1000000 | 31000 | 32 | 3 | 0.03
100000000 | 1000000 | 99 | 3 | 0.03
1000 | 100 | 10 | 2 | 0.2
11000 | 500 | 22 | 2 | 0.12
100000 | 2200 | 45 | 2 | 0.1
1000000 | 10000 | 100 | 2 | 0.02
100000000 | 218000 | 458 | 2 | 0.04

##  7 Future Scope and Conclusion

In BUDS, one-hot encoding is used which transform the categorical or real
valued variable in a form that helps a machine learning algorithm to produce a
better result by keeping privacy with great utility. Although one-hot encoding
has proved to be a good encoding option, in future other encoding options will
be explored too, to further balance the trade-offs between privacy and
utility. In future extensive experiments on different benchmark datasets using
this algorithm has a great promise itself.

To summarise this whole paper, BUDS gives a balanced approach using one-hot
encoding, iterative shuffling with loss management and risk minimization
update. The empirical result analysis is given in Table 3. We get the privacy
value $\epsilon=0.02$ for the optimal conditions if we analyse the Table 3
carefully. These results themselves are very promising for further exploration
in the practical applications, as in the future scope mentioned above.

##  8 Acknowledgement

This research was partially supported by Department of Science and Technology
Grant.
Grant ID: NRDMS/UG/S.Mishra/Odisha/E-01/2018.

## References

  * [1] C. Dwork and A. Roth, ”The algorithmic foundations of differential privacy”, Foundations and Trends® in Theoretical Computer Science, 9(3–4), pp.211-407.
  * [2] $\acute{U}$. Erlingsson, V. Pihur, A.Korolova, ”Rappor: Randomized aggregatable privacy-preserving ordinal response”, In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security 2014, Nov 3 (pp. 1054-1067).
  * [3] A. Bittau, $\acute{U}$. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes and B. Seefeld, ”Prochlo: Strong privacy for analytics in the crowd”, In Proceedings of the 26th Symposium on Operating Systems Principles, October, 2017 (pp. 441-459).
  * [4] $\acute{U}$. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar and A. Thakurta,” Amplification by shuffling: From local to central differential privacy via anonymity”, In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2019 (pp. 2468-2479)
  * [5] S. Paul, S. Mishra, ”ARA: Aggregated RAPPOR and Analysis for Centralized Differential Privacy”, SN Computer Science, 1(1),2020, p.22.
  * [6] $\acute{U}$. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar and A. Thakurta, ”Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation”, arXiv preprint arXiv:2001.03618., 2020
  * [7] M.S. Alvim, M.E. Andrés, K. Chatzikokolakis, P. Degano and C. Palamidessi, ”Differential privacy: on the trade-off between utility and information leakage”, In International Workshop on Formal Aspects in Security and Trust .Springer, Berlin, Heidelberg, 2011, September,(pp. 39-54).
  * [8] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith ,”What can we learn privately?” SIAM Journal on Computing, 40(3),2011,(pp 793-826)
  * [9] A. M. Goon, M. K. Gupta, and B. Dasgupta, ”Fundamentals of Statistics, Volume ”,. Calcutta Statistical Association Bulletin, 17(2-3),1968,(pp-134–135), doi:10.1177/0008068319680206
  * [10] M. Lecuyer , V. Atlidakis , R. Geambasu , D. Hsu , and S. Jana . Certified robustness to adversarial examples with differential privacy. In2019 IEEE Symposium on Security and Privacy (SP) 2019 May 19 (pp. 656-672). IEEE.
  * [11] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. ”Distributed differential privacy via shuffling.” In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 375-403. Springer, Cham, 2019.
  * [12] Z. Li, T. Wang, M. Lopuhaä-Zwakenberg, N. Li, and B. Škoric. ”Estimating numerical distributions under local differential privacy.” In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 621-635. 2020.
  * [13] K. Chaudhuri, I. Jacob , and A. Machanavajjhala. ”Capacity bounded differential privacy.” In Advances in Neural Information Processing Systems, pp. 3469-3478. 2019.
  * [14] M. Asada, M. Yoshikawa, and Y. Cao. ”“When and Where Do You Want to Hide?”–Recommendation of Location Privacy Preferences with Local Differential Privacy.” In IFIP Annual Conference on Data and Applications Security and Privacy, pp. 164-176. Springer, Cham, 2019.


# Time–Varying Capacitors as Lossless
Two–Port Devices

Dimitri Jeltsema

(Balanced Energy Systems
HAN University of Applied Sciences
P.O. Box 2217, 6802 CE Arnhem, The Netherlands
Email<EMAIL_ADDRESS>
###### Abstract

Inspired by recent assertions that imply incorrectness of the classical
constitutive relationship of time–varying capacitance, energetic and
system–theoretic perspectives are invoked that, instead of incorrectness, show
incompleteness of the associated one–port device model. Based on dissipativity
and passivity theory, an energetic analysis is presented that naturally leads
to a complete two–port device model that is consistent with the laws of
thermodynamics.

##  1 Motivation

Recently, the paper “Origin of the Curie–von Schweidler law and the fractional
capacitor from time–varying capacitance” [13] asserted arguments to obtain a
physical interpretation to this century–old law of dielectrics. The exposition
in [13] starts by arguing that the derivation of this law requires a revision
of the classical charge–voltage relation of linear and time–varying
capacitors,

$Q(t)=C(t)V(t),$ (1)

where $Q$ represents the charge, $C$ the capacitance, $V$ the voltage, and $t$
represents time. The proposed revision of (1) is expressed in [13] as a
convolution between the time–varying capacitance and the time–derivative of
the associated voltage, i.e.,

$Q(t)=C(t)*\dot{V}(t).$ (2)

A similar type of revision is proposed in [5].

To substantiate the arguments against (1), the paper [13], and additionally
the response [14] to another critical analysis [1], discusses a simple example
in which an external voltage is applied to a linearly increasing capacitance
of the form $C(t)=C_{0}+\phi t$, with $C_{0},\phi>0$. The resulting current is
then obtained by taking the time–derivative of the charge, i.e.,

$I(t)=\dot{Q}(t)=\frac{d}{dt}\big{[}C(t)V(t)\big{]}=C(t)\dot{V}(t)+\dot{C}(t)V(t),$
(3)

which, for the assumed linearly increasing capacitance, implies that

$I(t)=C_{0}\dot{V}(t)+\phi t\dot{V}(t)+\phi V(t).$ (4)

Besides the fact that (3) is advocated in classical textbooks like [3, 4, 20],
and is also used in simulation programs like Matlab, Micro–Cap, or Pspice [2],
the argumentation in [13] proceeds with the evaluation of (4) at $t=0$ and
points out an apparent inconsistency as the initial capacitance $C(0)=C_{0}$
suggests that the initial current should read as

$I(0)=C_{0}\dot{V}(0),$ (5)

while (3) dictates that

$I(0)=C_{0}\dot{V}(0)+\phi V(0).$ (6)

Based on these considerations, [13] labels the term $\phi V(t)$ in (4) as an
anomaly arising from the constitutive relationship (1), and concludes (1) to
be erroneous.

Although at first glance this observation might seem conspicuous and
convincing, there is an elementary mathematical flaw in this reasoning that
can be easily resolved by a proper classification of (3). Nevertheless, there
are indeed some fundamental energetic and system–theoretic issues with the
device model (3) that will be the main focus of the remainder of the present
work.

##  2 Outline and contribution

The contribution of this paper is multi–folded. In Section 3, it will be
argued that (3) naturally defines an elementary linear ordinary differential
equation that generally consists of both a homogeneous and a particular
solution—something that appears to be overlooked in [13]. This renders the
initial arguments in [13] to advocate for (2) invalid, and the discussion is
proceeded with a short subsection about physical causality and concludes by
showing that (3) violates gauge symmetry. Section 4 addresses the fact that
(3) constitutes an electrical one–port device that is physically incomplete
since the mechanism that causes a capacitor to change its capacitance is
missing in the model. Based on the energetic and system–theoretic notions of
dissipativity and passivity, it is shown that (3) violates the First Law of
thermodynamics when the capacitance varies in a cyclic fashion. In Section 5,
the device model (3) is completed by considering a time–varying capacitor as a
two–port device, with an electrical port and a port that provides the
‘mechanical’ work to accomplish the change in the capacitance. Additionally,
Section 6 provides a consistent resolution to a long standing debate of a
non–cyclic example that is (close to) equivalent with the peculiar so–called
“Two–Capacitor Paradox.” The paper is concluded with some final remarks and a
short discussion about the proposed convolution relation (2).

##  3 First get the mathematics right…

…the rest is physics.111Conversely, after Rudolf Kálmán’s famous quote: “First
get the physics right, the rest is mathematics.” Indeed, it is not difficult
to observe that (3) rather—and most naturally—defines a linear ordinary
differential equation (ODE)

$\boxed{\dot{V}(t)+\frac{\dot{C}(t)}{C(t)}V(t)=f(t)}$ (7)

with forcing term $f(t)=I(t)/C(t)$. The solution to such standard ODE’s can be
found in virtually any undergraduate calculus textbook. Indeed, using the
method of integrating factors, the general solution to (7) is given by (see
e.g., [19, Section 9.5])

$V(t)=e^{-\alpha(t)}\int e^{\alpha(t)}f(t)dt+\gamma e^{-\alpha(t)},\
\dot{\alpha}(t)=\frac{\dot{C}(t)}{C(t)},$

where the constant $\gamma$ depends on the initial conditions. Clearly, this
solution consists of two parts: a particular (forced) solution and a
homogeneous (unforced) solution. The current $I(t)$ is the independent part of
the forcing term $f(t)$ that determines, together with $V(0)$, the
time–evolution of $V(t)$. Hence, in the voltage–current equation (3), the
independent variable is the supplied current, whereas the dependent variable
is the resulting capacitor voltage. To illustrate what goes wrong with the
reasoning in [13], let us return to the example of Section 1.

###  3.1 The complete solution of (3)

Continuing the example of [13] and [14], let $V(t)=at$, with $a>0$, and
$C(t)=C_{0}+\phi t$ as before. Substitution of the latter into (3) suggest
that the current will be given by

$I(t)=(C_{0}+2\phi t)a.$ (8)

Along the lines of [13], one would be tempted to conclude that $a=\dot{V}(t)$
and that the two terms on the right–hand side of (8) can be interpreted as two
capacitive currents that flow through two capacitors that are arranged in a
parallel combination of a constant capacitor $C_{0}$ and a time–varying
capacitor $2\phi t$. Such interpretation would be conflicting with the fact
that $C(t)$ equals $C_{0}+\phi t$ instead of $C_{0}+2\phi t$ (as is suggested
in Fig. 1 of [13]).

However, this reasoning fails since the mapping $at\mapsto I(t)$ that results
in (8) only considers the particular solution of the problem. Indeed, if we
conversely substitute (8) into (7), then the _complete_ solution will be

$V(t)=at+\frac{C_{0}}{C(t)}V(0)\ \Rightarrow\
\dot{V}(t)=a-\frac{C_{0}}{C^{2}(t)}\phi V(0),$ (9)

instead of just $\dot{V}(t)=a$. Hence, an equivalent parallel arrangement of
two capacitors connected to a voltage source $V(t)=at$ breaks down, and so
does the apparent contradiction between equations (5) and (6) at $t=0$. The
reason why the author of [13] was escorted to this apparent inconsistency in
the first place can perhaps be explained in terms of (physical) causality.

###  3.2 Physical causality

Although the time–differentiation in (3) of the voltage leading to the current
is (in principle) a causal operation, it is not physically realizable as such.
This becomes clear if one considers a (constant) capacitor directly in series
with an ideal battery. It is not physically possible to charge a capacitor
instantly. Indeed, whether the capacitance is constant or not, if a constant
voltage is applied to (3), then the associated current is instantly infinite
(i.e., the current would behave, at least theoretically, as a Dirac impulse).
Moreover, by solely considering the constitutive relation between charge and
voltage (1), the dynamical aspect of charging is neglected. Indeed, a
capacitor, either linear or nonlinear, time–varying or time–invariant,
accumulates charge according to

$Q(t)=Q(0)+\int\limits_{0}^{t}I(\tau)d\tau,$ (10)

which is not an instant process.

###  3.3 Violation of gauge symmetry

Gauge symmetry [15] requires that the laws of physics are invariant under
transformations like $V(t)\mapsto V(t)+\Psi$, where $\Psi$ is an arbitrary
(constant) reference potential. This implies that no experiment should be able
to measure the absolute potential, without reference to some external standard
such as an electrical ground or datum point. Moreover, if gauge symmetry holds
and energy is conserved, then charge must be conserved [15].

To test if (3) satisfies this principle, let us replace $V$ by $V+\Psi$ and
evaluate the result, i.e.,

$I(t)=\frac{d}{dt}\big{[}C(t)(V(t)+\Psi)\big{]}=C(t)\dot{V}(t)+\dot{C}(t)V(t)+\boxed{\dot{C}(t)\Psi}$

which readily implies that

$\frac{d}{dt}\big{[}C(t)V(t)\big{]}\neq\frac{d}{dt}\big{[}C(t)\big{(}V(t)+\Psi\big{)}\big{]},$
(11)

unless $C(t)$ is a constant!

Apart from conservation of charge, the next question that arises is what this
means for the energy conservation properties associated to the device model
(3).

##  4 Violation of the First Law of thermodynamics

For a device model to be physically consistent with the First Law of
thermodynamics, we need to assure that the energy supplied to the device
always equals, or is larger than, the amount of stored energy, i.e., the
device must be _passive_.222See the Appendix for a brief outline of
dissipativity and passivity theory and some selected references about these
concepts. For the device model (3), or its equivalent (7), that is initially
at rest, passivity amounts to the requirement that

$\int\limits_{0}^{t}V(\tau)I(\tau)d\tau\geq 0,$ (12)

for all $t\geq 0$.

###  4.1 One–port formulation

An equivalent way to formulate the current–voltage relationship (3) is by
selecting the charge $Q(t)$ as an internal state variable, and define the
linear and time–varying _one–port_ input–state–output system333This model is
in the form of a so–called input–state–output _port-Hamiltonian system_. The
interested reader is referred to [16] or [17] for details of such system
descriptions.

$\displaystyle\dot{Q}(t)$ $\displaystyle=I(t)\ \ \text{(input)},$ (13)
$\displaystyle\text{(output)}\ \ V(t)$ $\displaystyle=\frac{\partial
S}{\partial Q}\big{(}Q(t),t\big{)},$

with conjugated port–variables $(I,V)$ and

$S\big{(}Q(t),t\big{)}=\frac{1}{2C(t)}Q^{2}(t)$ (14)

represents the total energy stored in the capacitor at any instant of time
$t$. Indeed, differentiating (14) along the trajectories of (13) yields

$\frac{d}{dt}S\big{(}Q(t),t\big{)}=V(t)I(t)-\frac{1}{2}\dot{C}(t)V^{2}(t).$
(15)

The requirement for (13) to be passive is that

$\frac{d}{dt}S\big{(}Q(t),t\big{)}\leq V(t)I(t),$ (16)

and lossless if the latter holds with equality.

Obviously, for a constant capacitor $C(t)=C_{0}$, with $C_{0}>0$, this is
trivially satisfied as (16) holds with equality and therefore implies that
constant capacitors are lossless devices (as should be expected). On the other
hand, time–varying capacitors only satisfy (16) as long as $C(t)$ is such that

$\frac{1}{2}\dot{C}(t)V^{2}(t)\geq 0,$ (17)

for all time $t$.

For the example of Section 3.1, this requirement is readily satisfied as $\phi
V^{2}(t)\geq 0$, for all admissible capacitor voltages $V(t)$ and $\phi>0$.
Hence, this hypothetical device is not purely lossless, but generally
dissipates energy in moving from one state to another. The situation for the
practically relevant class of linear capacitors that vary in a cyclic fashion,
however, turns out to be quite different.

###  4.2 Linear cyclic capacitance

Consider again the current–voltage equation (3) or, equivalently, the linear
ODE (7) or the one-port formulation (13). Let us first consider a
time–interval $[t_{1},t_{2}]$ in which $C(t_{1})=C(t_{2})$ and
$V(t_{1})=V(t_{2})$. Then, instead of starting from the total stored energy
(14), consider the energy that is supplied to the device by the electrical
port $(V,I)$. Over one cycle the supplied energy is given by

$\displaystyle\oint\limits_{t_{1}}^{t_{2}}V(t)I(t)dt$
$\displaystyle=\oint\limits_{t_{1}}^{t_{2}}V(t)\frac{d}{dt}\big{[}C(t)V(t)\big{]}dt$
(18)
$\displaystyle=C(t)V^{2}(t)\bigg{|}_{t_{1}}^{t_{2}}-\oint\limits_{t_{1}}^{t_{2}}C(t)V(t)\dot{V}(t)dt$
$\displaystyle=\oint\limits_{t_{1}}^{t_{2}}\frac{1}{2}\dot{C}(t)V^{2}(t)dt,$

which again leads to the passivity condition (17).

The dissipativity and passivity theory of the Appendix implies that for _any_
linear cyclicly varying capacitance $C(t)$, that is either described by (3),
(7), or (13), there should _always_ exist a particular current excitation
profile that let us extract more energy from the device than it is supplied
with. This conclusion is completely in line with the one–port analysis of [6].
An explicit construction of such a current function will be given next.

Figure 1: A variable capacitor system.

###  4.3 An apparent ‘energy harvesting’ device

Consider the variable capacitor system depicted in Figure 1. Two plates are
shown, one of which is driven by a constant angular velocity
$\omega=\frac{1}{2}$ [rad/s], and let us adopt the example in [3, p. 304] in
which the plate arrangement is assumed to be such that capacitance between the
plates varies cyclicly according to

$C(t)=2+\sin(\omega t).$ (19)

For a purely sinusoidal current $I(t)=\cos(2\omega t)$ and $Q(0)=0$, the
device models (3) or (13) appear to be lossless since the supplied energy (18)
equals

$\oint\limits_{0}^{T}V(t)I(t)dt=0,$

where $T=2\pi/\omega=4\pi$ [s] is the time of one full cycle of the variable
capacitance. However, inspired by [12], selecting the following (zero-mean)
$4\pi$–periodic current profile

$\displaystyle I(t)$ $\displaystyle=\frac{5}{2}\sin(\omega
t)-\frac{1}{4}\cos(\omega t)-5\sin(2\omega t)$ (20)
$\displaystyle\qquad-\frac{5}{4}\cos(2\omega t)+\frac{11}{4}\cos(3\omega
t)-\frac{5}{4}\cos(4\omega t),$

yields that the supplied energy over one cycle equals

$\oint\limits_{0}^{T}V(t)I(t)dt\approx\boxed{-0.7\ \text{[joules]}}$

which shows that there is more energy gained from the device than it is
supplied with. Moreover, for each subsequent cycle, the gained energy
increases linearly with the number of cycles. This suggests that this device
is an _overunity_ system, or, in a more classical parlance, a _perpetual
motion_ machine of the first kind.

The gain of energy is also evident from the Lissajous plot in Figure 2; the
loop in the first quadrant has a counter–clockwise orientation (energy
release), whereas the loops in the third quadrant both have a clockwise
orientation (energy absorption); the energy release clearly exceeds the
absorption of energy. Thus, we can apparently harvest ‘free’ energy from a
cyclicly changing capacitor device that is either described by the
(incomplete) device model (3) or (13).

Figure 2: Lissajous plot of the voltage versus the charge of the
electromechanical system of Figure 1 according to the (incomplete) device
model (3) or (13).

##  5 Now, get the physics right…

The obvious reason why an apparent amount of energy can be extracted from the
cyclic capacitor device in Figure 1 is that there is also some sort of
mechanical torque required to change the dielectrics of the capacitor.
However, this torque–like quantity is not taken into consideration in the
device model (3) or (13). To fix this, the device model should be augmented
with a mechanism that causes the change in the capacitance. This introduces a
second degree of freedom that can be included by extending (3) or (13) with a
state equation of the form

$\dot{C}(t)=U(t),$

where $U(t)$ represents an independent external variable that causes the rate
of change in the capacitance.

###  5.1 Time–varying capacitor as two–port device

Concerning the device model (13), this will result in the following linear and
time–invariant state equations444See [16, p. 168] for a similar type of system
in the context of variable impedance control.

$\displaystyle\dot{Q}(t)$ $\displaystyle=I(t)$ (21a) $\displaystyle\dot{C}(t)$
$\displaystyle=U(t)$ (21b)

with the nonlinear and time–invariant conjugated outputs (compare to (15))

$\boxed{V(t)=\frac{Q(t)}{C(t)}}\ \ \text{and}\ \
\boxed{F(t)=-\frac{1}{2C^{2}(t)}Q^{2}(t)}$ (22)

and initial conditions $Q(0)=Q_{0}$ and $C(0)=C_{0}$, respectively.

Note that $U(t)$ has the units of Farads per second [F/s], and as such can be
interpreted as some kind of mechanical–like velocity. Consequently, the
associated conjugate output $F(t)$ must represent a mechanical–like force or
torque, known in classical electro–mechanics as the counter–electromotive
force or back EMF. Indeed, in the light of (21)–(22), the time–dependent
stored energy (14) now matures to a proper nonlinear and time–invariant state
function

$S\big{(}Q(t),C(t)\big{)}=\frac{1}{2C(t)}Q^{2}(t),$ (23)

for which the associated power–balance becomes

$\frac{d}{dt}S\big{(}Q(t),C(t)\big{)}=V(t)I(t)+F(t)U(t),$ (24)

for all time $t$.

The equality (24) readily implies that the device model (21)–(22) constitutes
a passive (in fact, _lossless_) _two–port_ device, with conjugated electrical
port variables $(I,V)$ and mechanical–like port variables $(U,F)$, and
therefore the device model (21)–(22) satisfies the First Law of
thermodynamics—as should be expected.

###  5.2 Mechanical side of the picture

Starting from the constitutive relationship (1), the two–port device model
(21)–(22) should be considered as the minimum set of equations that is needed
to be energetically consistent. The physical structure of the mechanism that
causes the capacitance to vary is still missing from the device model. Indeed,
apart from assuming perfectly conducting electrical wires and frictionless
mechanics, a practical rotating plate in Figure 1 will always experience some
moment of inertia. As a result, there will also be storage of kinetic energy
due to an induced angular momentum.

Assuming the moment of inertia, say $J$, is constant, the angular momentum $P$
is given by the constitutive relationship $P(t)=J\dot{\Theta}(t)$, where
$\Theta(t)$ represents the angular displacement of the rotating plate.
Consequently, the capacitance can be expressed as an explicit function of the
angular displacement, so that (1) is replaced by a constitutive relationship
of the form

$Q(t)=C\big{(}\Theta(t)\big{)}V(t)$ (25)

and (21b) is replaced by the dynamics of the mechanical subsystem.

For details and other examples that involve state–modulated capacitors, such
as capacitor microphones and micro electro–mechanical systems (MEMS), the
interested reader is referred to [16] and [18], and the references therein.

##  6 A two capacitor–like ‘paradox’

Although we mainly concentrated on capacitors that vary in a continuous cyclic
fashion, the proposed two–port device model (21)–(22) is also valid for
discontinuous and non–cyclic capacitive devices. To illustrate this, consider
a capacitor that is initially charged with a certain amount of charge, say
$Q$, and at a certain moment in time, say $t_{1}=0$, changes linearly to twice
its capacitance at $t_{2}=1$; see Figure 3.

Figure 3: A capacitor with a linear change in its dielectrics.

Since the total charge is conserved, the dynamics covering this time–varying
process is

$\displaystyle\dot{Q}(t)$ $\displaystyle=0,$ (26a) $\displaystyle\dot{C}(t)$
$\displaystyle=U(t),$ (26b)

with external ‘mechanical’ input

$U(t)=\left\\{\begin{array}[]{ccc}0&\text{for}&t<0,\\\ 1/T&\text{for}&0\leq
t<T,\\\ 0&\text{for}&t\geq T,\end{array}\right.$ (27)

with $T=t_{2}-t_{1}$. If the capacitance at $t\leq t_{1}$ is $C_{0}$, then the
energy stored in the capacitor at $t=t_{1}$ equals

$S\big{(}C(t_{1})\big{)}=\frac{1}{2C_{0}}Q^{2}.$ (28)

However, after the transition from $C$ to $2C$ is completed, the energy is
reduced to

$S\big{(}C(t_{2})\big{)}=\frac{1}{4C_{0}}Q^{2}.$ (29)

Now, where did this energy go?

Again, the most natural answer lies in the fact that we did not take the
mechanism that causes the change of the capacitance into account. Indeed,
differentiating the total energy at any arbitrary time $t$ along the
trajectories of (26) yields

$\frac{d}{dt}\left(\frac{1}{2C(t)}Q^{2}\right)=-\frac{1}{2}\frac{Q^{2}}{C^{2}(t)}\dot{C}(t)\equiv
F(t)U(t),$ (30)

which, in turn, implies that

$S\big{(}C(t_{2})\big{)}-S\big{(}C(t_{1})\big{)}=\int\limits_{t_{1}}^{t_{2}}F(t)U(t)dt=-\frac{1}{4C_{0}}Q^{2}.$
(31)

Interestingly, note that in the limit $t_{2}\to t_{1}$, and subsequently,

$\lim_{T\to 0}U(t)=\delta(t),$ (32)

with $\delta(t)$ the Dirac impulse function, the result still holds and
reduces to a similar problem known as the “Two Capacitor Paradox;” see [7, p.
155] and [9] and the references therein. Hence, the resolution to this paradox
is that the apparent ‘lost’ energy is due to the mechanism that causes the
change in the system. This is to be expected, and in full agreement with the
analysis of [9], since ‘mechanical’ work is required to change the dielectrics
of the capacitor or to operate an ideal switching device that connects to
identical capacitors $C_{0}$, one of which is initially charged to a certain
charge level $Q$ and the other initially uncharged, at a certain instant of
time.

##  7 Final remarks

The main conclusion to be drawn from the perspectives of this paper is that
the classical charge–voltage relationship (1) is generally valid—at least
within the context of circuit–theoretic device models and their postulates.
However, a naive application of the one–port device model (3) generally leads
to incomplete and thermodynamically inconsistent results. To avoid such
issues, the proposed two–port model (21)–(22) should be used instead.

On the other hand, as briefly outlined in Section 5.2, if one includes
physical details about the mechanism that causes the change in capacitance,
then a capacitor that explicitly depends on time generally loses its
relevance.

Furthermore, although only time–varying capacitance is discussed, the same
analysis can be carried over verbatim to a time–varying inductance that is
described by a constitutive relationship of the form $\Phi(t)=L(t)I(t)$ and a
(naive) application of Faraday’s law, $V(t)=\dot{\Phi}(t)$, yielding

$V(t)=\frac{d}{dt}\big{[}L(t)I(t)\big{]}=L(t)\dot{I}(t)+\dot{L}(t)I(t),$ (33)

where $\Phi(t)$ denotes the flux–linkage.

Finally, concerning the constitutive relationship (2) as proposed in [13], it
is well–known, see e.g., [10], that in electromagnetic media there are
situations that the material itself may have some sort of inherent memory. In
such case, the constitutive relationships associated to the permittivity,
permeability and conductivity might involve convolutions between the intensive
and extensive field variables. However, it is rather doubtful if such cases
can be simplified to quasi–static circuit–theoretic models without violating
any physical laws.

## References

  * [1] A. Allagui, A.S. Elwakil, C. Psychalinos, Comment on “Origin of the Curie?von Schweidler law and the fractional capacitor from time-varying capacitance” [J. Pow. Sources 532 (2022) 231309], Journal of Power Sources, Volume 551, 2022, 232166.
  * [2] D. Biolek, Z. Kolka, V. Biolkova, “Modeling time-varying storage components in PSpice,” In Proc. Electronic Devices and Systems IMAPS CS International Conference EDS, pp. 39–44, 2007.
  * [3] L.O. Chua, C.A. Desoer and E.S. Kuh, Linear and Nonlinear Circuits, McGraw–Hill Inc., 1987.
  * [4] C.A. Desoer and E.S. Kuh, Basic Circuit Theory, McGraw–Hill Book Company, 1969.
  * [5] M.E. Fouda, A. Allagui, A.S. Elwakil, S. Das, C. Psychalinos, and A.G. Radwan, “Nonlinear charge–voltage relationship in constant phase element,” AEU-Int. J. Electron. Commun., 117:153104, 2020.
  * [6] T.T. Georgiou, F. Jabbari and M.C. Smith, “Principles of lossless adjustable one–ports,” IEEE Transactions on Automatic Control, vol. 65, no. 1, pp. 252-262, Jan. 2020.
  * [7] A.R. Hambley, Electrical Engineering: Principles and Applications, 6th Edition, Pearson Education Limited, 2014.
  * [8] D.J. Hill and P.J. Moylan, “Dissipative dynamical systems: basic input-output and state properties,” Journal of the Franklin Institute, 309(5):327-357, 1980.
  * [9] J. Hoekstra, “A solution of the two–capacitor problem through its similarity to single-electron electronics,” IEEE Open Journal of Circuits and Systems, Vol. 1, pp. 13–21, 2020, DOI: 10.1109/OJCAS.2020.2977216.
  * [10] A.T. de Hoop, Handbook of Radiation and Scattering of Waves, Academic Press, 1995.
  * [11] D. Jeltsema and J.M.A. Scherpen, “Multidomain modeling of nonlinear networks and systems,” IEEE Control Systems Magazine, Vol. 29, No. 4, pp. 28–59, July 2009.
  * [12] D. Jeltsema and A.J. van der Schaft, “Ideal memcapacitors and meminductors are overunity devices,” Scientific Reports, 10, 16688, 2020, DOI: 10.1038/s41598–020–73833–3.
  * [13] V. Pandley, “Origin of the Curie–von Schweidler law and the fractional capacitor from time–varying capacitance, Journal of Power Sources, 532, 231309, 2022.
  * [14] V. Pandey, Response to “Comment on ‘Origin of the Curie–von Schweidler law and the fractional capacitor from time–varying capacitance [J. Power Sources 532 (2022) 231309]’ ”, Journal of Power Sources, Volume 551, 2022, 232167.
  * [15] D.H. Perkins, Introduction to High-Energy Physics, Addison-Wesley, 1982.
  * [16] A.J. van der Schaft, $L_{2}$-Gain and Passivity Techniques in Nonlinear Control, 3rd Edition, Springer International, 2017.
  * [17] A.J. van der Schaft and D. Jeltsema, Port-Hamiltonian Systems Theory: An Introductory Overview, Foundations and Trends in Systems and Control, NOW Publishers, 2014.
  * [18] A.J. van der Schaft and D. Jeltsema, “Limits to Energy Conversion,” in IEEE Trans. on Automatic Control, vol. 67, no. 1, pp. 532–538, Jan. 2022, DOI: 10.1109/TAC.2021.3075652.
  * [19] J. Stewart, Calculus, 6th Edition, Thomson Brooks/Cole, 2008.
  * [20] M.E. van Valkenburg, Network Analysis, Prentice–Hall, Inc., 1955.
  * [21] J.C. Willems, “Dissipative dynamical systems, part I: general theory,” Arch. Rat. Mech. and Analysis, 45(5):321–351, 1972.
  * [22] J.C. Willems, “Qualitative behavior of interconnected systems,” Annals of Systems Research, 3:61–80, 1973.

## Appendix: Dissipativity and passivity theory

Consider a system with state vector $x$ and a vector of external (e.g., input
and output) variables $w$. Consider a scalar–valued supply rate $s(w)$. A
function $S(x)$ is said to be a storage function (with respect to the supply
rate $s$) if along all trajectories of the system and for all $t_{1}\leq
t_{2}$ and $x(t_{1})$ it satisfies the dissipation inequality (see e.g., [8],
[16], and [21])

$S\big{(}x(t_{2})\big{)}-S\big{(}x(t_{1})\big{)}\leq\int\limits_{t_{1}}^{t_{2}}s\big{(}w(t)\big{)}dt.$
(34)

Interpreting $s\big{(}w(t)\big{)}$ as ‘power’ supplied to the system at time
$t$, and $S\big{(}x(t)\big{)}$ as stored ‘energy’ while at state $x(t)$, this
means that increase of the stored energy can only occur due to externally
supplied power.

Following [21]. the system is called dissipative (with respect to the supply
rate $s$) if there exists a nonnegative storage function $S$.555Since addition
of an arbitrary constant to a storage function again leads to a storage
function, the requirement of nonnegativity of $S$ can be relaxed to $S$ being
bounded from below. Furthermore, it is called lossless (with respect to $s$)
if there exists a nonnegative storage function satisfying the dissipation
inequality (34) with equality.

An external characterization of dissipativity, in terms of the behavior of the
$w$ trajectories, is the following [21]. Define for any $x$ the expression
(possibly infinite)

$S_{a}(x):=\sup_{w,T\geq 0}-\int\limits_{0}^{T}s\big{(}w(t)\big{)}dt,$ (35)

where the supremum is taken over all external trajectories $w(\cdot)$ of the
system corresponding to initial condition $x(0)=x$, and all $T\geq 0$.
Obviously, $S_{a}(x)\geq 0$. Then the system is dissipative with respect to
the supply rate $s$ if and only if $S_{a}(x)$ is finite for every $x$.

Interpreting as above $s(w)$ as ‘power’ supplied to the system, $S_{a}(x)$ is
the maximal ‘energy’ that can be extracted from the system at initial
condition $x$, and the system is dissipative if and only if this maximal
‘energy’ is finite for any $x$. Furthermore, if $S_{a}(x)$ is finite for every
$x$ then $S_{a}$ is itself a non-negative storage function, and is in fact the
minimal nonnegative storage function (generally among many others).

Dropping the requirement of non-negativity of the storage function $S$ leads
to the notion of cyclo–dissipativity, respectively cyclo–losslessness [16,
22]. First note that if a general, possibly indefinite, storage function $S$
satisfies (34), then for all cyclic trajectories, i.e., such that
$x(t_{1})=x(t_{2})$, we have that

$\oint\limits_{t_{1}}^{t_{2}}s\big{(}w(t)\big{)}dt\geq 0,$ (36)

which holds with equality in case (34) holds with equality. This leads to the
following external characterization of cyclo-dissipativity and
cyclo–losslessness.

A system is cyclo-dissipative if (36) holds for all $t_{2}\geq t_{1}$ and all
external trajectories $w$ such that $x(t_{2})=x(t_{1})$. In case (36) holds
with equality, we speak about cyclo–losslessness. Furthermore, the system is
called cyclo-dissipative with respect to $x^{*}$ if (36) holds for all
$t_{2}\geq t_{1}$ and all external trajectories $w$ such that
$x(t_{2})=x(t_{1})=x^{*}$, and cyclo–lossless with respect to $x^{*}$ if this
holds with equality.

Interpreting again $s(w)$ as the power provided to the system,
cyclo–dissipativity thus means that for any cyclic trajectory the net amount
of energy supplied to the system is non-negative, and zero in case of
cyclo–losslessness.

In case of the passivity supply rate

$s(w)=s(u,y)=y^{T}u,$ (37)

where $w=(u,y)$ and $u$ and $y$ are equally dimensioned vectors, the
terminology ‘dissipativity’ in all of the above is replaced by the classical
terminology of passivity. In this case $u$ and $y$ typically are vectors of
power–conjugate variables, like forces and velocities, and voltages and
currents.