#  $\mathsf{Harpocrates}$: Privacy-Preserving and Immutable Audit Log for
Sensitive Data Operations

Mohit Bhasi Thazhath, Jan Michalak, Thang Hoang  Department of Computer
Science, Virginia Tech, USA
{mohitbt, janmichalak<EMAIL_ADDRESS>
###### Abstract

The audit log is a crucial component to monitor fine-grained operations over
sensitive data (e.g., personal, health) for security inspection and assurance.
Since such data operations can be highly sensitive, it is vital to ensure that
the audit log achieves not only validity and immutability, but also
confidentiality against active threats to standard data regulations (e.g.,
HIPAA) compliance. Despite its critical needs, state-of-the-art privacy-
preserving audit log schemes (e.g., Ghostor (NSDI ’20), Calypso (VLDB ’19)) do
not fully obtain a high level of privacy, integrity, and immutability
simultaneously, in which certain information (e.g., user identities) is still
leaked in the log.

In this paper, we propose $\mathsf{Harpocrates}$, a new privacy-preserving and
immutable audit log scheme. $\mathsf{Harpocrates}$ permits data store, share,
and access operations to be recorded in the audit log without leaking
sensitive information (e.g., data identifier, user identity), while permitting
the validity of data operations to be publicly verifiable.
$\mathsf{Harpocrates}$ makes use of blockchain techniques to achieve
immutability and avoid a single point of failure, while cryptographic zero-
knowledge proofs are harnessed for confidentiality and public verifiability.
We analyze the security of our proposed technique and prove that it achieves
non-malleability and indistinguishability. We fully implemented
$\mathsf{Harpocrates}$ and evaluated its performance on a real blockchain
system (i.e., Hyperledger Fabric) deployed on a commodity platform (i.e.,
Amazon EC2). Experimental results demonstrated that $\mathsf{Harpocrates}$ is
highly scalable and achieves practical performance.

##  I Introduction

Remote data storage systems have become predominant in the past decade due to
the growth of cloud computing. Cloud Service Providers (CSPs) have dedicated
resources to store data, and have developed a suite of services to support it
such as AWS S3, Azure Blobs, GCP Buckets. The widespread use of cloud data
storage has made it easy to share/access remote data.

Given that CSPs generally maintain a vast amount of user data, many of which
can be highly sensitive (e.g., personal, health), it is vital to maintain an
audit log that records all the data operations (e.g., sharing, access
activities) to support system integrity inspection and critical security
assurances such as intrusion detection and problem analysis [1]. Many data
audit log schemes have been proposed to record fine-grained operations (e.g.,
read, write, share) over sensitive data (e.g., Electronic Health Records
(EHRs) [2, 3], supply chains [4, 5, 6, 7]) in a tamper-resistant and immutable
manner.

Despite their merits, achieving the immutability and integrity of the audit
log may not be sufficient to ensure security against active threats. This is
because the audit log contains all data operations (i.e., metadata), which can
reveal significant sensitive information. By analyzing the data log, the
adversary can obtain the needed information without having to access the
actual data [8]. Such metadata leakage has become notorious in related areas
such as communication surveillance. A former NSA General Counsel stated, “
_Metadata absolutely tells you everything about somebody’s life_ ” [9]. Due to
the sensitivity of metadata, it is vital to ensure integrity and
confidentiality of audit logs as indicated in standard data regulations such
as The Health Insurance Portability and Accountability Act of 1996 (HIPAA)
[10].

To enable both privacy and integrity, several privacy-preserving data audit
log schemes have been proposed. Preliminary constructions permit data
operations to be logged in a single server with privacy and integrity
guarantees using cryptographic tools such as digital signatures and symmetric
encryption [11, 12]. Despite their merits, such centralized approaches suffer
from a single point of failure, in which the corrupted server can compromise
the validity and confidentiality of the audit log. To address single point of
failure, several decentralized privacy-preserving audit log approaches have
been proposed using blockchain techniques [13, 14, 15, 16, 17, 18, 19].
However, there are certain limitations to these techniques. For example,
Droplet [17] offers confidentiality but not anonymity. Ghostor [18] records
data sharing activities with anonymity, but the validity can only be verified
privately by the data owner. This requires all the users to participate in the
audit process to verify the validity of the data operations, thereby reducing
the audit transparency. Calypso [19] achieves partial anonymity (i.e., leaks
data owner identity) and private verifiability.

Research gaps. Given that existing data logging techniques lack a certain
degree of anonymity, integrity, confidentiality, and transparency, our
objective is to design a new privacy-preserving audit log scheme that can
offer all desirable security properties for standard data regulations
compliance.

Contribution. In this paper, we propose $\mathsf{Harpocrates}$, a new privacy-
preserving and immutable audit log scheme for sensitive data operations.
$\mathsf{Harpocrates}$ permits data operations (i.e., store, share, access) to
be recorded in the audit log with validity, confidentiality, and public
verifiability guarantees. $\mathsf{Harpocrates}$ makes use of blockchain
technologies (e.g., distributed ledger) to achieve immutability and validity,
while confidentiality and public verifiability are achieved using advanced
cryptographic techniques such as zero-knowledge proofs [20].

TABLE I: Comparison of $\mathsf{Harpocrates}$ with prior works.

Scheme |  Audit Log  Confidentiality |  Audit Log  Anonymity | Temporal Access Control | Validity Verifiability
---|---|---|---|---
Store Record | Share Record | Access Record
Calypso [19] | ✓ | Partial$\dagger$ | ✗ | Private | Private | Private
Ghostor [18] | ✓ | ✓ | ✗ | Private | Private | Private
Droplet [17] | ✓ | ✗$\dagger$ | ✗ | Not Verifiable | Public | Not Verifiable
$\mathsf{Harpocrates}$ | ✓ | ✓ | ✓ | Public | Public | Public

  * •

$\dagger$ Calypso and Droplet do not hide data owner identity.

$\mathsf{Harpocrates}$ achieves the following properties.

  * •

Record Immutability: All the data operation records cannot be modified by
anyone.

  * •

Full Anonymity: The identity of the data and the user(s) remain hidden all the
time. This security guarantee is stronger than existing works (e.g., [19,
17]).

  * •

Publicly Verifiable Validity: Validity of the data operations (e.g., whether
the share/access is performed by an authorized user) can be publicly verified
by anyone. This improves audit transparency such that all the data users do
not need to participate during the audit process.

  * •

Temporal Access Control: Restricts the time for which the data can be
accessed. This is useful when operating on highly sensitive data like EHRs.

§ I compares $\mathsf{Harpocrates}$ with state-of-the-art techniques. We
rigorously analyze the security of our proposed technique and prove that it
achieves standard security notions (non-malleability, indistinguishability).
Finally, we implemented our technique and deployed it on a commodity platform
(Amazon EC2) to evaluate its efficiency. Experimental results showed that
$\mathsf{Harpocrates}$ is highly scalable (§ VII) and practical. Therefore,
$\mathsf{Harpocrates}$ can be used for sensitive data storage applications
that require privacy-preserving audit log such as EHRs [13, 14] or supply
chains [15, 16].

##  II Preliminaries

###  II-A Notation

We denote $||$ as the concatenation operator. Let $\lambda$ be a security
parameter, $\mathsf{negl}(\cdot)$ be a negligible function. We denote
$H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$ as a collision-resistant hash
function. $r\leftarrow\mathsf{PRF}(s)$ is a pseudorandom function that outputs
a pseudorandom $r$ given a seed $s$. Let
$\mathcal{E}=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be an asymmetric
encryption, in which
$(\mathsf{pk}_{\mathsf{adr}},\mathsf{sk}_{\mathsf{adr}})\leftarrow\mathcal{E}.\mathsf{Gen}(1^{\lambda})$
generates a public and private key pair given a security parameter $\lambda$;
$c\leftarrow\mathcal{E}.\mathsf{Enc}({\mathsf{pk}_{\mathsf{adr}}},m)$ encrypts
a plaintext $m$ under public key $\mathsf{pk}_{\mathsf{adr}}$;
$m\leftarrow\mathcal{E}.\mathsf{Dec}({\mathsf{sk}_{\mathsf{adr}}},c)$ decrypts
a ciphertext $c$ with private key $\mathsf{sk}_{\mathsf{adr}}$. Let
$\Sigma=(\mathsf{Gen},\mathsf{Sign},\mathsf{Verify})$ be a digital signature,
where
$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})\leftarrow\Sigma.\mathsf{Gen}(1^{\lambda})$
generates a public and private key pair;
$\sigma\leftarrow\Sigma.\mathsf{Sign}({\mathsf{sk}_{\mathsf{sig}}},m)$
produces a signature $\sigma$ for message $m$ under private key
$\mathsf{sk}_{\mathsf{sig}}$;
$\\{0,1\\}\leftarrow\Sigma.\mathsf{Verify}(\mathsf{pk}_{\mathsf{sig}},m,\sigma)$
verifies whether $\sigma$ is a valid signature of $m$ using public key
$\mathsf{pk}_{\mathsf{sig}}$.

###  II-B Cryptographic Building blocks

Commitment Scheme. A commitment scheme is a tuple of Probabilistic Polynomial
Time (PPT) algorithms $(\mathsf{Com}.\mathcal{G},\mathsf{Com})$ –

  * •

$\mathsf{pp}\leftarrow\mathsf{Com}.\mathcal{G}(1^{\lambda})$: Given a security
parameter $\lambda$, it outputs public parameters $\mathsf{pp}$.

  * •

$\mathsf{cm}\leftarrow\mathsf{Com}_{r}(m,\mathsf{pp})$: Given a message $m$
and a trapdoor $r$, it outputs a commitment $\mathsf{cm}$.

A commitment scheme is binding if for any PPT adversary $\mathcal{A}$ such
that $\mathsf{pp}\leftarrow\mathsf{Com}.\mathcal{G}(1^{\lambda})$,
$(m_{0},m_{1},r_{0},r_{1})\leftarrow\mathcal{A}(\mathsf{pp})$, it holds that
$\mathsf{Pr}\left[\mathsf{Com}_{r_{0}}(m_{0},\mathsf{pp})=\mathsf{Com}_{r_{1}}(m_{1},\mathsf{pp})\land
m_{0}\neq m_{1}\right]\leq\mathsf{negl}(\lambda)$; hiding if for any PPT
$\mathcal{A}$ such that
$(m_{0},m_{1})\leftarrow\mathcal{A}(\mathsf{pp}),b\xleftarrow{\$}{0,1},r\xleftarrow{\$}\\{0,1\\}^{\lambda},\mathsf{cm}\leftarrow\mathsf{Com}_{r_{b}}(m_{b},\mathsf{pp}),b^{\prime}\leftarrow\mathcal{A}(\mathsf{cm})$,
it holds that
$|\mathsf{Pr}[b=b^{\prime}]-\frac{1}{2}|\leq\mathsf{negl}(\lambda)$.

Merkle Tree. Merkle tree permits to commit to a set of values with the ability
to reveal an element in the committed set later (proof of membership). Given
$\vec{m}=(m_{1},m_{2},m_{3},\dotsc,m_{n})$, it first initializes a binary tree
$T$ with $n$ leaves and $H(m_{i})$ be the $i$-th leaf node. $T$ is built
bottom-up, where each non-leaf node $t$ of $T$ is computed by computing the
hash of its child nodes $t_{\mathsf{l}}$ and $t_{\mathsf{r}}$, i.e.,
$t=H(t_{\mathsf{l}}||t_{\mathsf{r}})$. To prove $m_{i}\in\vec{m}$, the prover
reveals $\mathsf{path}$ from $\mathsf{rt}$ to $H(m_{i})$, where $\mathsf{rt}$
is root of $T$ and $\mathsf{path}$ is the set of sibling nodes along the path
from $m_{i}$ to $\mathsf{rt}$. The verifier recomputes $\mathsf{rt}$ using
$\mathsf{path}$ for membership verification.

Given an updated set $\vec{m^{\prime}}$, where $m_{i}\in\vec{m^{\prime}}$ is
the updated value. The prover updates $i^{th}$ leaf with $H(m^{\prime}_{i})$,
recomputes non-leaf nodes along the path from $H(m^{\prime}_{i})$ to
$\mathsf{rt}$ in logarithmic time, and outputs updated root
$\mathsf{rt}^{\prime}$.

Argument of Knowledge. An argument of knowledge for an NP relation
$\mathcal{R}$ is a protocol between a prover $\mathcal{P}$ and a verifier
$\mathcal{V}$, in which $\mathcal{P}$ convinces $\mathcal{V}$ that it knows a
witness $w$ for some input in an NP language $x\in\mathcal{L}$ such that
$(x,w)\in\mathcal{R}$. Formally speaking, a zero-knowledge argument of
knowledge is a tuple of PPT algorithms
$\mathsf{zkp}=(\mathcal{G},\mathcal{P},\mathcal{V})$ as follows.

  * •

$\mathsf{pp}\leftarrow\mathsf{zkp}.\mathcal{G}(1^{\lambda})$: Given a security
parameter $\lambda$, it outputs public parameters $\mathsf{pp}$.

  * •

$\pi\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$: Given a statement
$x$ and a witness $w$, it generates a proof $\pi$ to show
$(x,w)\in\mathcal{R}$.

  * •

$\\{0,1\\}\leftarrow\mathsf{zkp}.\mathcal{V}(x,\pi,\mathsf{pp})$: Given a
statement $x$ and a proof $\pi$, it outputs $1$ if $\pi$ is valid and
$(x,w)\in\mathcal{R}$, else it outputs 0.

An argument of knowledge is complete if for any $(x,w)\in\mathcal{R}$,
$\mathsf{pp}\leftarrow\mathsf{zkp}.\mathcal{G}(1^{\lambda})$,
$\pi\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$, it holds that
$\mathsf{Pr}\left[\mathsf{zkp}.\mathcal{V}(x,\pi,\mathsf{pp})=1\right]=1$; is
sound iff for any PPT prover $\mathcal{P}^{*}$, there exists a PPT extractor
$\mathcal{E}$, when given the entire execution and randomness of
$\mathcal{P}^{*}$, $\mathcal{E}$ can extract a witness $w$ such that
$\mathsf{pp}\leftarrow\mathsf{zkp}.\mathcal{G}(1^{\lambda})$,
$\pi^{*}\leftarrow\mathcal{P}^{*}(x,\mathsf{pp})$,
$w\leftarrow\mathcal{E}^{\mathcal{P}^{*}}(x,\pi^{*},\mathsf{pp})$ and
$\mathsf{Pr}\left[\mathsf{zkp}.\mathcal{V}(x,\pi,\mathsf{pp})=1\land(x,w)\notin\mathcal{R}\right]\leq\mathsf{negl}(\lambda)$;
is zero-knowledge iff for any PPT verifier $\mathcal{V}^{*}$ there exists
simulators $(S_{1},S_{2})$ –

$\mathsf{Pr}\left[\begin{array}[]{r}\mathsf{pp}\leftarrow\mathsf{zkp}.\mathcal{G}(1^{\lambda})\\\
\pi\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})\\\
\mathsf{zkp}.\mathcal{V}(x,\pi,\mathsf{pp})=1\end{array}\right]\approx\mathsf{Pr}\left[\begin{array}[]{r}\mathsf{pp}\leftarrow
S_{1}(1^{\lambda})\\\ \pi\leftarrow S_{2}(x,\mathsf{pp})\\\
\mathcal{V}^{*}(x,\pi,\mathsf{pp})=1\end{array}\right]$

##  III Models

System Model. In our system, there are three types of participants: (i) The
data owner $\mathcal{O}$ who owns some data; (ii) The data user $\mathcal{U}$
who would like to access $\mathcal{O}$’s data; (iii) The storage provider
$\mathcal{S}$ that provides storage facilities to store $\mathcal{O}$’s data
remotely. Our system permits data storage, sharing, and access between these
participants while, at the same time, _recording_ all the data operations in a
distributed audit log for auditability. A Privacy-preserving and Immutable
Audit Log (PIAL) scheme consists of the following PPT algorithms –

  * •

$(\mathcal{L},\mathsf{pp})\leftarrow\mathsf{Init}(1^{\lambda},N)$: Given a
security parameter $\lambda$, and the maximum number of supported operations
$N$, it outputs an initial distributed audit log $\mathcal{L}$ and public
parameters $\mathsf{pp}$.

  * •

$(\mathsf{pk}_{\mathsf{adr}},\mathsf{sk}_{\mathsf{adr}})\leftarrow\mathsf{Register}(1^{\lambda})$:
Given a security parameter $\lambda$, it outputs an address-key pair
$(\mathsf{pk}_{\mathsf{adr}},\mathsf{sk}_{\mathsf{adr}})$ as an identifier for
the participant.

  * •

$(\mathsf{tk}_{\mathsf{str}},\mathsf{tx}_{\mathsf{str}})\leftarrow\mathsf{Store}(D,\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},\mathsf{pp}$):
Given data $D$, $\mathcal{O}$’s private identity
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$, $\mathcal{S}$’s public identity
$\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}$, it outputs a store token
$\mathsf{tk}_{\mathsf{str}}$ and a store record $\mathsf{tx}_{\mathsf{str}}$.

  * •

$(\mathsf{tk}_{\mathsf{own}},\mathsf{tx}_{\mathsf{own}})\leftarrow\mathsf{AssignOwner}(\mathsf{tk}_{\mathsf{str}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pp})$:
Given $\mathsf{tk}_{\mathsf{str}}$, $\mathcal{S}$’s private identity
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}$, and $\mathcal{O}$’s public
identity $\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}}$, it outputs an ownership
token $\mathsf{tk}_{\mathsf{own}}$, which permits $\mathcal{O}$ to share her
data stored on $\mathcal{S}$ later, and create a record of ownership
$\mathsf{tx}_{\mathsf{own}}$.

  * •

$(\mathsf{tk}_{\mathsf{shr}},\mathsf{tx}_{\mathsf{shr}})\leftarrow\mathsf{Share}(\mathsf{tk}_{\mathsf{own}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},\mathsf{ts},\mathsf{pp})$:
Given $\mathsf{tk}_{\mathsf{own}}$, $\mathcal{O}$’s private identity
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$, $\mathcal{U}$’s public identity
$\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}}$, a share expiry timestamp
$\mathsf{ts}>0$, it outputs a data share token $\mathsf{tk}_{\mathsf{shr}}$
that is only valid up to $\mathsf{ts}$, and a record of share
$\mathsf{tx}_{\mathsf{shr}}$.

  * •

$(\mathsf{tk}_{\mathsf{acc}},\mathsf{tx}_{\mathsf{acc}})\leftarrow\mathsf{Access}(\mathsf{tk}_{\mathsf{shr}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}.\mathsf{pp})$:
Given $\mathsf{tk}_{\mathsf{shr}}$, $\mathcal{U}$’s private identity
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}}$, $\mathcal{S}$’s public identity
$\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}$, it outputs a data access token
$\mathsf{tk}_{\mathsf{acc}}$ (if $\mathsf{tk}_{\mathsf{shr}}$ is not expired)
and a record of access $\mathsf{tx}_{\mathsf{acc}}$.

  * •

$\\{0,1\\}\leftarrow\mathsf{VerifyLog}(\mathsf{tx},\mathcal{L},\mathsf{pp})$:
Given a record $\mathsf{tx}$ and audit log $\mathcal{L}$, it outputs $1$ if
the record is valid else $0$.

Threat and Security Models. We assume participants do not trust each other,
i.e., they can behave maliciously toward the records created by other
participants. The adversary is curious about the record content, e.g., who is
the owner of a particular data, whom the data is shared with or accessed by,
and what data is being shared or accessed. The adversary may also attempt to
modify the record to compromise validity or to gain unauthorized access. We
aim to achieve integrity and confidentiality properties for the audit log via
record non-malleability and audit log indistinguishability as follows.

###### Definition 1 (Record Non-Malleability).

Let $\Pi$ be a candidate PIAL scheme. Consider experiment
$\texttt{NMGame}_{\Pi,\mathcal{A}}(\lambda)$ between the adversary
$\mathcal{A}$ and the challenger $\mathcal{C}$. $\mathcal{C}$ samples
$\mathsf{pp}\leftarrow\mathsf{Init}(1^{\lambda})$ and sends $\mathsf{pp}$ to
$\mathcal{A}$. Then, $\mathcal{C}$ initializes a PIAL oracle
$\mathcal{O}^{\mathsf{PIAL}}$ using $\mathsf{pp}$ with audit log
$\mathcal{L}$. At each time step, $\mathcal{A}$ adaptively specifies a query
$q\in\\{\mathsf{CreateAddress}$, $\mathsf{Store}$, $\mathsf{AssignOwner}$,
$\mathsf{Share}$, $\mathsf{Access}\\}$ to $\mathcal{C}$. $\mathcal{C}$
forwards $q$ to $\mathcal{O}^{\mathsf{PIAL}}$, receives a response and
forwards it to $\mathcal{A}$. $\mathcal{C}$ also provides the view of
$\mathcal{L}$ to $\mathcal{A}$. $\mathcal{A}$ outputs a record
$\mathsf{tx}^{*}$ and let $\mathcal{T}$ be the set of records with the same
type of $\mathsf{tx}^{*}$ that $\mathcal{O}^{\mathsf{PIAL}}$ generates during
the query phase.

If there exists a record $\mathsf{tx}\in\mathcal{T}$ created in response to a
query, $\mathcal{A}$ wins and outputs 1 iff the following conditions hold –
(i) $m^{*}\neq m$; (ii)
$\mathsf{VerifyLog}(\mathsf{tx}^{*},\mathsf{pp},\mathcal{L}^{\prime})=1$,
where $\mathcal{L}^{\prime}$ is the state of the audit log preceding
$\mathsf{tx}$; iii) if $\mathsf{tx}^{*}$ is a record of ownership,
$\mathsf{sn}^{*}=\mathsf{sn}$. Otherwise, it outputs 0.

$\Pi$ is said to achieve _record non-malleability_ if
$\mathsf{Pr}[{\texttt{NMGame}}_{\Pi,\mathcal{A}}(\lambda)=1]\leq\mathsf{negl}(\lambda)$.

###### Definition 2 (Audit Log Indistinguishability).

Let $\Pi$ be a candidate PIAL scheme. Consider experiment
$\texttt{IndGame}_{\Pi,\mathcal{A}}(\lambda)$ between $\mathcal{A}$ and
$\mathcal{C}$. $\mathcal{C}$ first samples a random bit
$b\xleftarrow{\$}\\{0,1\\}$,
$\mathsf{pp}\leftarrow\mathsf{Com}.\mathcal{G}(1^{\lambda})$ and initializes
two PIAL oracles $\mathcal{O}^{\mathsf{PIAL}}_{0}$ and
$\mathcal{O}^{\mathsf{PIAL}}_{1}$, where each oracle
$\mathcal{O}^{\mathsf{PIAL}}_{i}$ has a separate audit log $\mathcal{L}_{i}$
as well as internal variables. At each time step, $\mathcal{A}$ adaptively
specifies two queries $Q,Q^{\prime}$ of the same type (one of
$\mathsf{Store},\mathsf{AssignOwner},\mathsf{Share},\mathsf{Access}$).
$\mathcal{C}$ forwards $Q$ to $\mathcal{O}^{\mathsf{PIAL}}_{0}$, $Q^{\prime}$
to $\mathcal{O}^{\mathsf{PIAL}}_{1}$ and receives the corresponding answers
$R_{0},R_{1}$. $\mathcal{C}$ forwards $(R_{b},R_{1-b})$ to $\mathcal{A}$.
$\mathcal{C}$ also provides to $\mathcal{A}$ two ledgers
$\mathcal{L}_{\mathsf{left}}=\mathcal{L}_{b}$,
$\mathcal{L}_{\mathsf{right}}=\mathcal{L}_{1-b}$, where $\mathcal{L}_{b}$ is
the current audit log in $\mathcal{O}^{\mathsf{PIAL}}_{b}$. $\mathcal{A}$
outputs a bit $b^{\prime}\in\\{0,1\\}$. $\mathcal{A}$ wins if $b^{\prime}=b$
and outputs $1$ else 0.

$\Pi$ is said to achieve _audit log indistinguishability_ if
$\mathsf{Pr}[{\texttt{IndGame}}_{\Pi,\mathcal{A}}(\lambda)=1]\leq\frac{1}{2}+\mathsf{negl}(\lambda)$.

##  IV Our Proposed Method

###  IV-A Overview

$\mathsf{Harpocrates}$ supports three data operations – store, share, and
access, wherein each operation is recorded in a distributed audit log (i.e.,
blockchain).

Figure 1: Overview of $\mathsf{Harpocrates}$ scheme.

The high-level workflow (ref. Figure 1) is as follows, given a data $d$ to be
stored on $\mathcal{S}$, $\mathcal{O}$ creates “store” record (1) and a token
for $\mathcal{S}$ containing the message digest of $d$, while sending $d$ off-
chain to $\mathcal{S}$ for storage. The nodes in the blockchain then verify
the validity of the store record (2) before recording it to the audit log.
$\mathcal{S}$ then creates an “ownership” record that certifies the ownership
of $\mathcal{O}$ on the data and provides a token (3) that permits
$\mathcal{O}$ to share her data with $\mathcal{U}$ later. To share the data,
$\mathcal{O}$ creates a “share” record (4) demonstrating her ownership, which
is then verified by the blockchain before being appended to the audit log (5).
The user then accesses this record to obtain a share token
$\mathsf{tk}_{\mathsf{shr}}$ (6) indicating the authorization to access the
shared data stored on $\mathcal{S}$ for a limited period of time. To access
the shared data, the user creates an “access” record (7) demonstrating the
access is authorized by the owner, and an access token for $\mathcal{S}$ to
serve the request. Finally, the record (8) is verified by the blockchain and
included in the audit log. If it is valid, $\mathcal{S}$ sends data (9) to the
requested user $\mathcal{U}$.

To ensure all the data operations are confidential (e.g., hides participant
identity or which data is being shared/accessed), while permitting public
verification, we harness cryptographic commitment, encryption, and zero-
knowledge techniques inspired by Zerocash [21].

###  IV-B Detailed Construction

####  IV-B1 Initialization

The initialization generates public parameters for NP-statements to be
proven/verified in zero-knowledge. We initialize four empty Merkle trees with
roots
($\mathsf{rt}_{\mathsf{str}},\mathsf{rt}_{\mathsf{own}},\mathsf{rt}_{\mathsf{shr}},\mathsf{rt}_{\mathsf{acc}}$),
each containing commitments of the corresponding data operation being
performed. We assume $\mathsf{Harpocrates}$ permits up to $N$ number of
operations per type.

Figure 2 presents the initialization in detail. Since $\mathsf{Harpocrates}$
operates on a distributed audit log, each participant needs an address keypair
for communication and logging their data operations by using
$\mathsf{Register}$.

Since $(\mathsf{pk}_{\mathsf{adr}},\mathsf{sk}_{\mathsf{adr}})$ is never
revealed, each participant is free to re-use a single address for all
operations.

$(\mathcal{L},\mathsf{pp})\leftarrow\mathsf{Init}(1^{\lambda},N)$:
1:$\mathsf{pp}\leftarrow\mathsf{zkp}.\mathcal{G}(1^{\lambda})$ 2:Initialize
four empty Merkle trees containing $N$ nodes with roots
$(\mathsf{rt}_{\mathsf{str}},\mathsf{rt}_{\mathsf{own}},\mathsf{rt}_{\mathsf{shr}},\mathsf{rt}_{\mathsf{acc}})$
3:$\mathcal{L}\leftarrow\\{\mathsf{rt}_{\mathsf{str}},\mathsf{rt}_{\mathsf{own}},\mathsf{rt}_{\mathsf{shr}},\mathsf{rt}_{\mathsf{acc}}\\}$
4:return ($\mathcal{L},\mathsf{pp}$)
$(\mathcal{L},\mathsf{pp})\leftarrow\mathsf{Register}(1^{\lambda},N)$:
1:$\mathsf{sk}_{\mathsf{adr}}\xleftarrow{\$}\\{0,1\\}^{\lambda}$
2:$\mathsf{pk}_{\mathsf{adr}}\leftarrow\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}})$

Figure 2: Initialization.

####  IV-B2 Data Store Protocol

Figure 3 presents our data store protocol. Given data $D$, $\mathcal{O}$ first
creates a commitment formed by the hash of the data $H(D)$, $\mathcal{S}$’s
identity $\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}$ and a random value $\rho$
as
$\mathsf{cm}_{\mathsf{str}}\leftarrow\mathsf{Com}_{r}(H(D)||\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}||\rho,\mathsf{pp})$
(Figure 3, line 3). $\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}$ is needed in
$\mathsf{cm}_{\mathsf{str}}$ to tie store request of $D$ with $\mathcal{S}$.
On the other hand, the random $\rho$ is used to ensure that the request can
only be handled _once_ (see § IV-B3).

$\mathcal{O}$ generates a one-time unique signing key pair
$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})$ to sign their store
request (Figure 3, line 4). This ensures unlinkability between multiple
requests from $\mathcal{O}$. To achieve non-repudiation and prevent
malleability attacks, such keys must be tied with
$\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}}$. Thus, $\mathcal{O}$ creates a MAC
tag $h$ of the signing key $\mathsf{pk}_{\mathsf{sig}}$ under their address
private key $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$ as
$h\leftarrow\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$,
where $h_{\mathsf{sig}}\leftarrow H(\mathsf{pk}_{\mathsf{sig}})$ (Figure 3,
line 5). For creating a store record, $\mathcal{O}$ needs to show that the
components of $(\mathsf{cm}_{\mathsf{str}},h)$ have been formed correctly
under their secrets
$(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r,\rho,v,\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$.

NP-statements for Data Store. Given a store instance
$x=(\mathsf{cm}_{\mathsf{str}},h)$, the witness
$w=(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r,\rho,v,\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$
is a valid witness for $x$ if the following holds –

  * •

The commitment $\mathsf{cm}_{\mathsf{str}}$ is well-formed, i.e.,
$\mathsf{cm}_{\mathsf{str}}=\mathsf{Com}_{r}(H(D)||\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}||\rho,\mathsf{pp})$.

  * •

The address secret key $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$ ties
$h_{\mathsf{sig}}$ to $h$, i.e.,
$h=\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}||h_{\mathsf{sig}})$.

$\mathcal{O}$ then creates a store token
$\mathsf{tk}_{\mathsf{str}}\leftarrow\mathcal{E}.\mathsf{Enc}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r||\rho||v||\mathsf{cm}_{\mathsf{str}})$
containing the openings of the commitment and encrypts it under
$\mathcal{S}$’s public key (Figure 3, line 9). This token will be used by
$\mathcal{S}$ to respond to $\mathcal{O}$’s request appropriately.
$\mathcal{O}$ forms a store record $\mathsf{tx}_{\mathsf{str}}$, which
contains the commitment $\mathsf{cm}_{\mathsf{str}}$, the MAC tag $h$, the
encrypted token $\mathsf{tk}_{\mathsf{str}}$, proof $\pi_{\mathsf{str}}$, and
the signature verification key $\mathsf{pk}_{\mathsf{sig}}$. We store the
token in the record to help with auditing. During an audit, $\mathcal{O}$
simply uses their secret key to decrypt the token and verify record contents.
Finally, $\mathcal{O}$ signs the record with $\mathsf{sk}_{\mathsf{sig}}$, and
broadcasts it to the distributed audit log while sending the data $D$ to
$\mathcal{S}$. $\mathcal{S}$ checks if the decrypted store token
$\mathsf{tk}_{\mathsf{str}}$ is consistent with the commitment and the record
is valid (i.e., valid signature and valid proof). If so, $\mathcal{S}$ stores
$D$ in an appropriate location and creates a record to give the ownership to
$\mathcal{O}$.

$(\mathsf{tk}_{\mathsf{str}},\mathsf{tx}_{\mathsf{str}})\leftarrow\mathsf{Store}(D,\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},\mathsf{pp}$):
1:$v\leftarrow H(D)$ 2:$\rho\xleftarrow{\$}\\{0,1\\}^{\lambda}$
3:$\mathsf{cm}_{\mathsf{str}}\leftarrow\mathsf{Com}_{r}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}||\rho||v,\mathsf{pp})$
4:$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})\leftarrow\Sigma.\mathsf{Gen}(1^{\lambda})$
5:$h_{\mathsf{sig}}\leftarrow H(\mathsf{pk}_{\mathsf{sig}})$,
$h\leftarrow\mathsf{PRF}({\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}}||h_{\mathsf{sig}})$
6:$x=(\mathsf{cm}_{\mathsf{str}},h)$
7:$w=(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r,\rho,v,\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$
8:$\pi_{\mathsf{str}}\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$
9:$\mathsf{tk}_{\mathsf{str}}\leftarrow\mathcal{E}.\mathsf{Enc}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r||\rho||v||\mathsf{cm}_{\mathsf{str}})$
10:$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{str}}||\mathsf{tk}_{\mathsf{str}}$
11:$\sigma\leftarrow\Sigma.\mathsf{Sign}(\mathsf{sk}_{\mathsf{sig}},m)$
12:$\mathsf{tx}_{\mathsf{str}}=(\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{str}},h,\pi_{\mathsf{str}},\mathsf{tk}_{\mathsf{str}})$
13:return $(\mathsf{tk}_{\mathsf{str}},\mathsf{tx}_{\mathsf{str}})$
$(\mathsf{tk}_{\mathsf{own}},\mathsf{tx}_{\mathsf{own}})\leftarrow\mathsf{AssignOwner}(\mathsf{tk}_{\mathsf{str}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pp}$):
14:$\mathsf{sn}\leftarrow\mathsf{PRF}({\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}}||\rho)$
15:$\mathsf{cm}_{\mathsf{own}}\leftarrow\mathsf{Com}_{r^{\prime}}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}}||v^{\prime},\mathsf{pp})$
$\triangleright$ $v^{\prime}=v$ 16:$\mathsf{path}_{\mathsf{str}}=$ Merkle path
from $\mathsf{cm}_{\mathsf{str}}$ to $\mathsf{rt}_{\mathsf{str}}$ (
$\mathsf{rt}_{\mathsf{str}}$ from $\mathcal{L}$)
17:$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})\leftarrow\Sigma.\mathsf{Gen}(1^{\lambda})$
18:$h_{\mathsf{sig}}\leftarrow H(\mathsf{pk}_{\mathsf{sig}})$,
$h\leftarrow\mathsf{PRF}({\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}}||h_{\mathsf{sig}})$
19:$x=(\mathsf{rt}_{\mathsf{str}},\mathsf{sn},\mathsf{cm}_{\mathsf{own}},h)$
20:$w=(\mathsf{path}_{\mathsf{str}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}},\rho,r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r^{\prime},v^{\prime},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$
21:$\pi_{\mathsf{own}}\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$
22:$\mathsf{tk}_{\mathsf{own}}\leftarrow\mathcal{E}.\mathsf{Enc}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},r^{\prime}||v^{\prime}||\mathsf{cm}_{\mathsf{own}})$
23:$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{own}}||\mathsf{tk}_{\mathsf{own}}$
24:$\sigma\leftarrow\Sigma.\mathsf{Sign}(\mathsf{sk}_{\mathsf{sig}},m)$
25:$\mathsf{tx}_{\mathsf{own}}=(\mathsf{rt}_{\mathsf{str}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{sn},\mathsf{cm}_{\mathsf{own}},h,\pi_{\mathsf{own}},\mathsf{tk}_{\mathsf{own}})$
26:return $(\mathsf{tk}_{\mathsf{own}},\mathsf{tx}_{\mathsf{own}})$

Figure 3: Data store and owner assignment protocols.

####  IV-B3 Assign Ownership Protocol

$\mathcal{S}$ performs an assign ownership operation on receiving a
$\mathsf{tk}_{\mathsf{str}}$. $\mathcal{S}$ decrypts
$\mathsf{tk}_{\mathsf{str}}$ to identify which data needs to be assigned. A
serial number $\mathsf{sn}$ is generated using the seed $\rho$ (Figure 3, line
14) in the store record. $\mathsf{sn}$ uses a collision-resistant
$\mathsf{PRF}$ function to ensure that only one assignment is created for the
corresponding store operation. Without this, $\mathcal{S}$ can use a single
$\mathsf{tk}_{\mathsf{str}}$ to maliciously perform assign operations to
multiple data owners. Subsequently, $\mathcal{S}$ generates a commitment
$\mathsf{cm}_{\mathsf{own}}\leftarrow\mathsf{Com}_{r^{\prime}}(\mathsf{pk}_{\mathsf{addr}}^{\mathcal{O}}||v^{\prime},\mathsf{pp})$
(Figure 3, line 15) to represent ownership assignment. To successfully create
an assign record, $\mathcal{S}$ generates a proof of ownership
$\pi_{\mathsf{own}}$ (Figure 3, line 21). Verification of the proof shows that
$\mathcal{S}$ received a store request for the corresponding data. The proof
is generated by the following NP statements –

NP-statements for Data Owner Assignment. Given an assign owner instance
$x=(\mathsf{rt}_{\mathsf{str}},\mathsf{sn},\mathsf{cm}_{\mathsf{own}},h)$, the
witness
$w=(\mathsf{path}_{\mathsf{str}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}},\rho,r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r^{\prime},v^{\prime},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},h_{\mathsf{sig}})$
is a valid witness for $x$ if the following holds –

  * •

Commitment $\mathsf{cm}_{\mathsf{str}}$ appears in the Merkle tree
$\mathsf{rt}_{\mathsf{str}}$, i.e.,
$\mathsf{rt}_{\mathsf{str}}=H(\dots(H(H(\mathsf{cm}_{\mathsf{str}})||\mathsf{path}_{\mathsf{str}}^{d})||\mathsf{path}_{\mathsf{str}}^{d-1})||\dots||\mathsf{path}_{\mathsf{str}}^{1}))$
where $d$ is the height of the Merkle tree and
$\mathsf{path}_{\mathsf{str}}^{i}$ represents the sibling node at height $i$.

  * •

Commitments $\mathsf{cm}_{\mathsf{str}}$ and $\mathsf{cm}_{\mathsf{own}}$ are
well-formed.

  * •

Serial number $\mathsf{sn}$ is computed correctly, i.e.,
$\mathsf{sn}=\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}||\rho)$

  * •

Values committed to $\mathsf{cm}_{\mathsf{str}}$ and
$\mathsf{cm}_{\mathsf{own}}$ are the same.

  * •

The address secret key $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}$ ties
$h_{\mathsf{sig}}$ to $h$.

We utilize Merkle trees to prove set membership i.e, the statement to prove
$\mathsf{cm}_{\mathsf{str}}$ appears in $\mathsf{rt}_{\mathsf{str}}$. The tree
is stored locally by the blockchain nodes and only the root is added to the
record. This is because we want to capture the state of the tree when the
particular record was created. $\mathcal{S}$ then creates an encrypted
ownership token $\mathsf{tk}_{\mathsf{own}}$ (Figure 3, line 22). Finally,
$\mathcal{S}$ signs record $\mathsf{tx}_{\mathsf{own}}$, using a one-time
signing key, and appends it to the distributed audit log. $\mathcal{S}$ also
sends $\mathsf{tk}_{\mathsf{own}}$ to $\mathcal{O}$.

####  IV-B4 Sharing Protocol

Given an ownership token $\mathsf{tk}_{\mathsf{own}}$, a share expiry
timestamp $\mathsf{ts}$, $\mathcal{U}$’s public identity
$\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}}$ and $\mathcal{O}$’s identity
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$ a share operation generates a share
token $\mathsf{tk}_{\mathsf{shr}}$ to $\mathcal{U}$ and a record
$\mathsf{tx}_{\mathsf{shr}}$. A commitment $\mathsf{cm}_{\mathsf{shr}}$ is
created to $\mathcal{U}$, share expiry timestamp and the hash of the data
being shared (Figure 4, line 1). $\mathcal{O}$ generates a valid proof
$\pi_{\mathsf{shr}}$ (Figure 4, line 7) by proving the following NP statements
–

NP-statements for Data Sharing. Given a share instance
$x=(\mathsf{rt}_{\mathsf{own}},\mathsf{cm}_{\mathsf{shr}},h)$, the witness
$w=(\mathsf{path}_{\mathsf{own}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},r^{\prime},v^{\prime},h_{\mathsf{sig}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}})$
is a valid witness for $x$ if the following holds –

  * •

Commitment $\mathsf{cm}_{\mathsf{own}}$ appears in the Merkle tree
$\mathsf{rt}_{\mathsf{own}}$.

  * •

Commitments $\mathsf{cm}_{\mathsf{own}}$ and $\mathsf{cm}_{\mathsf{shr}}$ are
well-formed.

  * •

Values committed to $\mathsf{cm}_{\mathsf{str}}$ and
$\mathsf{cm}_{\mathsf{own}}$ are the same.

  * •

The expiration timestamp committed to $\mathsf{cm}_{\mathsf{shr}}$ is valid,
i.e., $\mathsf{ts}\geq 0$.

  * •

The address secret key $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}$ ties
$h_{\mathsf{sig}}$ to $h$.

Verification of this proof means that $\mathcal{O}$ owns the corresponding
data being shared and is sharing it for a valid period of time. Once the proof
is generated, all the generated data is bundled into a record
$\mathsf{tx}_{\mathsf{shr}}$ and signed using $\mathsf{sk}_{\mathsf{sig}}$
(Figure 4, line 10). The record is added to the distributed audit log for
verification and the token $\mathsf{tk}_{\mathsf{shr}}$ is sent to
$\mathcal{U}$. Note that $\mathcal{O}$ can share their data multiple times
because they can re-use their token $\mathsf{tk}_{\mathsf{own}}$ more than
once.

$(\mathsf{tk}_{\mathsf{shr}},\mathsf{tx}_{\mathsf{shr}})\leftarrow\mathsf{Share}(\mathsf{tk}_{\mathsf{own}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},\mathsf{ts},\mathsf{pp})$:
1:$\mathsf{cm}_{\mathsf{shr}}\leftarrow\mathsf{Com}_{r^{\prime}}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}}||\mathsf{ts}||v^{\prime},\mathsf{pp})$
$\triangleright$ $v^{\prime}=v$ 2:$\mathsf{path}_{\mathsf{own}}\leftarrow$
path from $\mathsf{cm}_{\mathsf{own}}$ to $\mathsf{rt}_{\mathsf{own}}$ (
$\mathsf{rt}_{\mathsf{own}}$ from $\mathcal{L}$)
3:$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})\leftarrow\Sigma.\mathsf{Gen}(1^{\lambda})$
4:$h_{\mathsf{sig}}\leftarrow H(\mathsf{pk}_{\mathsf{sig}})$,
$h\leftarrow\mathsf{PRF}({\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}}}||h_{\mathsf{sig}})$
5:$x=(\mathsf{rt}_{\mathsf{own}},\mathsf{cm}_{\mathsf{shr}},h)$
6:$w=(\mathsf{path}_{\mathsf{own}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O}},r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},r^{\prime},v^{\prime},h_{\mathsf{sig}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{O}})$
7:$\pi_{\mathsf{shr}}\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$
8:$\mathsf{tk}_{\mathsf{shr}}\leftarrow\mathcal{E}.\mathsf{Enc}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},r^{\prime}||v^{\prime}||\mathsf{ts}||\mathsf{cm}_{\mathsf{shr}})$
9:$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{shr}}||\mathsf{tk}_{\mathsf{shr}}$
10:$\sigma\leftarrow\Sigma.\mathsf{Sign}(\mathsf{sk}_{\mathsf{sig}},m)$
11:$\mathsf{tx}_{\mathsf{shr}}=(\mathsf{rt}_{\mathsf{own}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{shr}},h,\pi_{\mathsf{shr}},\mathsf{tk}_{\mathsf{shr}})$
12:return $(\mathsf{tk}_{\mathsf{shr}},\mathsf{tx}_{\mathsf{shr}})$
$(\mathsf{tk}_{\mathsf{acc}},\mathsf{tx}_{\mathsf{acc}})\leftarrow\mathsf{Access}(\mathsf{tk}_{\mathsf{shr}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},\mathsf{pp})$:
13:$\mathsf{cm}_{\mathsf{acc}}\leftarrow\mathsf{Com}_{r^{\prime}}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}||\mathsf{ts}-\mathsf{curr}||v^{\prime},\mathsf{pp})$
$\triangleright$ $v^{\prime}=v$ 14:$\mathsf{path}_{\mathsf{shr}}$ is the path
from $\mathsf{cm}_{\mathsf{shr}}$ to $\mathsf{rt}_{\mathsf{shr}}$ in Merkle
tree ($\mathsf{rt}_{\mathsf{shr}}$ from $\mathcal{L}$)
15:$(\mathsf{pk}_{\mathsf{sig}},\mathsf{sk}_{\mathsf{sig}})\leftarrow\Sigma.\mathsf{Gen}(1^{\lambda})$
16:$h_{\mathsf{sig}}\leftarrow H(\mathsf{pk}_{\mathsf{sig}})$,
$h\leftarrow\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}}||h_{\mathsf{sig}})$
17:$x=(\mathsf{rt}_{\mathsf{shr}},\mathsf{cm}_{\mathsf{acc}},h)$
18:$w=(\mathsf{path}_{\mathsf{shr}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r^{\prime},v^{\prime},\mathsf{ts},\mathsf{curr},h_{\mathsf{sig}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}})$
19:$\pi_{\mathsf{acc}}\leftarrow\mathsf{zkp}.\mathcal{P}(x,w,\mathsf{pp})$
20:$\mathsf{tk}_{\mathsf{acc}}\leftarrow\mathcal{E}.\mathsf{Enc}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r^{\prime}||v^{\prime}||\mathsf{curr}||\mathsf{cm}_{\mathsf{acc}})$
21:$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{acc}}||\mathsf{tk}_{\mathsf{acc}}$
22:$\sigma\leftarrow\Sigma.\mathsf{Sign}(\mathsf{sk}_{\mathsf{sig}},m)$
23:$\mathsf{tx}_{\mathsf{acc}}=(\mathsf{rt}_{\mathsf{shr}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{acc}},\mathsf{cm}_{\mathsf{shr}},\mathsf{ts},h,\pi_{\mathsf{acc}},\mathsf{tk}_{\mathsf{acc}})$
24:return $(\mathsf{tk}_{\mathsf{acc}},\mathsf{tx}_{\mathsf{acc}})$

Figure 4: Data share and access protocols.

####  IV-B5 Access Protocol

$\mathcal{U}$ uses $\mathsf{tk}_{\mathsf{shr}}$ obtained from $\mathcal{O}$ to
perform an access operation. A commitment representing an access
$\mathsf{cm}_{\mathsf{acc}}\leftarrow\mathsf{Com}_{r^{\prime}}(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}}||v^{\prime},\mathsf{pp})$
is generated using $\mathcal{S}$’s public key and the hash of the data that
needs to be accessed (Figure 4, line 13). $\mathcal{U}$ then creates a proof
$\pi_{\mathsf{acc}}$ by proving the following –

NP-statements for Data Access. Given an access instance
$x=(\mathsf{rt}_{\mathsf{shr}},\mathsf{cm}_{\mathsf{acc}},h)$, the witness
$w=(\mathsf{path}_{\mathsf{shr}},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{U}},r,v,\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}},r^{\prime},v^{\prime},\mathsf{ts},\mathsf{curr},h_{\mathsf{sig}},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}})$
is a valid witness for $x$ if the following holds –

  * •

Commitment $\mathsf{cm}_{\mathsf{shr}}$ appears in Merkle tree
$\mathsf{rt}_{\mathsf{shr}}$.

  * •

Commitments $\mathsf{cm}_{\mathsf{shr}}$ and $\mathsf{cm}_{\mathsf{acc}}$ are
well-formed.

  * •

Values committed to $\mathsf{cm}_{\mathsf{shr}}$ and
$\mathsf{cm}_{\mathsf{acc}}$ are the same.

  * •

The timestamp committed to $\mathsf{cm}_{\mathsf{acc}}$ is not expired, i.e.,
$0<\mathsf{curr}<\mathsf{ts}$ where $\mathsf{curr}$ is the current timestamp.

  * •

The address secret key $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{U}}$ ties
$h_{\mathsf{sig}}$ to $h$.

A valid proof for the above statements can only be generated if $\mathcal{U}$
was given the share token by $\mathcal{O}$ and the share expiry timestamp is
not expired. We note that $\mathcal{U}$ can access the data as many times as
they wish within the given time period after which they will not be able to
generate a valid $\pi_{\mathsf{acc}}$. Finally, $\mathcal{U}$ creates an
access record (Figure 4, line 23) and appends it to the distributed audit log.
$\mathcal{U}$ also sends the access token to the $\mathcal{S}$ to obtain the
data shared with them. $\mathcal{S}$ sends the data only if the record (i.e
$\mathsf{tx}_{\mathsf{acc}}$) corresponding to $\mathsf{tk}_{\mathsf{acc}}$
has been validated by the distributed audit log.

####  IV-B6 Record Verification

The $\mathsf{VerifyRecord}$ protocol (see Figure 5) runs on the distributed
audit log nodes to verify the zero-knowledge proof and the signature included
in the record. If either of the verification procedures fails, the record is
discarded. If the record verification succeeds, the audit log nodes update
their local copies of the corresponding commitment tree and appends the record
to the audit log.

$\\{0,1\\}\leftarrow\mathsf{VerifyRecord}(\mathsf{tx},\mathcal{L},\mathsf{pp})$:
1:if
$\mathsf{tx}=(\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{str}},h,\pi_{\mathsf{str}},\mathsf{tk}_{\mathsf{str}})$
$\triangleright$ $\mathsf{tx}_{\mathsf{str}}$ 2:
$x=(\mathsf{cm}_{\mathsf{str}},h)$ 3:
$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{str}}||\mathsf{tk}_{\mathsf{str}}$ 4:else
if
$\mathsf{tx}=(\mathsf{rt}_{\mathsf{own}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{sn},\mathsf{cm}_{\mathsf{str}},h,\pi_{\mathsf{own}},\mathsf{tk}_{\mathsf{own}})$
$\triangleright$ $\mathsf{tx}_{\mathsf{own}}$ 5: If
$\mathsf{sn}\in\mathcal{L}$, abort.  6:
$x=(\mathsf{rt}_{\mathsf{str}},\mathsf{sn},\mathsf{cm}_{\mathsf{own}},h)$,  7:
$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{own}}||\mathsf{tk}_{\mathsf{own}}$ 8:else
if
$\mathsf{tx}=(\mathsf{rt}_{\mathsf{shr}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{shr}},h,\pi_{\mathsf{shr}},\mathsf{tk}_{\mathsf{shr}})$
$\triangleright$ $\mathsf{tx}_{\mathsf{shr}}$ 9:
$x=(\mathsf{rt}_{\mathsf{own}},\mathsf{cm}_{\mathsf{shr}},h)$ 10:
$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{shr}}||\mathsf{tk}_{\mathsf{shr}}$
11:else if
$\mathsf{tx}=(\mathsf{rt}_{\mathsf{acc}},\mathsf{pk}_{\mathsf{sig}},\sigma,\mathsf{cm}_{\mathsf{acc}},h,\pi_{\mathsf{acc}},\mathsf{tk}_{\mathsf{acc}})$
$\triangleright$ $\mathsf{tx}_{\mathsf{acc}}$ 12:
$x=(\mathsf{rt}_{\mathsf{shr}},\mathsf{cm}_{\mathsf{acc}},h)$ 13:
$m=x||h_{\mathsf{sig}}||\pi_{\mathsf{acc}}||\mathsf{tk}_{\mathsf{acc}}$
14:return
$\mathsf{zkp}.\mathcal{V}(x,\pi,\mathsf{pp})\land\Sigma.\mathsf{Verify}({\mathsf{pk}_{\mathsf{sig}}},m,\sigma)$

Figure 5: Verification protocol.

##  V Security Analysis

###### Theorem 1.

$\mathsf{Harpocrates}$ satisfies record non-malleability by Definition 1.

###### Proof (sketch).

Let $Q_{\mathsf{Register}}=\\{1^{\lambda},1^{\lambda},\dotsc\\}$ be the
queries by $\mathcal{A}$ to $\mathsf{Register}$ and
$R_{\mathsf{Register}}=\\{(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S},1},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S},1}),(\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S},2},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S},2}),\dotsc\\}$
be $\mathcal{C}$’s response.

Without loss of generality, let
$Q_{\mathsf{AssignOwner}}=\\{(\mathsf{tk}_{\mathsf{str}}^{1},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S},1},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O},1},\mathsf{pp}),(\mathsf{tk}_{\mathsf{str}}^{2},\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S},2},\mathsf{pk}_{\mathsf{adr}}^{\mathcal{O},2},\mathsf{pp}),,\dotsc\\}$
be the queries created by $\mathcal{A}$ and
$R_{\mathsf{AssignOwner}}=\\{(\mathsf{tk}_{\mathsf{own}}^{1},\mathsf{tx}_{\mathsf{own}}^{1}),(\mathsf{tk}_{\mathsf{own}}^{2},\mathsf{tx}_{\mathsf{own}}^{2}),\dotsc\\}$
be the response by $\mathcal{C}$. $\mathcal{A}$ wins the experiment NMGame
when it outputs a record $\mathsf{tx}_{\mathsf{own}}^{*}$ such that (i)
$m^{*}\neq m$, where $m$ is the message in some $\mathsf{tx}_{\mathsf{own}}\in
R_{\mathsf{AssignOwner}}$; (ii)
$\mathsf{VerifyLog}(\mathsf{tx}_{\mathsf{own}}^{*},\mathcal{L}^{\prime},\mathsf{pp})=1$,
where $\mathcal{L}^{\prime}$ is the state of the audit log preceding
$\mathsf{tx}_{\mathsf{own}}$; (iii) $\mathsf{sn}^{*}=\mathsf{sn}$ iff
$\mathsf{tx}^{*}$ is an ownership record.

Assume that $\mathcal{A}$ wins by creating a record
$\mathsf{tx}_{\mathsf{own}}^{*}=(\mathsf{rt}_{\mathsf{str}}^{*},\mathsf{pk}_{\mathsf{sig}}^{*},\sigma^{*},\mathsf{sn}^{*},\mathsf{cm}_{\mathsf{own}}^{*},h^{*},\pi_{\mathsf{own}}^{*},\mathsf{tk}_{\mathsf{own}}^{*})$
with proof instance
$x^{*}=(\mathsf{rt}_{\mathsf{str}}^{*},\mathsf{sn}^{*},\mathsf{cm}_{\mathsf{own}}^{*},h^{*})$
and
$m^{*}=x^{*}||h_{\mathsf{sig}}^{*}||\pi_{\mathsf{own}}^{*}||\mathsf{tk}_{\mathsf{own}}^{*}$.
We consider the following events.

$E_{1}:$ $\mathcal{A}$ wins, and there exists $\mathsf{pk}_{\mathsf{sig}}\in
R_{\mathsf{AssignOwner}}$ such that
$\mathsf{pk}_{\mathsf{sig}}^{*}=\mathsf{pk}_{\mathsf{sig}}$. To win,
$\mathcal{A}$ produces $\sigma^{*}$ such that
$\Sigma.\mathsf{Verify}(\mathsf{pk}_{\mathsf{sig}}^{*},m^{*},\sigma^{*})=1$,
$m^{*}\neq m$ and $\mathsf{pk}_{\mathsf{sig}}^{*}=\mathsf{pk}_{\mathsf{sig}}$.
However, due to the SUF-CMA property of the signature scheme [22], this
happens with negligible probability.

$E_{2}:$ $\mathcal{A}$ wins, $E_{1}$ does not occur, and there exists
$\mathsf{pk}_{\mathsf{sig}}\in R_{\mathsf{AssignOwner}}$ such that
$h^{*}_{\mathsf{sig}}=h_{\mathsf{sig}}$. When $\mathcal{A}$ wins, it crafts a
$h^{*}_{\mathsf{sig}}=h_{\mathsf{sig}}$ when
$\mathsf{pk}_{\mathsf{sig}}^{*}\neq\mathsf{pk}_{\mathsf{sig}}$. However, the
hash function [23] is collision-resistant, a contradiction.

$E_{3}:$ $\mathcal{A}$ wins, $(E_{1},E_{2})$ do not occur and
$h^{*}=\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}||h^{*}_{\mathsf{sig}})$
for some $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}\in
R_{\mathsf{Register}}$. Due to the one-wayness property of $\mathsf{PRF}$
(used to generate $\mathsf{pk}_{\mathsf{adr}}^{\mathcal{S}^{*}}$),
$\mathcal{A}$ will not be able to deduce
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}$ and generates $h^{*}$ with a
random key. However, due to indistinguishability property of $\mathsf{PRF}$
(used to generate $h^{*}$), $\mathcal{A}$ wins negligbly.

$E_{4}:$ $\mathcal{A}$ wins, $(E_{1},E_{2},E_{3})$ do not occur,
$\mathsf{tx}^{*}$ is an ownership record and
$h^{*}\neq\mathsf{PRF}(\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}||h^{*}_{\mathsf{sig}})$
for all $\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}\in
R_{\mathsf{Register}}$. If $\mathcal{A}$ wins, it outputs a modified record
such that $\mathsf{sn}^{*}=\mathsf{sn}$. However, since in $E_{4}$
$\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}^{*}}\neq\mathsf{sk}_{\mathsf{adr}}^{\mathcal{S}}$,
it means that to generate $\mathsf{sn}^{*}$, $\mathcal{A}$ found a collision
in the $\mathsf{PRF}$ needed to generate $\mathsf{sn}$ which occurs with
negligible probability due to the collision-resistant property of the
$\mathsf{PRF}$ function used to generate $\mathsf{sn}$. ∎

###### Theorem 2.

$\mathsf{Harpocrates}$ satisfies audit log indistinguishability by Definition
2

###### Proof (sketch).

$\mathcal{C}$ creates a simulation $\texttt{IndGame}_{S}$ that can answer the
queries ($Q,Q^{\prime}$) independent to the selected bit $b$ as follows.
$\mathcal{C}$ modifies the commitment
$\mathsf{cm}_{\mathsf{str}}^{*}\leftarrow\mathsf{Com}_{r}(k,\mathsf{pp})$ by
using random inputs $k,r$. To answer $\mathsf{AssignOwner}$ queries,
$\mathcal{C}$ modifies $\mathsf{AssignOwner}$ to create $\mathsf{sn}$ and $h$
randomly. $\mathsf{cm}_{\mathsf{own}}$ is computed like in $\mathsf{Store}$.
$\mathsf{tk}_{\mathsf{own}}^{*}\leftarrow\mathcal{E}.\mathsf{Enc}(e,p)$ is
generated using a random plaintext $p$ and key $e$. Proof
$\pi_{\mathsf{own}}^{*}\leftarrow S(x,\mathsf{pp})$ is computed using a
simulator. To answer $\mathsf{Share}$ or $\mathsf{Access}$ queries,
$\mathcal{C}$ computes $h$, commitments
($\mathsf{cm}_{\mathsf{shr}}$/$\mathsf{cm}_{\mathsf{acc}}$), tokens
($\mathsf{tk}_{\mathsf{shr}}$/$\mathsf{tk}_{\mathsf{acc}}$), proofs
($\pi_{\mathsf{shr}}$/$\pi_{\mathsf{acc}}$) by following modifications in
$\mathsf{AssignOwner}$.

We prove this by constructing a sequence of hybrid games and show that they
are indistinguishable as follows. Let $G_{0}$ be the original protocol
$\texttt{IndGame}_{\Pi}$. We define $G_{1}$ as similar to $G_{0}$, except that
$\mathcal{C}$ modifies the commitment in the response to use a
$\mathsf{cm}^{*}\leftarrow\mathsf{Com}_{r}(k,\mathsf{pp})$ by using random
inputs $k,r$. We have that $G_{1}\stackrel{{\scriptstyle c}}{{\approx}}G_{0}$
due to the hiding property of the commitment scheme.We define $G_{2}$ as
similar to $G_{1}$, except that the token in the response is replaced with
$\mathsf{tk}^{*}\leftarrow\mathcal{E}.\mathsf{Enc}(e,p)$ where $e$ is a random
public key and $p$ is a random plaintext. We argue that
$G_{2}\stackrel{{\scriptstyle c}}{{\approx}}G_{1}$ due to the IND-CCA and IK-
CCA properties of the encryption scheme [24]. We define $G_{3}$ as similar to
$G_{2}$, except that all $\mathsf{PRF}$ generated values (i.e,
$h,\mathsf{sn}$) in the response are replaced with values generated using a
random function. We say that $G_{3}\stackrel{{\scriptstyle
c}}{{\approx}}G_{2}$ due to the indistinguishability between $\mathsf{PRF}$
and random number function. Finally, we define $G_{4}$ as similar to $G_{3}$,
except that the zero-knowledge proof in the response is replaced by a
simulated proof $\pi^{*}\leftarrow S(x,\mathsf{pp})$. We have that
$G_{4}\stackrel{{\scriptstyle c}}{{\approx}}G_{3}$ due to the zero-knowledge
property of the proof system.

We can see that $G_{4}$ is the simulation $\texttt{IndGame}_{S}$. Therefore,
$\texttt{IndGame}_{\Pi}=G_{0}\stackrel{{\scriptstyle
c}}{{\approx}}G_{1}\stackrel{{\scriptstyle
c}}{{\approx}}G_{2}\stackrel{{\scriptstyle
c}}{{\approx}}G_{3}\stackrel{{\scriptstyle
c}}{{\approx}}G_{4}=\texttt{IndGame}_{S}$. Since $\texttt{IndGame}_{S}$ can
simulate the response to $Q$ and $Q^{\prime}$ independent of bit $b$,
$\mathcal{A}$ can win $\texttt{IndGame}_{\Pi}$ game with negligible
probability. ∎

##  VI Implementation

We implemented $\mathsf{Harpocrates}$ in Rust with 3,100 lines of code. We
used Hyperledger Fabric [25] to set up the audit log as the distributed
ledger. Each data operation was implemented as Hyperledger chaincode
(equivalent to smart contracts) in Go. For the signature scheme, we
implemented Schnorr signature scheme [22]. For the asymmetric encryption, we
implemented ECIES with AES-GCM as the underlying symmetric encryption scheme
[24]. For the commitment scheme, we used Pedersen commitment [26]. We
implemented the Merkle trees with Poseidon hash function as it can efficiently
compute hashes of two elements at once [27]. We implemented MiMC as the
primary hash function as well as PRF due to its low multiplicative complexity
[23]. Finally, our implementation made use of Bulletproofs [20] as the back-
end zero-knowledge proof due to its small proof size and transparent setup.

We prove/verify statements in zero-knowledge for each data operation as
follows –

Store. We implemented a circuit with one Pedersen commitment opening gadget
$\mathsf{PedG}$ (based on [28]) to show knowledge of openings of a commitment
and one hash pre-image gadget $\mathsf{HshG}$ (based on [23]) to show
knowledge of a pre-image of a MiMC hash.

Assign. We implemented a circuit with one $\mathsf{MemG}$, two
$\mathsf{PedG}$, and two $\mathsf{HshG}$. Here, $\mathsf{MemG}$ is a Merkle
tree based proof of membership gadget.

Share. We implemented a circuit with one range gadget $\mathsf{RgeG}$, one
$\mathsf{HshG}$, one $\mathsf{MemG}$, and two $\mathsf{PedG}$ gadgets.
$\mathsf{RgeG}$ (based on [20]) is used to show knowledge that a value
($\mathsf{ts}$ in our case) is within a given range.

Access. We implemented a circuit with $\mathsf{RgeG}$, one $\mathsf{HshG}$,
one $\mathsf{MemG}$, and two $\mathsf{PedG}$ gadgets.

##  VII Experimental Evaluation

1020304050$0$$10$$20$$30$$n$Time (sec)StoreAssignShareAccess (a) $k=25$

1020304050$0$$10$$20$$30$$40$$n$Time (sec) (b) $k=50$

1020304050$0$$20$$40$$60$$n$Time (sec) (c) $k=75$

Figure 6: Verification latency.

1020304050$0.8$$1$$1.2$$1.4$$1.6$$1.8$$2$$2.2$$2.4$$2.6$$2.8$$3$$\cdot
10^{2}$$n$Memory (MB)StoreAssignShareAccess (a) $k=25$

1020304050$1$$2$$3$$\cdot 10^{2}$$n$Memory (MB) (b) $k=50$

1020304050$1$$2$$3$$\cdot 10^{2}$$n$Memory (MB) (c) $k=75$

Figure 7: Memory usage distribution across blockchain nodes.

###  VII-A Configuration

Hardware. We used 50 AWS EC2 t3.medium instances to deploy a Hyperledger
Fabric blockchain network. Each instance had 4GB vRAM with a 2-core 3.1 GHz
CPU (Intel Xeon) and network bandwidth of 4.3 Gbps. Nodes were deployed in the
us-east-1 region.

Parameter Setting. We used standard parameters to achieve 128-bit security. We
used standard Poseidon Hash parameters for the Merkle tree including width
$t=6$, full rounds $R_{F}=8$ and partial rounds $R_{p}=130$ [27]. We used MiMC
hash function with rate $512$ and capacity $513$. We implemented the Schnorr
signature scheme to produce a 512-bit signature. For the ECIES encryption
scheme, our implementation used a 256-bit public and secret key. We used
Ed25519 curve of order $2^{255}-19$ for zero-knowledge proofs based on
Bulletproofs, ECIES, and Schnorr. For Hyperledger Fabric, we set block size as
10 and the number of transaction confirmations as 1.

###  VII-B Micro-Benchmark

Table II presents the processing overhead in terms of circuit complexity,
processing latency, and memory usage as well as the bandwidth overhead of each
operation.

TABLE II: Performance of each data operation.

Data | Circuit | Delay (s) | Mem (MB) | B/W
---|---|---|---|---
Op. | $\lvert C\rvert$ | $\lvert M\rvert$ | $\mathsf{zkp}.\mathcal{P}$ | $\mathsf{zkp}.\mathcal{V}$ | $\mathsf{zkp}.\mathcal{P}$ | $\mathsf{zkp}.\mathcal{V}$ | (KB)
Store | 2,389 | 644 | 1.8 | 1.5 | 40.1 | 39.3 | 1.0
Assign | 87,315 | 37,640 | 23.2 | 8.6 | 165.6 | 94.7 | 1.4
Share | 86,067 | 37,014 | 23.0 | 8.5 | 159.3 | 89.8 | 1.4
Access | 86,068 | 37,014 | 23.1 | 8.5 | 159.4 | 89.8 | 1.4

  * •

$\bullet$ $\lvert C\rvert$: # constraints, $\lvert M\rvert$: # multiplication
gates.

Circuit Complexity. Recording store operations incur the least circuit
complexity, compared with other operations such as assign, share, and access.
This is because performing a store operation only invokes one $\mathsf{PedG}$
and one $\mathsf{HshG}$, while other operations invokes $\mathsf{MemG}$ along
with other gadgets. The constraint system of $\mathsf{MemG}$ is complicated
and requires proving and verifying (in zero-knowledge) $d=64$ Poseidon hash
pre-images, each of which incurs $3\times t\times R_{F}+3\times R_{p}=534$
number of multiplication constraints [27]. Assign operation incurs a little
higher circuit complexity than share and access because of an extra
$\mathsf{HshG}$ used for $\mathsf{sn}$. Share has one constraint over access
as it requires an additional constraint to calculate difference between the
current timestamp, $\mathsf{curr}$ and the share expiry timestamp,
$\mathsf{ts}$ (see § IV-B5).

Processing Latency. The processing latency depends on circuit complexity,
especially the number of multiplication gates ($|M|$). Store operation incurs
a small latency compared with other operations because it does not require
checking set membership, which attributes to large circuit complexity. We
include the Common Reference String (CRS) loading delay that is needed for the
backend zero-knowledge proof (i.e., Bulletproofs), which takes around $1.5$
seconds (s) in total. Without CRS, the proving and verification time for store
operation is 0.35 s and 85 milliseconds (ms), respectively, which are about 60
times lesser than assign, share, and access. This matches their difference in
$\lvert M\rvert$.

Memory Usage. The memory usage also depends on the circuit complexity to prove
each data operation. The CRS component takes approximately $32$ MB. Proving
incurs more memory usage than verification, due to the space needed to store
the witness.

Bandwidth. Since Bulletproof incurs a polylogarithmic proof size, the
bandwidth overhead for each data operation is small. The proof size produced
by Bulletproofs is $2\lceil\log_{2}(|M|)\rceil+13$ group elements. For store,
$|M|=644$ so its proof contains $2\lceil\log_{2}(644)\rceil+13=33$ group
elements, which results in a total of $32\cdot 33=1,056$ bytes (B). For
assign, share, and access operations, $|M|\approx 37,000$ and, their proof
size is 1,440 B.

###  VII-C Macro-Benchmark

We benchmark the performance of $\mathsf{Harpocrates}$ using Hyperledger
Fabric. We vary the number of concurrent records $k$ and blockchain nodes $n$
to evaluate the scalability of our proposed technique.

Overall latency. Figure 6 presents the latency to verify a data operation with
varying $k$ and $n$. When $k=25$ and $n=10$, it takes around 17 s to verify a
record of assign, share, and access operations (see 5(a)). We see that the
verification delay reduces when increasing $n$. In particular, it reduces to
around 11 s for $n=20$, and 9 s for $n=30$, after which, we observe no further
improvement. This is because, when $n=30$, every node only verifies one
operation at a time. Notice that verifying an assign record should only take
8.5 s (from micro-benchmark), rather than 9 s as shown in Figure 6 (when
$n\geq k$). This is due to the delay caused by Hyperledger Fabric
implementation of about 0.5 s. The same trend is observed for store operation,
where the latency is 4.13 s when $n=10$ and reduces to 2.51 s and 2 s when
$n=20$ and $n=30$, respectively.

5(b) and 5(c) shows the impact on verification latency when increasing $k$. We
observe that when doubling $k$, the latency does not doubly increase but
increases around 2 - 1.5 times. This is due to the implementation of
Hyperledger Fabric, which attempts to exploit all the CPU resources (2 cores
in our setting) to verify all records submitted to it. The speedup is not
observed when $n=10$ because the load per node is 5 (when $k=50$) or 7.5 (when
$k=75$). The 5/7.5 verifications happen at the same time across 2 CPU cores.
This requires the CPUs to constantly switch between tasks which incurs a large
delay.

Figure 8 presents end-to-end processing latency when $n=30$ with varying $k$.
It captures proving time (including overhead to load CRS), record creation
time, verification time, and consensus delays.

1255075100$0$$15$$30$$45$$60$# concurrent data operations ($k$)Time
(sec)StoreAssignShareAccess Figure 8: End-to-end latency with $n=30$
blockchain nodes.

Memory Usage. Figure 7 presents distribution of memory used by nodes with
varying $k$ and $n$. In 6(a), when $k=25$ and $n=10$, the median memory used
to verify a store/assign/share/access operation is about 171/279/271/271 MB,
respectively. Similar to latency, we see that the memory used by nodes to
verify records of data operations reduces when increasing $n$. For example,
the inter-quartile range of memory usage when $n=20$ and $k=25$ for a store
operation is 130-151 MB with a median of 132 MB. This is because the majority
of the nodes verify one store operation and some handle two as seen by the
maximum value of 172 MB. When $n=50$ and $k=25$, half the nodes verify one
store operation and the other half are idle, therefore, we observe an inter-
quartile range of 92-131 MB with a median of 110 MB. The lower quartile of 92
MB shows the memory needed to run Hyperledger Fabric. The upper quartile of
131 MB shows the memory needed to verify one store operation.

As seen in 6(b) and 6(c), increasing $k$ increases the memory usage by the
blockchain nodes as observed by the tighter inter-quartile range. However, the
maximum memory used, regardless of $k$, is about 174/282/272/271 MB for
store/assign/share/access operations . This is equivalent to verifying two
operations at a time since every node only has two CPUs.

###  VII-D Comparison with prior works

TABLE III: Comparison of $\mathsf{Harpocrates}$ over prior works.

Scheme | Data Operation Latency (s) | Public Verifiability
---|---|---
Store | Share | Access
Ghostor [18] | 5.4 | 8.5 | 7.0 | ✗
Calypso [19] | 15.3 | 15.3 | 18.1 | ✗
$\mathsf{Harpocrates}$ | 36.3* | 32.4 | 31.1 | ✓

  * •

∗This combines the cost of “store” and “assign” operations.

We conservatively compare the performance of our scheme with some prior works
related to our setting including Ghostor [18] and Calypso [19]. Table III
presents the end-to-end delays incurred to perform one data operation of our
scheme and prior works. Ghostor incurs the least delay of an average of 7
seconds mostly due to the asymmetric encryption and Tor anonymous
communication. Calypso incurs the second highest delay of around 16 seconds
for each operation mainly as it relies on verifiable secret sharing. A data
operation in $\mathsf{Harpocrates}~{}$ takes about 33 seconds mostly due to
zero-knowledge proof of membership, which accounts for about 80% of the delay.
However, despite being slower than prior works, we note that our scheme
permits public verifiability for data operations thereby, making the audit
process transparent. In prior works, the log must be validated by a trusted
auditor and requires all the data operators to participate in the audit
process.

##  VIII Related Work

Centralized Audit Log. Traditional data sharing/access schemes record data
operations directly on the server that stores the data [29, 30]. Such records
are needed for audit purposes, where a third-party auditor determines whether
any unauthorized accesses have been made in the system [1, 31]. However, with
the introduction of regulations like HIPAA a secure logging mechanism [10] is
needed. Secure logging primitives [11, 32] rely on a trusted author whose
signature is considered the root of trust for integrity or requires analyzing
the entirety of the audit log to detect tampering due to the privacy-
preserving nature of the records. Alternatively, prior works [33, 12] use
secure hardware to achieve immutable and privacy-preserving records. Since the
audit log is maintained by the centralized server, it is vulnerable to a
single point of failure, where the corrupted server can compromise the
confidentiality and integrity of the audit log.

Decentralized Audit Log. Several works have proposed a decentralized audit log
to address the single point of failure vulnerabilities. These schemes were
designed for medical data [3, 13], supply chain [15, 16], and financial
applications [34, 35]. Some schemes permit tamper resistance and access
control to data objects being logged [36, 37]. However, these approaches do
not hide the user identities (e.g., sender/receiver). Several works attempted
to achieve either full anonymity [18] or partially anonymous [19]. There are
several schemes that permit the validity of audit log to be verified publicly
[17] or privately [18, 19]. Private validity verifiability requires every user
in the system to participate and prove the integrity of their records during
the audit phase.

##  IX Conclusion

We proposed $\mathsf{Harpocrates}$, a privacy-preserving and immutable audit
log scheme. $\mathsf{Harpocrates}$ achieved immutability and resistance to
single point of failure by leveraging blockchain, and achieved public
verifiability of record validity using zero-knowledge proofs. We fully
implemented $\mathsf{Harpocrates}$ and evaluated its performance by using
Hyperledger Fabric and Amazon EC2.

## Acknowledgement

This research is supported by BitShares and Robert Bosch (as an unrestricted
gift), and the Commonwealth Cyber Initiative (CCI), an investment in the
advancement of cyber R&D, innovation, and workforce development. For more
information about CCI, visit www.cyberinitiative.org.

## References

  * [1] J. Yuan and S. Yu, “Public integrity auditing for dynamic data sharing with multiuser modification,” _IEEE TIFS_ , vol. 10, no. 8, 2015.
  * [2] X. Liu, Z. Wang, C. Jin, F. Li, and G. Li, “A blockchain-based medical data sharing and protection scheme,” _IEEE Access_ , vol. 7, 2019.
  * [3] H. Guo, W. Li, M. Nejad, and C.-C. Shen, “Access control for electronic health records with hybrid blockchain-edge architecture,” in _IEEE Blockchain_ , 2019.
  * [4] W. F. Lau, D. Y. W. Liu, and M. H. Au, “Blockchain-based supply chain system for traceability, regulation and anti-counterfeiting,” in _IEEE Blockchain_ , 2021.
  * [5] A. Shahid _et al._ , “Blockchain-based agri-food supply chain: A complete solution,” _IEEE Access_ , vol. 8, 2020.
  * [6] K. Toyoda, P. T. Mathiopoulos, I. Sasase, and T. Ohtsuki, “A novel blockchain-based product ownership management system (poms) for anti-counterfeits in the post supply chain,” _IEEE Access_ , vol. 5, 2017\.
  * [7] Q. Song, Y. Chen, Y. Zhong, K. Lan, S. Fong, and R. Tang, “A supply-chain system framework based on internet of things using blockchain technology,” _ACM Trans. Internet Technol._ , vol. 21, no. 1, jan 2021.
  * [8] R. Zhou, M. Hamdaqa, H. Cai, and A. Hamou-Lhadj, “Mobilogleak: A preliminary study on data leakage caused by poor logging practices,” in _2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 2020, pp. 577–581.
  * [9] A. Rusbridger, “The Snowden leaks and the public,” in _The New York Review of Books—NYR Daily, 2013_.
  * [10] United States Department of Health, “The Health Insurance Portability and Accountability Act of 1996.”
  * [11] I. Ray, K. Belyaev, M. Strizhov, D. Mulamba, and M. Rajaram, “Secure logging as a service—delegating record management to the cloud,” _IEEE Systems Journal_ , 2013.
  * [12] D. Ma and G. Tsudik, “A new approach to secure logging,” _ACM Trans. Storage_ , vol. 5, no. 1, mar 2009.
  * [13] Q. Xia, E. B. Sifah, K. O. Asamoah, J. Gao, X. Du, and M. Guizani, “Medshare: Trust-less medical data sharing among cloud service providers via blockchain,” _IEEE Access_ , vol. 5, 2017.
  * [14] J. Liu, X. Li, L. Ye, H. Zhang, X. Du, and M. Guizani, “Bpds: A blockchain based privacy-preserving data sharing for electronic medical records,” in _IEEE GLOBECOM_ , 2018.
  * [15] F. M. Benčić, P. Skočir, and I. P. Žarko, “Dl-tags: Dlt and smart tags for decentralized, privacy-preserving, and verifiable supply chain management,” _IEEE Access_ , 2019.
  * [16] M. E. Maouchi, O. Ersoy, and Z. Erkin, “Decouples: A decentralized, unlinkable and privacy-preserving traceability system for the supply chain,” in _ACM SAC_ , 2019.
  * [17] H. Shafagh, L. Burkhalter, S. Ratnasamy, and A. Hithnawi, “Droplet: Decentralized authorization and access control for encrypted data streams,” in _USENIX Security_ , Aug. 2020.
  * [18] Y. Hu, S. Kumar, and R. A. Popa, “Ghostor: Toward a secure Data-Sharing system from decentralized trust,” in _USENIX NSDI_ , feb 2020.
  * [19] E. Kokoris-Kogias, E. C. Alp, L. Gasser, P. Jovanovic, E. Syta, and B. Ford, “Calypso: Private data management for decentralized ledgers,” _Proc. VLDB Endow._ , vol. 14, no. 4, Dec. 2020.
  * [20] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in _IEEE S &P_, 2018.
  * [21] E. Ben Sasson _et al._ , “Zerocash: Decentralized anonymous payments from bitcoin,” in _IEEE S &P_, 2014.
  * [22] C. P. Schnorr, “Efficient identification and signatures for smart cards,” in _Springer CRYPTO_ , 1990.
  * [23] M. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen, “Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity,” in _IACR ASIACRYPT_ , 2016.
  * [24] M. B. Michel Abdalla and P. Rogaway, “Dhaes: An encryption scheme based on the diffie-hellman problem,” IACR Cryptology ePrint Archive, Report 1999/007, 1999\.
  * [25] E. Androulaki _et al._ , “Hyperledger fabric: A distributed operating system for permissioned blockchains,” in _ACM EuroSys_ , 2018.
  * [26] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” in _CRYPTO_ , 1992.
  * [27] L. Grassi, D. Khovratovich, C. Rechberger, A. Roy, and M. Schofnegger, “Poseidon: A new hash function for Zero-Knowledge proof systems,” in _USENIX Security_ , Aug. 2021.
  * [28] D. Boneh, B. Bünz, and B. Fisch, “Batching techniques for accumulators with applications to iops and stateless blockchains,” in _Springer CRYPTO_ , 2019.
  * [29] S. Sundareswaran, A. Squicciarini, and D. Lin, “Ensuring distributed accountability for data sharing in the cloud,” _IEEE TDSC_ , vol. 9, no. 4, 2012.
  * [30] Z. Yang, W. Wang, and Y. Huang, “Ensuring reliable logging for data accountability in untrusted cloud storage,” in _IEEE ICC_ , 2017.
  * [31] H. Tian _et al._ , “Public audit for operation behavior logs with error locating in cloud storage,” _Soft Computing_ , vol. 23, no. 11, Jun 2019\.
  * [32] Y. Shen, T. Lam, J.-C. Liu, and W. Zhao, “On the confidential auditing of distributed computing systems,” in _IEEE ICDCS_ , 2004, pp. 600–607.
  * [33] V. Karande, E. Bauman, Z. Lin, and L. Khan, “Sgx-record: Securing system logs with sgx,” in _ACM Asia CCS_ , 2017.
  * [34] H. Al-Shaibani, N. Lasla, and M. Abdallah, “Consortium blockchain-based decentralized stock exchange platform,” _IEEE Access_ , vol. 8, 2020.
  * [35] A. Biryukov, D. Khovratovich, and S. Tikhomirov, “Findel: Secure derivative contracts for ethereum,” in _Springer FC_ , 2017.
  * [36] D. Di Francesco Maesa, P. Mori, and L. Ricci, “A blockchain based approach for the definition of auditable access control systems,” _Computers & Security_, 2019.
  * [37] O. J. A. Pinno, A. R. A. Gregio, and L. C. E. De Bona, “Controlchain: Blockchain as a central enabler for access control authorizations in the iot,” in _IEEE GLOBECOM_ , 2017.


# Enumerating permutations avoiding split patterns $3|12$ and $23|1$

Travis Grigsby<EMAIL_ADDRESS>and  Edward Richmond
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we give a formula for the number of permutations that avoid the
split patterns $3|12$ and $23|1$ with respect to a position $r$. Such
permutations count the number of Schubert varieties for which the projection
map from the flag variety to a Grassmannian induces a fiber bundle structure.
We also study the corresponding bivariate generating function and show how it
is related to modified Bessel functions.

##  1\. Introduction

Let $\operatorname{\mathfrak{S}}_{n}$ denote the permutation group on the set
of integers $\\{1,2,\ldots,n\\}$. In [AR18], the second author and Alland
define the notion of split pattern avoidance on permutations and use this idea
to combiantorially characterize when the projection map of a Schubert variety
to a Grassmannian gives rise to a fiber-bundle structure. Split pattern
avoidance is a specialization of classical pattern avoidance on permutations
and can be described as follows. A split pattern $u=u_{1}|u_{2}$ is a divided
permutation where $u_{1}=u(1)\cdots u(j)$ and $u_{2}=u(j+1)\cdots u(n)$ for
some $1\leq j\leq n$.

######  Definition 1.1.

[AR18, Definition 2.1] Let $w\in\operatorname{\mathfrak{S}}_{n}$ and
$u\in\operatorname{\mathfrak{S}}_{k}$. We say $w=w(1)\cdots w(n)$ contains the
split pattern $u=u(1)\cdots u(j)|u(j+1)\cdots u(k)$ with respect to position
$r$ if there exists a sequence $(1\leq i_{1}<\cdots<i_{k}\leq n)$ such that

  1. (1)

$w(i_{1})\cdots w(i_{k})$ has the same relative order as $u$ and

  2. (2)

$i_{j}\leq r<i_{j+1}$.

If $w$ does not contain $u$ with respect to position $r$, then we say $w$
avoids the split pattern $u$ with respect to position $r$.

Note that condition (1) in the above definition is the classical definition of
pattern containment. If a permutation $w$ avoids a split pattern $u$ with
respect to all positions $r\leq n$, then $w$ avoids $u$ in the traditional
sense. In this paper, we focus on permutations that avoid the split patterns
$3|12$ and $23|1$ which are the same split patterns studied in [AR18] in
connection with Schubert varieties. Diagrammatically, we represent a
permutation $w$ with its corresponding the permutation matrix with nodes
marking the points $(i,w(i))$. Here the point $(1,1)$ marks the lower left
corner. For example, if we consider $w=315642$, then the corresponding
permutation matrix is given by:

We can see that $w$ contains $23|1$ with respect to position $3$ (the pattern
containment is marked by the circled nodes). We can also see that $w$ avoids
$3|12$ with respect to position $3$ since all the nodes to the right of
position 3 are decreasing.

Let $K(r,n)$ denote the set of permutations in
$\operatorname{\mathfrak{S}}_{n}$ that avoid the split patterns $3|12$ and
$23|1$ with respect to position $r$ and define

$k(r,n):=|K(r,n)|.$

For convenience in enumeration, we set $k(0,0):=1$. Observe that rotation of a
permutation matrix by 180 degrees gives a bijection between the sets $K(r,n)$
and $K(n-r,n)$ and hence $k(r,n)=k(n-r,n)$. For any integer $m$ and $i\geq 1$,
let

$(m)_{i}:=m(m-1)\cdots(m-i+1)$

denote the falling factorial. The first main result of this paper the
following formula for $k(r,n)$:

######  Theorem 1.2.

For any, $0\leq r\leq n$, we have

$k(r,n)=r!(n-r)!+\sum_{i=1}^{r}\sum_{j=1}^{n-r}\binom{n-i-j}{r-i}\cdot(r)_{i-1}\cdot(n-r)_{j-1}.$

Table 1 below lists values of $k(r,n)$ for $n\leq 9$ and $r\leq 4$. Note that,
by the symmetry $k(r,n)=k(n-r,n)$, all values of $k(r,n)$ for $n\leq 9$ can be
deduced from the table.

$r\backslash n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
0 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40320 | 362880
1 | 1 | 2 | 5 | 16 | 65 | 326 | 1957 | 13700 | 109601
2 |  | 2 | 5 | 14 | 47 | 194 | 977 | 5870 | 41099
3 |  |  | 6 | 16 | 47 | 162 | 676 | 3416 | 20541
4 |  |  |  | 24 | 65 | 194 | 676 | 2836 | 14359
Table 1. Number of permutations in $\operatorname{\mathfrak{S}}_{n}$ avoiding
the split patterns $3|12$ and $23|1$ with respect to position $r$.

Theorem 1.2 implies that the value $k(r,n)\geq r!(n-r)!$ and hence we consider
the bivariate exponential generating function

$\mathcal{K}(x,y):=\sum_{n=0}^{\infty}\sum_{r=0}^{n}k(r,n)\frac{x^{r}y^{n-r}}{r!(n-r)!}.$

The second main result of this paper is a formula for $\mathcal{K}(x,y)$ which
has a surprising connection with Bessel functions. Consider the complex valued
function

$I_{0}(z)=\frac{1}{\pi}\int_{0}^{\pi}e^{z\cos\theta}d\theta.$

The function $I_{0}(z)$ is called the modified Bessel function of first kind
(at $\alpha=0$) and is a solution to the modified Bessel differential equation

$z^{2}u_{zz}+zu_{z}-z^{2}u=0.$

Bessel equations and their solutions are important objects in the study of
partial differential equations and have several applications in physics
including the modeling of heat conduction, membrane vibration, hydrodynamics
and electrostatics [Tra69, Chapter 7]. For more on the general theory of
Bessel functions see [Wat44]. In this paper, we will primarily use the fact
that $I_{0}$ has power series expansion

(1)
$I_{0}(z)=\sum_{m=0}^{\infty}\frac{1}{(m!)^{2}}\left(\frac{z^{2}}{4}\right)^{m}.$

In fact, this power series expansion of $I_{0}$ is commonly taken as the
definition of the modified Bessel function. The following theorem is the
second main result of this paper.

######  Theorem 1.3.

The generating function $\mathcal{K}(x,y)$ satisfies

$\mathcal{K}(x,y)=\frac{\mathcal{L}(x,y)+1}{1-x-y+xy}$

where

(2) $\mathcal{L}(x,y)=\iint e^{x+y}I_{0}(2\sqrt{xy})\ dx\,dy$

with boundary conditions $\mathcal{L}(x,0)=e^{x}$ and
$\mathcal{L}(0,y)=e^{y}.$

In Proposition 3.2, we prove that the expression $e^{x+y}I_{0}(2\sqrt{xy})$ in
the integral from Equation (2) is a bivariate exponential generating function
for binomial coefficients. Specifically, we show that

(3)
$\sum_{r,s=0}^{\infty}\binom{r+s}{r}\frac{x^{r}y^{s}}{r!\,s!}=e^{x+y}I_{0}(2\sqrt{xy}).$

We remark that there are two other commonly known bivariate generating
functions for binomial coefficients given by

$\sum_{r,s=0}^{\infty}\binom{r+s}{r}x^{r}y^{s}=\frac{1}{1-x-y}\quad\text{and}\quad\sum_{r,s=0}^{\infty}\binom{r+s}{r}\frac{x^{r}y^{s}}{(r+s)!}=e^{x+y}.$

The authors are unaware of any previously known statement or proof for the
“intermediate” generating function for binomials given in Equation (3).

Observe that specializing to $x=y$ in Equation (3) gives

$\displaystyle e^{2x}\cdot I_{0}(2x)$
$\displaystyle=\sum_{r,s=0}^{\infty}\binom{r+s}{r}\frac{x^{r+s}}{r!\,s!}$
$\displaystyle=\sum_{r,s=0}^{\infty}\binom{r+s}{r}^{2}\frac{x^{r+s}}{(r+s)!}.$

Setting $m=r+s$ yields

$\displaystyle e^{2x}\cdot
I_{0}(2x)=\sum_{m=0}^{\infty}\left(\sum_{r=0}^{m}\binom{m}{r}^{2}\right)\frac{x^{m}}{m!}=\sum_{m=0}^{\infty}\binom{2m}{m}\frac{x^{m}}{m!}.$

Hence we recover the formula for the exponential generating function for
central binomial coefficients. In particular, Equation (3) can be viewed as a
bivariate refinement of the generating function for central binomial
coefficients with respect to Vandermonde’s identity. We note that the
connection between central binomial coefficients and Bessel functions was
previously known [Slo] and can be deduced directly from Equation (1).

###  1.1. Connections with Schubert varieties

In this subsection, we give an overview the results found in [AR18] connecting
split pattern avoidance with the fiber bundle structures of Schubert
varieties. These fiber bundle structures are closely connected to Billey-
Postnikov decompositions which studies the parabolic factoring of lower Bruhat
intervals in Coxeter groups [BP05, RS16]. We also remark that pattern
avoidance is a tool commonly used to combinatorially characterize various
geometric properties of Schubert varieties. Most notably, Lakshmibai and
Sandhya show that a Schubert variety is smooth if and only if its indexing
permutation avoids the patterns 3412 and 4231 [LS90]. For a survey on the
connections between the geometry of Schubert varieties and pattern avoidance
see [AB16]. Let $\mathbb{K}$ be an algebraically closed field and let

$\operatorname{F\ell}(n):=\\{(V_{1}\subset V_{2}\subset\cdots\subset
V_{n-1}\subset\mathbb{K}^{n})\ |\ \dim(V_{i})=i\\}$

denote the complete flag variety on $\mathbb{K}^{n}.$ For each $1\leq r\leq
n$, let

$\operatorname{Gr}(r,n):=\\{V\subseteq\mathbb{K}^{n}\ |\ \dim(V)=r\\}$

denote the Grassmannian of $r$-dimensional subspaces of $\mathbb{K}^{n}$ and
consider the projection map

$\pi_{r}:\operatorname{F\ell}(n)\rightarrow\operatorname{Gr}(r,n)$

given by $\pi_{r}(V_{\bullet})=V_{r}.$ Fix a basis $\\{e_{1},\ldots,e_{n}\\}$
of $\mathbb{K}^{n}$ and let $E_{i}:=\operatorname{span}\langle
e_{1},\ldots,e_{i}\rangle$. Each permutation
$w\in\operatorname{\mathfrak{S}}_{n}$ defines a Schubert variety

$X_{w}:=\\{V_{\bullet}\in\operatorname{F\ell}(n)\ |\ \dim(E_{i}\cap V_{j})\geq
r_{w}[i,j]\\}$

where $r_{w}[i,j]:=\\#\\{k\leq j\ |\ w(k)\leq i\\}$. The following theorem
gives a connection between split pattern avoidance and fiber bundle structures
on $X_{w}$ with respect to the projection map $\pi_{r}$.

######  Theorem 1.4.

[AR18, Theorem 1.1] Let $r\leq n$ and $w\in\operatorname{\mathfrak{S}}_{n}$.
The projection $\pi_{r}$ restricted to $X_{w}$ is a Zariski-locally trivial
fiber bundle if and only if $w$ avoids the split patterns $3|12$ and $23|1$
with respect to position $r$.

Theorem 1.4 implies that the number $k(r,n)$ can alternately be viewed as the
number of Schubert varieties $X_{w}\subseteq\operatorname{F\ell}(n)$ for which
the projection $\pi_{r}$ to the Grassmannian $\operatorname{Gr}(r,n)$ induces
a fiber bundle structure on $X_{w}$.

For the remainder of this paper, we focus on proving Theorems 1.2 and 1.3.

##  2\. Enumerating split patterns

In this section we prove Theorem 1.2. For any
$w\in\operatorname{\mathfrak{S}}_{n}$ and $0\leq r\leq n$, define the integer
sets

$\operatorname{\textbf{Left}}_{r}(w):=\\{w(k)\ |\ k\leq
r\\}\quad\text{and}\quad\operatorname{\textbf{Right}}_{r}(w):=\\{w(k)\ |\
k>r\\}.$

For example, if $w=7361254$. Then
$\operatorname{\textbf{Left}}_{4}(w)=\\{1,3,6,7\\}$ and
$\operatorname{\textbf{Right}}_{4}(w)=\\{2,4,5\\}$. Recall that $K(r,n)$
denotes the set of permutations in $\operatorname{\mathfrak{S}}_{n}$ that
avoid the split patterns $3|12$ and $23|1$ with respect to position $r$ and
define

$K_{L}(r,n):=\\{w\in K(r,n)\ |\ n\in\operatorname{\textbf{Left}}_{r}(w)\\}$

and

$K_{R}(r,n):=\\{w\in K(r,n)\ |\ n\in\operatorname{\textbf{Right}}_{r}(w)\\}.$

In other words, $K_{L}(r,n)$ consists of those permutations in $K(r,n)$ for
which $n$ appears within the first $r$ positions in the one-line notation of
$w$ and and $K_{R}(r,n)$ are those for which $n$ appears within the last $n-r$
positions. Clearly, we have

$K(r,n)=K_{L}(r,n)\sqcup K_{R}(r,n).$

Let
$\phi_{n}:\operatorname{\mathfrak{S}}_{n}\rightarrow\operatorname{\mathfrak{S}}_{n-1}$
denote the map that removes $n$ from the one-line notation of a permutation.
For example, we have

$\phi_{6}(432\textbf{6}15)=43215.$

Note that if $w\in\operatorname{\mathfrak{S}}_{n}$ avoids the split patterns
$3|12$ and $23|1$ with respect to position $r$, then $\phi_{n}(w)$ will avoid
these patterns with respect to either position $r$ or $r-1$. In particular, if
$w\in K_{R}(r,n)$, then $\phi_{n}(w)\in K(r,n-1)$, and if $w\in K_{L}(r,n)$,
then $\phi_{n}(w)\in K(r-1,n-1)$. The next proposition is on the restriction
of $\phi_{n}$ to $K_{R}(r,n)$.

######  Proposition 2.1.

The restricted map $\phi_{n}:K_{R}(r,n)\rightarrow K(r,n-1)$ is surjective.
Moreover the fiber size $|\phi_{n}^{-1}(w)|=n-r$ for any $w\in K(r,n-1)$.

###### Proof.

Let $w\in K(r,n-1)$ and for any $1\leq i\leq n-r$, define the permutation
$w_{i}\in\operatorname{\mathfrak{S}}_{n}$ by

$w_{i}(k):=\begin{cases}w(k)&\text{if $k<r+i$}\\\ n&\text{if $k=r+i$}\\\
w(k-1)&\text{if $k>r+i$.}\end{cases}$

In other words, $w_{i}$ is the permutation in $S_{n}$ arising form inserting
$n$ into the $(r+i)$-th position of the one-line notation of $w$. It is easy
to see that $\phi_{n}(w_{i})=w$. Since $w$ avoids $3|12$ and $23|1$ with
respect to position $r$ and $n\in\operatorname{\textbf{Right}}_{r}(w_{i})$, we
have that $w_{i}$ also avoids $3|12$ and $23|1$ with respect to position $r$.
In particular, $w_{i}\in K_{R}(r,n)$. This implies the restricted map
$\phi_{n}:K_{R}(n,r)\rightarrow K(r,n-1)$ is surjective with
$|\phi_{n}^{-1}(w)|\geq n-r$. Finally, suppose $u\in K_{R}(r,n)$. Then
$u^{-1}(n)=r+j$ for some $1\leq j\leq n-r$ and $u=\phi_{n}(u)_{j}$. This
implies $|\phi_{n}^{-1}(w)|=n-r$ for any $w\in K(r,n-1)$. ∎

One consequence of Proposition 2.1 is the following corollary.

######  Corollary 2.2.

For any $1\leq r\leq n$, we have

$k(r,n)=\sum_{j=0}^{n-r}(n-r)_{j}\cdot|K_{L}(r,n-j)|.$

###### Proof.

Since $K(r,n)=K_{L}(r,n)\sqcup K_{R}(r,n)$, we have

$k(r,n)=|K_{R}(r,n)|+|K_{L}(r,n)|.$

Proposition 2.1 implies $|K_{R}(r,n)|=(n-r)\cdot k(r,n-1)$ and hence

$k(r,n)=(n-r)\cdot k(r,n-1)+|K_{L}(r,n)|.$

Applying this decomposition again on $k(r,n-1)$ and iterating this process
yields the desired formula. Note the iteration terminates when $n=r$ in which
case we get $|K_{L}(r,r)|=k(r,r)=r!$. ∎

To prove Theorem 1.2, it suffices to calculate $|K_{L}(r,n)|$.

######  Proposition 2.3.

For any $1\leq r<n$, we have

$|K_{L}(r,n)|=\sum_{i=1}^{r}\binom{n-i-1}{r-i}\cdot(r)_{i-1}.$

###### Proof.

Fix $1\leq r<n$ and for any $1\leq i\leq n$, define the set

$S(i):=\\{w\in K_{L}(r,n)\ |\ \text{$i\in\operatorname{\textbf{Right}}_{r}(w)$
and $k\in\operatorname{\textbf{Left}}_{r}(w)$ for all $k<i$}\\}.$

For example, if $n=9$, $r=6$ and $i=4$, then $w=391276|854\in S(4)$.

The set $S(i)$ can be thought of as the set of permutations in $K_{L}(r,n)$
for which $i$ is the smallest value appearing right of position $r$. Note
that, since $|\operatorname{\textbf{Left}}_{r}(w)|=r$, $S(i)$ is empty for all
$i>r$ . Since every permutation has some smallest value appearing right of
position $r$, we get

$K_{L}(r,n)=\bigsqcup_{i=1}^{r}S(i).$

Fix $1\leq i<r$ and suppose that $w\in S(i)$. Then the permutation matrix of
$w$ can be divided into regions $A,B,C,D$ as follows:

$A$$B$$C$$D$$j$$n$$r$

Given a node $(k,w(k))$ in the permutation matrix of $w$, we will refer to $k$
as the position of the node and $w(k)$ as the value of the node. Since
$k\in\operatorname{\textbf{Left}}_{r}(w)$ for all $k<i$, we must have that
region $D$ is empty (in other words, no nodes of the form $(k,w(k))$ appear in
region $D$). Since region $D$ is empty, the nodes in region $C$ can have any
relative order with $w$ still avoiding $3|12$ and $23|1$ with respect to
position $r$. Moreover, the set of values of the nodes in region $C$ are
exactly $\\{1,2,\ldots,i-1\\}$. Observe that there are $(r)_{i-1}$ ways to
assign $\\{1,2,\ldots,i-1\\}$ to the values $\\{w(1),\ldots,w(r)\\}$ in region
$C$. Any such assignment determines the positions of the nodes found in region
$C$ and hence, it will also determine the positions of the nodes found in
region $A$ (but not the values). Next we determine the number of ways to
select values in region $A$. First note that
$n\in\operatorname{\textbf{Left}}_{r}(w)$ and
$i\in\operatorname{\textbf{Right}}_{r}(w)$, and hence $n$ must the value of
some node in region $A$, while $i$ is a value of some node in region $B$. This
leaves $\displaystyle\binom{n-i-1}{r-i}$ ways to select the remaining values
for the nodes in region $A$. Furthermore, since region $D$ is empty, any such
choice uniquely determines the values of the nodes in region $B$. Since
$n\in\operatorname{\textbf{Left}}_{r}(w)$ and $w$ avoids $3|12$ with respect
to position $r$, the values of the nodes in region $B$ must be decreasing.
Similarly, since $i\in\operatorname{\textbf{Right}}_{r}(w)$ and $w$ avoids
$23|1$ with respect to position $r$, the values of the nodes in region $A$ are
also decreasing. The fact that the nodes in both regions $A$ and $B$ must be
arranged in decreasing order implies

$|S(i)|=\binom{n-i-1}{r-i}\cdot(r)_{i-1}$

and thus

$|K_{L}(r,n)|=\sum_{i=1}^{r}\binom{n-i-1}{r-i}\cdot(r)_{i-1}.$

∎

###### Proof of Theorem 1.2.

Fix $1\leq r\leq n$ and observe that $|K_{L}(r,r)|=k(r,r)=r!$. Corollary 2.2
and Proposition 2.3 imply that

$\displaystyle k(r,n)$
$\displaystyle=r!(n-r)!+\sum_{j=0}^{n-r-1}\left(\sum_{i=1}^{r}\binom{n-j-i-1}{r-i}\cdot(r)_{i-1}\right)\cdot(n-r)_{j}$
$\displaystyle=r!(n-r)!+\sum_{i=1}^{r}\sum_{j=1}^{n-r}\binom{n-i-j}{r-i}\cdot(r)_{i-1}\cdot(n-r)_{j-1}$

∎

##  3\. Generating functions

In this section we prove Theorem 1.3. Our first step will be to isolate the
summation term from the formula found in Theorem 1.2. We show that this
summation term has a nice recursive structure. For any $r,s\geq 0$, we define

(4) $a(r,s):=\frac{k(r,r+s)}{r!\cdot s!}-1.$

Note that $a(0,0)=0$ since $k(0,0)=1$. We also have $a(r,s)=a(s,r)$ by the
symmetry $k(r,r+s)=k(s,r+s)$.

######  Lemma 3.1.

The values $a(r,s)$ satisfy the recursion

(5) $a(r,s)=a(r,s-1)+a(r-1,s)-a(r-1,s-1)+\binom{r+s-2}{r-1}\frac{1}{r!\,s!}$

with initial conditions $a(r,0)=a(0,s)=0$ for all $r,s\geq 0$.

###### Proof.

First note that $a(r,0)=a(0,s)=0$ since $k(r,r)=r!$. Now if $r,s>0$, then
Theorem 1.2 implies

$\displaystyle a(r,s)$
$\displaystyle=\sum_{i=1}^{r}\sum_{j=1}^{s}\binom{r+s-i-j}{r-i}\frac{(r)_{i-1}(s)_{j-1}}{r!\,s!}$
$\displaystyle=\sum_{i=1}^{r}\sum_{j=1}^{s}\binom{r+s-i-j}{r-i}\frac{1}{(r-i+1)!(s-j+1)!}.$

Reversing the ordering in the summations gives

$a(r,s)=\sum_{i=0}^{r-1}\sum_{j=0}^{s-1}\binom{i+j}{i}\frac{1}{(i+1)!(j+1)!}.$

Equation (5) immediately follows from this formula. ∎

Define the ordinary generating function

$\mathcal{A}(x,y):=\sum_{r,s=0}^{\infty}a(r,s)\,x^{r}y^{s}.$

Lemma 3.1 implies

(6) $\mathcal{A}(x,y)=\frac{\mathcal{L}(x,y)}{1-x-y+xy}$

where

$\mathcal{L}(x,y):=\sum_{r,s=0}^{\infty}\binom{r+s-2}{r-1}\frac{x^{r}y^{s}}{r!\,s!}.$

For the second step, we study the function $\mathcal{L}(x,y)$. Taking the
mixed partial derivative of $\mathcal{L}(x,y)$ yields a bivariate exponential
generating function for binomial coefficients:

(7)
$\partial_{xy}(\mathcal{L}(x,y))=\sum_{r,s=0}^{\infty}\binom{r+s}{r}\frac{x^{r}y^{s}}{r!\,s!}.$

Let

$I_{0}(z)=\frac{1}{\pi}\int_{0}^{\pi}e^{z\cos\theta}d\theta$

denote the modified Bessel function of first kind. It is well known that
$I_{0}(z)$ has generating function

$I_{0}(z)=\sum_{m=0}^{\infty}\frac{1}{(m!)^{2}}\left(\frac{z^{2}}{4}\right)^{m}.$

######  Proposition 3.2.

The exponential generating function for binomial coefficients is given by

(8) $\sum_{r,s=0}^{\infty}\binom{r+s}{r}\frac{x^{r}y^{s}}{r!\,s!}=e^{x+y}\cdot
I_{0}(2\sqrt{xy}).$

###### Proof.

Expanding the right hand side of Equation (8) gives

$\displaystyle e^{x+y}\cdot I_{0}(2\sqrt{xy})$
$\displaystyle=\left(\sum_{a,b=0}^{\infty}\frac{x^{a}y^{b}}{a!\,b!}\right)\left(\sum_{m=0}^{\infty}\frac{(xy)^{m}}{(m!)^{2}}\right)$
$\displaystyle=\sum_{a,b,m=0}^{\infty}\binom{a+m}{m}\binom{b+m}{b}\frac{x^{a+m}y^{b+m}}{(a+m)!(b+m)!}.$

If we re-index the summands by setting $r=a+m$ and $s=b+m$ and apply
Vandermonde’s identity on binomials, we get

$\displaystyle e^{x+y}\cdot I_{0}(2\sqrt{xy})$
$\displaystyle=\sum_{r,s=0}^{\infty}\left(\sum_{m=0}^{\min(r,s)}\binom{r}{m}\binom{s}{s-m}\right)\frac{x^{r}y^{s}}{r!\,s!}$
$\displaystyle=\sum_{r,s=0}^{\infty}\binom{r+s}{s}\frac{x^{r}y^{s}}{r!\,s!}.$

∎

###### Proof of Theorem 1.3.

By the definition given in Equation (4), we have

$\displaystyle\mathcal{K}(x,y)$
$\displaystyle=\sum_{r,s=0}^{\infty}k(r,r+s)\frac{x^{r}y^{s}}{r!\,s!}$
$\displaystyle=\sum_{r,s=0}^{\infty}(a(r,s)+1)\,x^{r}y^{s}$
$\displaystyle=\mathcal{A}(x,y)+\frac{1}{1-x-y+xy}.$

Equation (6) implies

$\mathcal{K}(x,y)=\frac{\mathcal{L}(x,y)+1}{1-x-y+xy}.$

The theorem now follows from Proposition 3.2 and Equation (7). ∎

## References

  * [AB16] Hiraku Abe and Sara Billey, _Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry_ , Schubert calculus—Osaka 2012, Adv. Stud. Pure Math., vol. 71, Math. Soc. Japan, [Tokyo], 2016, pp. 1–52. MR 3644818
  * [AR18] Timothy Alland and Edward Richmond, _Pattern avoidance and fiber bundle structures on Schubert varieties_ , J. Combin. Theory Ser. A 154 (2018), 533–550. MR 3718076
  * [BP05] Sara Billey and Alexander Postnikov, _Smoothness of Schubert varieties via patterns in root subsystems_ , Adv. in Appl. Math. 34 (2005), no. 3, 447–466. MR 2123545
  * [LS90] V. Lakshmibai and B. Sandhya, _Criterion for smoothness of Schubert varieties in ${\rm Sl}(n)/B$_, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), no. 1, 45–52. MR 1051089
  * [RS16] Edward Richmond and William Slofstra, _Billey-Postnikov decompositions and the fibre bundle structure of Schubert varieties_ , Math. Ann. 366 (2016), no. 1-2, 31–55. MR 3552231
  * [Slo] N. J. A. Sloane, _Central binomial coefficients, entry A000984 in the On-line Encyclopedia of Integer Sequences_ , https://oeis.org/A000984.
  * [Tra69] C. J. Tranter, _Bessel functions with some physical applications_ , Hart Publishing Co., Inc., New York, 1969. MR 241714
  * [Wat44] G. N. Watson, _A Treatise on the Theory of Bessel Functions_ , Cambridge University Press, Cambridge; The Macmillan Company, New York, 1944. MR 10746