# Scalable and Lightweight Post-Quantum Authentication for Internet of Things

Attila A. Yavuz<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Saleh Darzi<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Saif E. Nouma
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Internet of Things (IoT) applications are composed of massive quantities of
resource-limited devices that collect sensitive data with long-term
operational and security requirements. With the threat of emerging quantum
computers, Post-Quantum Cryptography (PQC) is a critical requirement for IoTs.
In particular, digital signatures offer scalable authentication with non-
repudiation and are an essential tool for IoTs. However, as seen in NIST PQC
standardization, post-quantum signatures are extremely costly for resource-
limited IoTs. Hence, there is a significant need for quantum-safe signatures
that respect the processing, memory, and bandwidth limitations of IoTs.

In this paper, we created a new lightweight quantum-safe digital signature
referred to as $\texttt{INFinity}\mathchar 45\relax\texttt{HORS}$
($\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$), which is (to the best of
our knowledge) the first signer-optimal hash-based signature with
(polynomially) unbounded signing capability. $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ enables a verifier to non-interactively construct
one-time public keys from a master public key via encrypted function
evaluations. This strategy avoids the performance bottleneck of hash-based
standards (e.g., SPHINCS+) by eliminating hyper-tree structures. It also does
not require a trusted party or non-colliding servers to distribute public
keys. Our performance analysis confirms that $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ is magnitudes of times more signer computation
efficient than selected NIST PQC schemes (e.g., SPHINCS+, Dilithium, Falcon)
with a small memory footprint.

###### Index Terms:

Internet of Things, post-quantum security, lightweight authentication, digital
signatures.

##  I Introduction

Several initiatives are taken for the next-generation networked systems [1]
that open new opportunities for high connectivity rates, making autonomous
systems and virtual reality applications a near possibility. The Internet of
Things (IoT) harbors a wide range of connected computing devices that collect,
process, and communicate sensitive data at large scales. IoT applications are
expected to be an integral part of next-generation networks [1]. For instance,
smart-health applications [2] rely on a large number of resource-constrained
devices (e.g., medical wearables [3]) that gather security-sensitive patient
and infrastructure information. Such IoT systems need lightweight cyber-
security mechanisms that can support massive amounts of devices to respect the
resource limitations and scalability requirements of next-generation networks
[4].

Authentication and integrity are essential cybersecurity services that protect
sensitive data from critical attacks (e.g., man-in-the-middle attacks, data
tampering) in IoT infrastructures. Digital signatures [5] rely on Public Key
Infrastructures (PKIs) to offer scalability for large-scale networks and lay
the foundation of authentication and integrity in many IoT applications.
Furthermore, they offer non-repudiation which is an important property for
various real-life applications (e.g., financial, medical). The standard
digital signatures (e.g. , RSA, ECDSA [6]) rely on conventional cryptographic
assumptions such as (Elliptic Curve) Discrete Logarithm Problem (ECDLP).
However, many of the well-known conventional digital signatures (e.g., ECDSA
[6], Ed25519 [7]) might not meet the stringent requirements of low-end IoTs in
terms of memory, computation, and bandwidth.

The emergence of quantum computers severely exacerbates the efficiency hurdles
of digital signatures for resource-limited IoTs. The standard cryptographic
techniques that rely on conventional intractability assumptions (e.g., ECDLP)
can be broken by quantum computers with Shor’s algorithm [8]. The threat of
quantum computers over conventional cryptography garnered much attention from
the industry, academia, and government. Especially, NIST’s Post-Quantum
Cryptography (PQC) standardization process recently announced their selected
digital signatures (CRYSTALS-Dilithium as the Module-Lattice-Based Digital
Signature Standard (FIPS 204) and SPHINCS+ as Stateless Hash-Based Digital
Signature Standard (FIPS 205)) [9]. Despite their elegance, these post-quantum
signatures are not designed for resource-limited IoT systems. They are
significantly more computationally costly with a large signature size than
conventional digital signatures. As shown with experiments (see Table I), they
are extremely costly for low-end devices and therefore are likely not
practical for IoTs that must operate for long periods amid battery, processor,
and bandwidth constraints [10].

There is a significant need for lightweight post-quantum signatures that
respect the strict memory, computation, and bandwidth limitations of resource-
constrained IoT applications. In particular, the heavy overhead of current
post-quantum signatures on embedded devices is a severely limiting factor in
their real-life deployment. In this work, we aim to answer the following
research questions:

(i) Is it possible to achieve efficient quantum-safe signing with only
symmetric cryptographic operations? (ii) Is it possible to permit efficient
signing without imposing non-conventional and risky assumptions on the
verifier like non-colluding multiple servers or third parties storing secret
keys? (iii) Can we meet these requirements in a multi-user setting to scale
IoTs?

In the following, we first outline the research gap in the state-of-the-art
with a focus on the NIST PQC standardization effort and then summarize our
contribution.

###  I-A Related Work and Limitations of the State-of-the-Art

Numerous conventional digital signatures proffer a highly efficient signature
generation and small key sizes alongside strong security guarantees (e.g.,
[11, 12, 13, 14]). The proposed schemes based on the seminal elliptic-curve
Schnorr [7] stand out for their efficiency compared to other conventional
signature categories (e.g., pairing-based BLS [15], factorization-based RSA).
They often incorporate advanced security properties. For instance, OSLO [12]
is a signer-efficient EC-based signature scheme offer signature aggregation.
Alternatively, Chen et al. [14] offer confidentiality with authentication.
Also, Glas et al. [16] proposes a bandwidth-aware and backward-compatible
protocol that achieves authentication and integrity. Despite their merits,
none of them offer post-quantum security.

NIST is actively standardizing Post-Quantum Cryptography (PQC). Recently, NIST
disclosed the chosen post-quantum signatures for standardization [9],
featuring two lattice-based schemes and one hash-based scheme. The hash-based
standard SPHINCS+ [17] is based on the one-time signature HORS [18] and adopts
a hyper-tree structure to construct a multiple-time signature. SPHINCS+
achieve post-quantum security but with a signing time that is $62\times$
slower than ECDSA with $517\times$ bigger signature size [17]. Therefore, it
is not suitable for resource-constrained IoT devices. The two lattice-based
selected NIST standards are Dilithium [19] and Falcon [20]. They offer smaller
signature sizes and faster signing than their hash-based counterparts (e.g.,
SPHINCS+). Despite their elegance, these schemes are not designed for
resource-constrained IoTs. They incur more costly computations with larger
signature sizes compared with conventional signatures. Moreover, the lattice-
based signatures involve Gaussian and/or rejection sampling that are prone to
side-channel attacks (e.g., [21]). To our knowledge, there is no deployable
open-source implementation of lattice-based signatures available on highly
resource-limited embedded devices (e.g., 8-bit platforms) with the exception
of BLISS [22], which was not selected as a NIST PQC standard.

NIST also launched an additional competition, alongside standardized schemes,
to encourage diversity in signature standardization, emphasizing fast
verification and short signatures. The submissions are heterogeneous and cover
all PQC categories. For instance, there exist a lightweight post-quantum
digital signature based on multivariate quadratic equations [23]. Despite its
efficiency advantage over NIST PQC standards, it still entails large key sizes
compared to conventional digital signatures. Its private key is $12.6$ KB
which is $135\times$ larger than the ECDSA. Thus, it incurs a costly memory
usage for low-end IoT devices (e.g., 8-bit AVR ATmega2560) without considering
the algorithm code size. Despite the PQC progress and the real-world
applications, addressing the computational demands and key sizes of these
schemes remains a significant challenge for meeting the requirements of IoT
devices, often operate on 8-bit microcontrollers [24].

There are recent post-quantum digital signatures that offer a highly efficient
signature generation at the cost of additional assumptions [23]. For instance,
ANT [4] is a lattice-based digital signature that delegates costly generated
commitments to a set of distributed non-colluding servers. ANT assume that
distributed servers are within the semi-honest setting and they should not
collude among themselves. Additionally, the verifier should communicate to the
distributed servers in order to perform the verification, therefore incurring
network delays and outage risks. There is another line of TEE-assisted digital
signatures that offload the burden of the costly computations to a TEE-enabled
server. For instance, HASES [25] is a hash-based digital signature based on
the one-time digital signature HORS [18]. It relies on a TEE-enabled server to
supply the verifier with the public keys. However, the reliance on a single
TEE-enabled server causes a central root of trust and public-key escrow.
Overall, these types of digital signatures are not within the conventional
public key settings due to the reliance of additional assumptions, and
therefore they might not be suitable for some IoT applications.

There is a pressing demand for efficient quantum-safe digital signatures
tailored to the performance and security constraints of resource-limited IoT
applications. These signatures must address these needs without relying on
assumptions that may not be applicable in diverse real-world scenarios, all
while maintaining a lightweight design.

###  I-B Our Contribution

We created a novel lightweight post-quantum signature named as
$\texttt{INFinity}\mathchar 45\relax\texttt{HORS}$ ($\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$). Our key observation is that the main overhead of
hash-based signatures stems from the management of one-time public keys. To
address this problem, we develop innovative strategies that permit verifiers
to construct one-time public keys without interacting with the signers or any
other third parties. $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$
transforms one-time HORS into a mutliple-time signature by permitting
verifiers to extract one-time keys from a master public key via encrypted
pseudo-random function evaluations. To the best of our knowledge, this is the
first HORS-type (hash-based) scheme that lift the limitation of number of
messages to be signed, without having special assumptions like semi-honest
servers (ANT [4]), trusted hardware (HASES [25]) or extremely costly signing
and signatures (XMSS, SPHINCS+). This approach offers several desirable
properties as follows:

(1) Signer Computational/Energy Efficiency: Our scheme makes only one call to
the underlying one-time signature with identical tag sizes, and it is optimal
with respect to HORS. Hence, $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$
perform only a small-constant number (e.g., $16$) of Pseudo-Random Function
(PRF) calls per signing. Table I shows that $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ signature generation is $300\times$ and $1581\times$
faster than NIST PQC winners Dilithium-II and Falcon-512, respectively, on an
embedded device. It is even significantly more efficient than the best
conventional-secure (ECC-based) signatures. As shown in Section V, this
efficiency also translates into substantial energy savings.

(2) High Memory and Bandwidth Efficiency: The private key of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is just a single random seed
(e.g., 128-bit), and it transmits only one HORS signature per message. Hence,
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ has the smallest private key
and the most compact signature among its PQ counterparts (see Table I).

(3) Online/Offline Verification: $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ enables verifiers to derive one-time public keys from
the master public key either on-demand or prior to verification. The one-time
public key construction is computationally costly due to the encrypted
function evaluations. However, it can be done before receiving signatures. It
can be run by the verifier stand-alone or can be offloaded to a resourceful
cloud server. Hence, the overhead of public key construction is substantially
mitigated in practice.

(4) Compact Multi-User Storage: $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ allows verifier to construct a target one-time public
key for any given valid signer identity and state from a constant-size master
public key. This permits compact storage for a large number of users
considering their otherwise individual public keys and certificates to be
maintained (e.g., $2^{20}$ users).

(5) Advanced Security Features: (i) $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ follows the standard public key setting. Unlike some
quantum-safe alternatives [4], it refrains from unconventional assumptions
like non-colluding servers. Similarly, $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ avoids security assumptions like trusted private key
servers to ferry public keys which introduce architectural risk. (ii) The
Gaussian and rejection sampling operations in lattice-based are highly prone
to side-channel and timing attacks (e.g., [21]). $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ only relies on symmetric primitives, therefore is
free from these types of attacks. Moreover, $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ uses deterministic signing that can mitigate the
vulnerabilities stemming from weak random number generators typically found in
low-end IoTs.

All these properties indicate that $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ is an ideal post-quantum signature to achieve
lightweight and scalable authentication for resource-limited IoT applications.

Limitations: The signature verification of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ is costlier than the NIST PQC digital signatures with
substantially larger public key. Therefore, the verification is not real-time
and it consumes a higher memory usage compared to the state-of-the-art
counterparts. However, we have demonstrated that this is a profitable trade-
off for a non-interactive signer that require near-optimal signing, compact
signatures, and side-channel resiliency. Therefore, we foresee that
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is suitable for applications
that require a near-optimal signer performance at the cost of a delay
tolerance on the verifier side (e.g., audit logging and future forensic
investigation [12]).

##  II Preliminaries

Notation: $|x|$, $||$, and
$x\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\mathcal{S}$ denote the bit
length of the variable $x$, concatenation, and choosing $x$ randomly from the
set $\mathcal{S}$, respectively. $\oplus$ is the bitwise-XOR operation.
${\\{q_{i}\\}}_{i=1}^{n}$ denotes the set of items
$\\{q_{1},q_{2},\ldots,q_{n}\\}$.
$H:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\kappa}$ is a cryptographic hash
function.
$\texttt{PRF}{}:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\kappa}$
is a Pseudo-Random Function (PRF) $x\leftarrow{}\texttt{PRF}{}(k,M)$ that
takes a key $k$ and message $M$ as input, and produces $x$ as the output.
$f:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\kappa}$ is a one-way function.
$\\{0,1\\}\leftarrow{}\texttt{CMP}{}(x,y)$ denotes the equality comparison
function (circuit) of two numerical values (e.g., $x$ and $y$ can be $64$-bit
integers). $C\leftarrow{}E_{k}(m)$ denotes as the encryption of message $m$
with the key $k$ producing ciphertext $C$. $E$ is an Indistinguishability
under Chosen-Plaintext Attack (IND-CPA) secure block cipher.

###### Definition 1

Hash to Obtain Random Subset (HORS) [18] is a one-time signature scheme
comprised of three algorithms:

  * -

$\underline{(\mathit{sk}{},\mathit{PK}{},I_{\texttt{HORS}}{})\leftarrow{}\texttt{HORS.Kg}{}(1^{\kappa})}$:
Given the security parameter $\kappa$, it selects
$I_{\texttt{HORS}}{}\leftarrow{}(k,t)$, generates $t$ random $\kappa$-bit
strings $\\{s_{i}\\}_{i=1}^{t}$, and computes
$v_{i}\leftarrow{}f(s_{i}),\forall i=1,\ldots,t$. Finally, it sets
$\mathit{sk}{}\leftarrow{}\\{s_{i}\\}_{i=1}^{t}$ and
$\mathit{PK}{}\leftarrow{}\\{v_{i}\\}_{i=1}^{t}$.

  * -

$\underline{\sigma\leftarrow{}\texttt{HORS.Sig}{}(\mathit{sk}{},M)}$: Given
$\mathit{sk}$ and message $M$, it computes $h\leftarrow{}H(M)$. It splits $h$
into $k$ substrings $\\{h_{j}\\}_{j=1}^{k}$ (where $|h_{j}|=\log_{2}{t}$) and
interprets them as integers $\\{i_{j}\\}_{j=1}^{k}$. It outputs
$\sigma\leftarrow{}\\{s_{i_{j}}\\}_{j=1}^{k}$.

  * -

$\underline{b\leftarrow{}\texttt{HORS.Ver}{}(\mathit{PK}{},M,\sigma)}$: Given
$\mathit{PK}$, $M$, and $\sigma$, it computes $\\{i_{j}\\}_{j=1}^{k}$ as in
$\texttt{HORS.Sig}{}(.)$. If $v_{i_{j}}=f(\sigma_{j}),\forall j=1,\ldots,k$,
it returns $b=1$, else it returns $b=0$.

###### Definition 2

A Fully Homomorphic Encryption scheme (FHE) [26] is comprised of four
probabilistic polynomial-time algorithms
$\texttt{FHE}{}=(\texttt{Kg}{},\texttt{Enc}{},\texttt{Eval}{},\texttt{Dec}{})$
defined as below:

  * -

$(\mathit{sk}{}’,\mathit{PK}{}’,I_{\texttt{FHE}{}})\leftarrow{}\texttt{FHE.Kg}{}(1^{\kappa})$:
Given $\kappa$, it creates the auxiliary argument $I_{\texttt{FHE}{}}$ and
generates FHE private/public key pair
$(\mathit{sk}{}^{\prime},\mathit{PK}{}^{\prime})$.

  * -

$C\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}’,M)$: Given
$\mathit{PK}{}^{\prime}$ and a plaintext $M$, it encrypts $M$ and returns the
ciphertext $C$.

  * -

$C\leftarrow{}\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\mathcal{F}(\overrightarrow{c}=\\{c_{j}\\}_{j=1}^{n}))$:
Given $\mathit{PK}{}^{\prime}$, a function $\mathcal{F}$, and a set of input
arguments $\overrightarrow{c}$, it evaluates $\mathcal{F}$ on
$\overrightarrow{c}$ under encryption.

  * -

$M\leftarrow{}\texttt{FHE.Dec}{}(\mathit{sk}{}^{\prime},C)$: Given
$\mathit{sk}{}^{\prime}$ and $C$, it decrypts $C$ via $\mathit{sk}{}^{\prime}$
and outputs the plaintext $M$.

For illustration,
$\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\texttt{PRF}{}(Y,x))$ and
$\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\texttt{CMP}{}(x_{1},x_{2}))$
evaluate $\texttt{PRF}{}(y,x)$ and $\texttt{CMP}{}(X_{1},X_{2})$ functions
under encryption, where the key $Y$ and the numerical values ($X_{1},X_{2}$)
are the encryption of $y$, $x_{1}$, and $x_{2}$ under $\mathit{PK}{}^{\prime}$
(i.e., $Y\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},y)$,
$X_{1}\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},x_{1})$,
$X_{2}\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},x_{2})$),
respectively. We choose an IND-CPA secure FHE instantiated with the Ring
Learning With Error (R-LWE) variant of the BGV cryptosystem [27]. Note that
these FHE instantiations also have a post-quantum security premise [28].

The Davies-Meyer scheme (DM) [29] is an iterated cryptographic hash function
based on a block cipher. In $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$,
we only rely on the one-wayness (OWF) of DM, which is based on the IND-CPA
security of symmetric cipher $E$.

###### Definition 3

$\underline{B_{n}\leftarrow{}\texttt{DM}{}(M,B_{0})}$: Given a message
$M=\\{m_{i}\\}_{i=1}^{n}$ with $n$ blocks, a pre-defined initial value
$I_{\texttt{DM}{}}=B_{0}$, block cipher $E$ of length $k$, it computes
$n=\lceil\frac{|M|}{k}\rceil$, and $B_{i}=E_{m_{i}}(B_{i-1})\oplus
m_{i},\forall i=1,2,...,n$. It outputs $B_{n}$.

###### Definition 4

A Public Key Outsourced Signature scheme $\texttt{PKO}\mathchar
45\relax\texttt{SGN}{}=(\texttt{Kg}{},\texttt{Sig}{},\texttt{PKConstr}{},\texttt{Ver}{})$
is as follows:

  * -

$(\mathit{PK}{},\mathit{sk}{},I)\leftarrow{}\texttt{PKO}\mathchar
45\relax\texttt{SGN.Kg}{}(1^{\kappa},\overrightarrow{ID})$: Given $\kappa$ and
set of users’ identifiers $\overrightarrow{ID}$, it returns $\mathit{PK}{}$
with both FHE and master public keys
$\mathit{PK}{}=\langle\mathit{PK}{}^{\prime},\mathit{MPK}{}\rangle$, the
private key $\mathit{sk}{}=\overrightarrow{\gamma}$, and the system-wide
parameters $I\leftarrow{}I_{\texttt{FHE}}{}$.

  * -

$\sigma_{i}^{j}\leftarrow{}\texttt{PKO}\mathchar
45\relax\texttt{SGN.Sig}{}(\gamma_{i},M_{j})$: Given the seed
$\gamma_{i}\in\overrightarrow{\gamma}$ of $ID_{i}$ and a message $M_{j}$, it
returns the signature $\sigma_{i}^{j}$.

  * -

$cv_{i}^{j}\leftarrow{}\texttt{PKO}\mathchar
45\relax\texttt{SGN.PKConstr}{}(\mathit{PK}{},ID_{i},j)$: Given the signer
$ID_{i}$, state $j$, and $\mathit{PK}{}$, it constructs the required public
keys under encryption $cv_{i}^{j}$ via $\texttt{FHE.Eval}{}(.)$.

  * -

$b\leftarrow{}\texttt{PKO}\mathchar
45\relax\texttt{SGN.Ver}{}(\mathit{PK}{}_{i}^{j},M_{j},\sigma_{i}^{j})$: Given
$\mathit{PK}{}_{i}^{j}$, $M_{j}$, and $\sigma_{i}^{j}$, it outputs $b=1$ if
$\sigma_{i}^{j}$ is valid, or $b=0$ otherwise.

##  III Models

System Model: We follow the traditional heterogeneous public-key-based
broadcast authentication model. (i) Signer: is a resource-constrained IoT
device. It only signs messages and transmits (broadcasts) signatures along
with the corresponding messages. (ii) Verifier: is the recipient of both
messages and signatures from signers. In $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$, the verifier constructs one-time public keys from
the master public key $\mathit{PK}$. The verifier can perform this
construction by itself, and therefore, unlike some other public key
construction models (e.g., [4]), our scheme does not necessitate a third type
of architectural entity (e.g., non-colluding servers or a trusted parties). In
Section IV, we also discuss optional alternatives in which the verifier can
outsource the public key construction to a resourceful entity (e.g., computing
cloud).

Threat and Security Model: Our threat model focuses on a resource active
adversary $\mathcal{A}$ who intercepts and/or tampers with communication.
$\mathcal{A}$ aims to produce an existential forgery to break the signature
scheme. Therefore, our security model relies upon the standard Existential
Unforgeability under Chosen Message Attack (EU-CMA) model[5].

###### Definition 5

The EU-CMA experiment for $\texttt{PKO}\mathchar 45\relax\texttt{SGN}$ is
defined as follows:

  * -

$(\mathit{PK}{},\mathit{sk}{},I)\leftarrow{}\texttt{PKO}\mathchar
45\relax\texttt{SGN.Kg}{}(1^{\kappa},\overrightarrow{ID})$

  * -

$(M^{*},\sigma^{*})\leftarrow{}\mathcal{A}^{\texttt{PKO}\mathchar
45\relax\texttt{SGN.Sig}{}_{\mathit{sk}{}}(.),\texttt{PKO}\mathchar
45\relax\texttt{SGN.PKConstr}{}(.)}(PK,I)$:

  * -

If $\texttt{PKO}\mathchar
45\relax\texttt{SGN.Ver}{}(\mathit{PK}{},M^{*},\sigma^{*})==1$ and $M^{*}$ was
not queried to $\texttt{PKO}\mathchar
45\relax\texttt{SGN.Sig}{}_{\mathit{sk}{}}(.)$, return $1$, else $0$.

The advantage of $\mathcal{A}$ in this experiment is as follows:

$\mathit{Adv}_{\mathit{\texttt{PKO}\mathchar
45\relax\texttt{SGN}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(\mathcal{A})=Pr[\mathit{Expt}_{\texttt{PKO}\mathchar
45\relax\texttt{SGN}{}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}(\mathcal{A})=1]$

The $\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$ advantage of SGN is defined
as:

$\mathit{Adv}_{\mathit{\texttt{PKO}\mathchar
45\relax\texttt{SGN}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t,q_{s})=\underset{\mathcal{A}}{\textnormal{max}}\\{\mathit{Adv}_{\mathit{\texttt{PKO}\mathchar
45\relax\texttt{SGN}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(\mathcal{A})\\}$

where $t$ is the time complexity of $\mathcal{A}$ and $q_{s}$ is the number of
queries to the public key constructor and signature.

##  IV Proposed Schemes

We first present our proposed scheme, $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$. We then describe its instantiations, design
rationale, and optimizations.

###  IV-A Our Proposed $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ Scheme

The main bottleneck of hash-based digital signatures is the generation and
management of one-time public keys. As outlined in Section I-A, the existing
alternatives rely on hyper-tree structures that incur extreme signature
generation and transmission overhead. A trivial yet insecure approach would be
to share the master secret key with a trusted party that replenishes one-time
keys for the verifiers. However, this invalidates the non-repudiation and
makes the system vulnerable to key compromises. Moreover, it is not scalable
to large-IoTs due to the massive transmission overhead.

We address this public key management conundrum by introducing a novel
approach that permits verifiers to construct one-time keys from a master
public key via encrypted evaluations. Our idea is to wrap the master secret
key with homomorphic encryption and then enable any verifier to retrieve one-
time public keys for any valid signer $ID_{i}$ and message $M_{i}^{j}$. This
allows signers to achieve optimal efficiency concerning HORS since it only
computes and broadcasts one HORS signature per message. The verifiers can
construct one-time public keys via encrypted evaluations without the risk of
private key compromises. Our approach effectively transforms one-time HORS
into practically unbounded hash-based signature, and therefore fittingly, we
name our new scheme $\texttt{INFinity}\mathchar 45\relax\texttt{HORS}$
($\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$). We provide the details of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ in Algorithm 1.

Algorithm 1 INFinity HORS ($\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$)
Scheme

1:$\underline{(\mathit{PK}{},\overrightarrow{\gamma},I)\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Kg}{}(1^{\kappa},\overrightarrow{ID}=\\{ID_{i}\\}_{i=1}^{N})}$:

2:$\mathit{msk}{}\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\\{0,1\\}^{\kappa}$
and set
$I\leftarrow{}(I_{\texttt{HORS}}{}=(k,t),I_{\texttt{FHE}}{},I_{\texttt{DM}}{})$
according to Definitions 1, 2, 3.

3:for $i=1,2,\ldots,N$ do

4: $\gamma_{i}\leftarrow{}\texttt{PRF}{}(\mathit{msk}{},ID_{i})$

5:$(\mathit{sk}{}^{\prime},\mathit{PK}{}^{\prime})\leftarrow{}\texttt{FHE.Kg}{}(1^{\kappa},I_{\texttt{FHE}{}})$

6:$\mathit{MPK}{}\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},\mathit{msk}{})$,
$\mathit{PK}{}=\langle\mathit{PK}{}^{\prime},\mathit{MPK}{}\rangle$

7:return
($\mathit{PK}{},\overrightarrow{\gamma}=\\{\gamma_{i}\\}_{i=1}^{N},I$), where
$\gamma_{i}$ is securely given $ID_{i}$

1:$\underline{\sigma_{i}^{j}\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Sig}{}(\gamma_{i},M_{i}^{j})}$: The signer $ID_{i}$
computes signature on message $M_{i}^{j}$ as follows:

2:$\mathit{sk}{}_{i}^{j}\leftarrow{}\texttt{PRF}{}(\gamma_{i},j)$

3:$h\leftarrow{}H(M_{i}^{j})$, split $h$ into $k$ sub-strings
$\\{h_{\ell}\\}_{\ell=1}^{k}$ where $|h_{\ell}|=\log_{2}t$, and interpret each
$\\{h_{\ell}\\}_{\ell=1}^{k}$ as an integer $\\{x_{\ell}\\}_{\ell=1}^{k}$.

4:for $\ell=1,2,...,k$ do

5: $s_{\ell}^{j}\leftarrow{}\texttt{PRF}{}(\mathit{sk}{}_{i}^{j},x_{\ell})$

6:Set $j\leftarrow{}j+1$ and return
$\sigma_{i}^{j}=(s_{1}^{j},s_{2}^{j},...,s_{k}^{j},j)$

1:$\underline{cv_{i}^{j}\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(\mathit{PK}{},ID_{i},j)}$: Performed by
the verifier for given $ID_{i}\in\overrightarrow{ID}$ and state $j$. The
verifier can perform it offline before receiving signatures, or optionally
outsource it to a powerful entity.

2:$c\gamma_{i}\leftarrow{}\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\texttt{PRF}{}(\mathit{MPK}{},ID_{i}))$

3:$\mathit{csk}{}_{i}^{j}\leftarrow{}\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\texttt{PRF}{}(c\gamma_{i},j))$

4:for $\ell=1,2,...,t$ do

5:
$cv_{\ell}^{j}\leftarrow{}\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},f(\texttt{PRF}{}(\mathit{csk}{}_{i}^{j},\ell)))$

6:return $cv_{i}^{j}\leftarrow{}(cv_{1}^{j},cv_{2}^{j},...,cv_{t}^{j})$

1:$\underline{b_{i}^{j}\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Ver}{}(\mathit{PK}{},M_{i}^{j},\sigma_{i}^{j})}$:

2:$cv_{i}^{j}\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(\mathit{PK}{},ID_{i},j)$

3:Execute Step 2 in $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.Sig(.)

4:for $\ell=1,2,...,k$ do

5: $v_{x_{\ell}}^{j}\leftarrow{}f(s_{\ell}^{j})$

6:
$CV_{\ell}^{j}\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},v_{\ell}^{j})$

7:
$b_{\ell}^{j}\leftarrow{}\texttt{FHE.Eval}{}(\mathit{PK}{}^{\prime},\texttt{CMP}{}(cv_{\ell}^{j},VC_{\ell}^{j}))$

8:if $b_{\ell}^{j}=1,\forall\ell\in[1,k]$ then return $b_{i}^{j}=1$ else
return $b_{i}^{j}=0$

The key generation algorithm $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Kg}{}(.)$ first derives the master signing key
$\mathit{msk}{}$ and sets up the public parameters $I$ including HORS, FHE,
and DM parameters as in Definition 1, Definition 2, and Definition3,
respectively (Step 1). It derives the initial private key $\gamma_{i}$ (seed)
of each signer with identifier $ID_{i}$ (Step 3-4). It then generates an FHE
key pair $(\mathit{sk}{}^{\prime},\mathit{PK}{}^{\prime})$, encrypts
$\mathit{msk}$ with $\mathit{PK}{}^{\prime}$ to generate master public key
$\mathit{MPK}$, and sets $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$
public key as $PK=(\mathit{PK}{}^{\prime},\mathit{MPK}{})$ (Step 5). As
elaborated in public key construction, this permits any verifier to extract a
one-time public key from the master key under encryption without exposing it.
Finally, all private and public keys are distributed to the verifiers and
signers (Step 6).

The signature generation algorithm for the signer $ID_{i}$
$\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.Sig}{}(.)$ first
derives the private key $\mathit{sk}{}_{i}^{j}$ from the seed $\gamma_{i}$ for
given message state (counter) $M_{i}^{j}$ (Step 1). The rest of the signing is
as in $\texttt{HORS.Sig}{}(.)$, with the difference that we compute the
signatures based on $\mathit{sk}{}_{i}^{j}$, instead of randomly generating
them (Step 2-4). Finally, the signer updates state $j$ and discloses HORS
signature (Step 5).

$\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.PKConstr}{}(.)$
algorithm enables any verifier to generate the one-time public key $j$ under
FHE encryption associated with a valid $ID_{i}\in\overrightarrow{ID}$ without
any interaction with the signer or having to access private keys
($\mathit{msk}{},\mathit{sk}{}^{\prime}$). It first derives $ID_{i}$’s initial
seed $\gamma_{i}$ under FHE encryption that is preserved in $c\gamma_{i}$
(Step 1). It then pinpoints the private key $\mathit{sk}{}_{i}^{j}$ of state
$j$, which is sealed under $\mathit{csk}{}_{i}^{j}$ (Step 2). Note that the
signer used $\mathit{sk}{}_{i}^{j}$ to derive HORS signature components for
$M_{i}^{j}$. Finally, it generates the FHE encryption of HORS one-time public
key for the state $j$ by evaluating $f(.)$ and PRF under encryption (Step
4-5).

The signature verification function $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Ver}{}(.)$ is as in $\texttt{HORS.Ver}{}(.)$ except
that public keys are first constructed via $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ and the comparison is performed under
encryption. Technically, the verifier performs $f(.)$ on the received
signatures and then, computes the FHE encryption of $f(.)$’s outputs.
Subsequently, by evaluating the comparison function $\texttt{CMP}{}(.)$ under
encryption (with FHE.Eval), the signature can be verified. As described in
more detail in Section IV-B, the verifier can perform public key construction
offline before receiving the message-signature pair. Also to minimize the
storage overhead on the verifier’s end, as an alternative variant of the
algorithm, she can furnish the integers acquired in Step 2 to
$\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ and
subsequently obtain only the specific set of $k$ public keys, instead of the
entire set of $t$ public keys.

###  IV-B $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ Instantiations and
Optimizations

The generic $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ in Algorithm 1 can
be instantiated with any FHE, PRF and $f(.)$ as OWF. However, these
instantiation choices make a drastic impact on performance, security, and
practicality. In the following, we articulate our instantiation rationale and
their potential optimizations.

BGV Cryptosystem as the FHE Instantiation: We instantiated our FHE with BGV
cryptosystem [27] for the following reasons: (i) BGV is considered as a
benchmark for FHE instantiations. It is well-studied and implemented in
different libraries like HElib. (ii) We employ the Ring-Learning With Error
(R-LWE) based BGV that offers an ideal security-efficiency trade-off. (iii)
BGV is amenable to parallelism and supports CRT-based encoding techniques to
allow entry-wise arithmetic.

Performance Hurdles of Traditional Cryptographic Hash Functions in FHE
Settings: Presuming it takes hundreds of clock cycles for a modern processor
to handle a single block cipher encryption, it takes millions of clock cycles
to complete the same task under FHE. Since $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ requires FHE evaluations, we require
FHE-friendly cryptographic primitives that suit the needs of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.

The hash-based signatures usually rely on traditional hash functions $H$ to
realize both the message compression and one-way function $f(.)$. However, it
was shown that ARX-based primitives like SHA-256 and BLAKE are not suitable
for FHE evaluations. For instance, SHA-256 requires $3311$ FHE levels, which
is infeasible for many practical purposes [30].

Mitigating Encrypted Evaluation Hurdles via Davies-Meyer as OWF: We made a key
observation that $f(.)$ needs only OWF property but not a full cryptographic
hash function. This permits us to consider alternative hash designs that rely
on symmetric ciphers that are suitable for FHE evaluations.

The symmetric ciphers generally have lower multiplicative complexity (depth
and size) compared to the traditional cryptographic hash functions, with
cheaper linear operations favoring more efficient FHE evaluations. Moreover,
when evaluated under encryption, they can serve as OWF with proper
instantiations. We have investigated various options and identified that a
block cipher-based hash function named, Davies-Meyer (DM) [29], satisfies our
efficiency and OWF prerequisites for the encrypted evaluation purposes.
Compared to other constructions, DM structure is lighter than one-way double-
block-length compression methods (e.g. Hirose [31]), and allows for key-setup
and encryption parallelization as opposed to other single-block-length one-way
compression functions.

Selection of Suitable Cipher for DM Instantiaton: We decided that AES is a
suitable choice for our DM instantiation: (i) It is widely deployed with
several optimized implementations. (ii) It has a low number of rounds with no
integer operations. (iii) The AES circuit has an algebraic structure that is
compliant with parallelism, packing techniques, and GPU optimizations [32].
(iv) Compared to other hash functions, the AES-based DM has a smaller and
fixed-size memory to store hash values iteratively. (v) Finally, homomorphic
evaluation of AES has been well-studied and available in the existing
libraries like HElib [33].

Optimizations: We introduce online-offline optimizations to permit efficient
signature verifications. (i) The public key construction is independent of
messages to be verified and can be executed for any $ID_{i}$ and state
information beforehand. Therefore, the verifier can run
$\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ with
batch processes offline, and use these encrypted public keys to efficiently
verify signatures online. As shown in Section V, this offers tremendous
performance gains for the online verification. (ii) Instead of generating
full-set of $t$ keys, the verifier can only construct $k$ one-time public key
components required for verification, thereby reducing the numbers of FHE
evaluations. (iii) Recall that $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ does not take any private input and
can be publicly executed by any entity. Therefore, optionally, the verifier
can offload offline execution of $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ to a resourceful entity (e.g.,
computing cloud). In exchange for a transmission delay, this approach can lift
the major burden of FHE evaluations from the verifier, while enabling the
powerful entity to employ several parallelization and GPU-acceleration
capabilities that are amenable to our $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ instantiations.

##  V Performance Analysis and Comparison

In this section, we give a detailed performance analysis of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ and compare it with its
counterparts.

###  V-A Evaluation Metrics and Experimental Setup

Evaluation Metrics: Our analysis involves evaluating $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ and its analogous counterparts with a focus on the
signer’s performance, as well as the public key sizes and the online running
time at the verifier side.

Signer: is considered to be a resource-limited device (e.g., smart-card,
RFIDs), wherein the computation, memory, and the energy usage must be
minimized. Thus, we assess the signer’s metrics in terms of the running time
and the energy usage of the signature generation, along with the key sizes.

Verifier: The signature verification is divided into two phases: (i) Offline
phase: is carried out prior to the verifier attempt to validate the signature.
Thus, it does not impact the response time. (ii) Online phase: is a crucial
part for evaluating the efficiency of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$. It includes the time required (excluding network
latency and byzantine faultiness for the sake of simplicity) to verify the
authenticity of the message.

Parameter Selection: Our system-wide parameters are
$I=(I_{\texttt{HORS}}{},I_{\texttt{FHE}}{},I_{\texttt{DM}}{})$. We choose
$I_{\texttt{HORS}{}}\leftarrow{}(k=16,t=1024)$, where SHA-256 and DM are used
as $H$ and $f(.)$ (OWF), respectively. In $I_{\texttt{DM}}{}$, we choose
AES-128 with Galois/Counter Mode (GCM) as our PRF. In $I_{\texttt{FHE}}{}$, we
set the plaintext space of mod $2$, the lattice dimension $\phi(m)=46080$,
where the $m$-th cyclotomic is $m=53261$. We utilize a packing technique that
empowers us to evaluate $120$ blocks of AES at once. We set $N=2^{20}$ as the
number of signers.

Hardware Configuration: We tested $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ on both commodity hardware and two selected embedded
devices.

$\bullet$ Commodity Hardware: is a resourceful desktop equipped with an Intel
<EMAIL_ADDRESS>processor and 64GB of RAM.

$\bullet$ Embedded devices: We choose two well-known embedded devices to test
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ on low-end IoT: (i) Raspberry
Pi 4.0: a single-board computer equipped with ARM Cortex-A72 quad-core running
at 1.5GHz processor and 4GB of RAM. (ii) AVR ATMega2560: a microcontroller
equipped with 256KB flash memory, 8KB EEPROM, with 16MHz as clock frequency.

Software Configuration: For the commodity hardware, we used the following
libraries (i) OpenSSL111https://github.com/openssl/openssl to implement
SHA-256 (ii) HElib222https://github.com/homenc/HElib to implement FHE
functionalities (e.g., evaluation and comparison under
encryption333https://github.com/iliailia/comparison-circuit-over-
fq/tree/master). (iii) liboqs444https://github.com/open-quantum-safe/liboqs
for PQC-based operations. DM is implemented using the hardware-optimized AES-
NI [34]. As for the 8-bit AVR device, we used the Rweather Arduino
library555https://github.com/rweather/arduinolibs to implement the basic
cryptographic operations. The second embedded device supports most of the
cryptographic libraries as in commodity hardware.

###  V-B Performance Evaluation and Comparison

TABLE I: Performance comparison of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ and its counterparts at the signer side on embedded
devices

| Scheme
---
Signing ($\boldmath{ms}$) |  | Secret
---
| Signature
---
| Post-Quantum
---
| Sampling
---
| Ease of
---
| 8-bit AVR ATMega2560 | 64-bit ARM Cortex-A72 | Key (KB) | Size (KB) | Promise | Operations | Implementation
ECDSA [6] | $5,080$ | $11,540$ | $0.063$ | $0.063$ | $\times$ | $\times$ | $\times$
Ed25519 [7] | $2,120$ | $255$ | $0.063$ | $0.063$ | $\times$ | $\times$ | $\times$
Dilithium-II [19] | $-$ | $3,912$ | $2.288$ | $2.363$ | $\checkmark$ | $\checkmark$ | $\times$
Falcon-512 [20] | $-$ | $20,563$ | $1.29$ | $0.65$ | $\checkmark$ | $\checkmark$ | $\times$
SPHINCS+ [17] | $-$ | $716,379$ | $0.125$ | $32.625$ | $\checkmark$ | $\times$ | $\times$
BLISS-I [22] | $660$ | $-$ | $2$ | $5.6$ | $\checkmark$ | $\checkmark$ | $\times$
INF-HORS | $\bm{120}$ | $\bm{13}$ | $\bm{0.016}$ | $\bm{0.25}$ | $\checkmark$ | $\times$ | $\checkmark$

  * •

The private key and signature sizes are in KB. We selected our counterparts to
cover the existent state-of-the-art signature schemes from classical EC-based
(e.g., ECDSA) to post-quantum (e.g., BLISS) that have an open-source
implementation on the selected devices. The symbol $-$ indicates that we were
unable to find an open-source implementation for both the scheme and embedded
device in question. The post-quantum counterparts have different types of
sampling (i.e., BLISS-I: Gaussian sampling, Dilithium-II: rejection sampling).

TABLE II: Performance comparison of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ and its counterparts on commodity hardware

| Scheme
---
| Signing
---
| Private
---
| Signature
---
| Verification
---
| Verifier Storage
---
| Post-Quantum
---
| Sampling
---
| Time ($\mu s$) | Key | Size | Time ($\mu s$) | Pub Key | Cert. |  | Tot. ($2^{20}$ users) (GB)
---
Promise | Operations
ECDSA [6] | 193.79 | $0.063$ | $0.063$ | $166.42$ | $0.094$ | $0.063$ | $0.156$ | $\times$ | $\times$
Ed25519 [7] | 29.46 | $0.063$ | $0.063$ | $79.44$ | $0.094$ | $0.063$ | $0.156$ | $\times$ | $\times$
BLISS-I [22] | $253.34$ | $2$ | $5.6$ | $24.68$ | $7$ | $5.6$ | $12.6$ | $\checkmark$ | $\checkmark$
Dilithium-II [19] | $50.29$ | $2.288$ | $2.363$ | $18.79$ | $1.281$ | $2.363$ | $3.745$ | $\checkmark$ | $\checkmark$
Falcon-512 [20] | $214.08$ | $1.290$ | $0.65$ | $19.31$ | $0.876$ | $0.65$ | $1.526$ | $\checkmark$ | $\checkmark$
SPHINCS+ [17] | $4,258.69$ | $0.125$ | $32.625$ | $241.2$ | $0.063$ | $32.625$ | $32.688$ | $\checkmark$ | $\times$
$\text{XMSS}^{\text{MT}}{}$[35] | $5,330.81$ | $3.109$ | $2.609$ | $968.54$ | $0.75$ | $2.609$ | $3.359$ | $\checkmark$ | $\times$
INF-HORS | $\bm{4.81}$ | $\bm{0.016}$ | $\bm{0.25}$ |  | Ver
---
(Online)
| PKConstr
---
(Offline)
$\bm{9.42}$ MB | $\checkmark$ | $\times$
$\bm{1.913~{}s}$ | $\bm{41.22~{}s}$

  * •

The private/public key, signature, and certificate sizes are in KB.
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ and NIST PQC candidates use
architecture-specific optimizations (i.e., AESNI, AVX2 instructions). Only
$\text{XMSS}^{\text{MT}}{}$ have forward security. For it, we choose
SHA20$/2\\_256$. For SPHINCS+, we set $n=256,h=63,d=9,b=12,k=29,w=16$. The
total verifier storage denotes the storage required to verify ($J=2^{30}$)
signatures for ($N=2^{20}$) signers.

Figure 1: Signing energy consumption of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ and its counterparts

####  V-B1 Signer

We present the computational, storage, and transmission overhead on both an
embedded device and commodity hardware in Tables I and II, respectively.

Table II demonstrates that among our counterparts (i.e., conventional-secure
and post-quantum), $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ has the
fastest signing time and the lowest signer storage overhead. For instance,
compared to its PQ counterparts, $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ is $10\times$ and $43\times$ faster than Dilithium-II
and Falcon-512, respectively. Additionally, it has a compact signature that is
$9.5\times$ and $2.6\times$ smaller than that of Dilithium-II and Falcon-512,
respectively. $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is also
significantly faster than other hash-based signature alternatives (e.g.,
$\text{XMSS}^{\text{MT}}{}$, SPHINCS+) and BLISS-I with much smaller signature
sizes. Moreover, $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ has the
smallest private key size among all of its alternatives. Further remark that,
despite being PQ-secure, $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is
also $1.5\times$ faster with a smaller private key size than the most
efficient conventional-secure (ECC-based SchnorrQ) alternative. The signer
computational performance advantages of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ become even more apparent on embedded devices. As
discussed in Section I (see Table I), $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ offers $301\times$ and $1581\times$ faster signing
than Dilithium-II and Falcon, respectively, on an embedded device with ARM
Cortex-A72.

The high signer computational efficiency translates into better energy
awareness on resource-limited devices. To showcase the potential of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$, we profiled the energy
efficiency of the signature generation versus sensor data sampling using
pulse666https://pulsesensor.com/ and pressure777https://cdn-
shop.adafruit.com/datasheets/1900_BMP183.pdf sensors (10 Hz for sampling
frequency and 1ms for reading time). On our 8-bit microcontroller (i.e., AVR
ATMega2560), Figure 1 compares the energy consumption of one signing to the
sampling of pulse and pressure sensors.

We remind that, to the best of our knowledge, none of the selected NIST PQC
signatures have an open-source implementation available on such resource-
limited devices (i.e., 8-bit microcontroller). The most prominent PQ
alternatives with a reported performance on this platform are BLISS-I. We also
included the most efficient ECC-based alternatives in our energy comparison to
assess $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ performance with
respect to (pre-quantum) conventional schemes. $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ signature generation consumes $26\times$ less energy
than the pulse sensor. We note that BLISS-I is vulnerable to side-channel
attacks, which hinders its use in practice. The side-channel attack resiliency
and ease of implementation are important factors for the practical deployments
of signature schemes on embedded devices. Lattice-based signatures require
various types of sampling operations (e.g., Gaussian, rejection samplings)
that make them vulnerable to side-channel attacks [21]. Moreover, due to their
complexity, they are notoriously difficult to implement on such platforms. As
an example, Falcon needs 53 bits of precision to implement without emulation
[36], which hinders its deployment on 8-bit microcontrollers.

$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ signature generation requires
only a few PRF calls. Hence, it is free from the aforementioned specialized
side-channel and timing attacks that target sampling operations. Moreover, it
is easy to implement, since it only requires a suitable symmetric cipher
(e.g., AES) and a cryptographic hash function (e.g., SHA256) with a minimal
code size.

Our analysis validates that $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is
the most suitable alternative among its counterparts to be deployed for
signature generation on IoT applications due to its high computational
efficiency, compact key/signature sizes, and high security.

####  V-B2 Verifier

While $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is a signer-optimal
scheme, we also introduced strategies to minimize the verifier
computational/storage overhead. As explained in Section IV-B, the verifiers
can generate public keys in offline mode (before signature verification),
thereby improving the efficiency of online verification. Moreover, the
verifiers have an option to outsource offline public key construction to a
resourceful entity.

Online Verification: The online verification cost is comprised of
$k\times\texttt{PRF}{}(.)$, $k\times\texttt{FHE.Enc}{}(.)$, and
$k\times\texttt{FHE.Eval}{}(.)$ of the comparison circuit. According to our
implementation parameters, this is estimated to be approximately $1.913$
seconds. Also, for further cost reduction, we strongly recommend an offline
generation of public keys whenever possible.

Offline Public Key Construction: The main computational bottleneck of
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is the offline phase. In our
tests, the average cost of a single homomorphic AES evaluation per block is
$2.29$ seconds. Hence, the overall cost of generating $k$ public key
components is $41.22$ seconds. We note that the offline computational overhead
can be significantly reduced with parallelizations. For example, since each
component of HORS public key can be generated independently, they can be
assigned to different threads or computing units. Moreover, as discussed in
Section IV-B, encrypted AES evaluations via BGV are highly parallelizable,
which is one of our reasons to opt for AES as our DM building block.

Verifier Storage Overhead: The total size of the master public key
$\mathit{PK}$ with the expansion per block evaluation is around $9.42$ MB. If
only single signer is considered, the size of $\mathit{PK}$ is much larger
than that of its counterparts. However, $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ enables a verifier to construct public keys for any
valid signer $ID_{i}$ of any state. This unique property permits
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ to achieve compact storage for
a large number of signers since the verifier does not need to store a
certificate for their public keys. For example, the total storage (public key
plus certificate) for $2^{20}$ users is still 9.42 MB for
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$, while it is around 1.52 GB
and 3.74 GB for Falcon-512 and Dilithium-II, respectively. The total storage
advantage increases with a growing number of signers.

##  VI Security Analysis

We prove that $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is EU-CMA secure
as follows.

###### Theorem 1

$\mathit{Adv}_{\mathit{\texttt{INF}\mathchar
45\relax\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t,q_{s})\leq
q_{s}\cdot\mathit{Adv}_{\mathit{\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t^{\prime},q^{\prime}_{s})$, where $q’_{s}=q_{s}+1$
and
$\mathcal{O}(t’)=\mathcal{O}(t)+q_{s}\cdot(k\cdot\texttt{PRF}{}+(t+2)\cdot\texttt{FHE.Eval}{}(\texttt{PRF}{}))$
(we omit terms negligible in terms of $\kappa$).

Proof: Let $\mathcal{A}$ be the $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ attacker. We construct a simulator $\mathcal{F}$ that
uses $\mathcal{A}$ as a subroutine to break one-time EU-CMA secure HORS, where
$(\overline{\mathit{sk}{}},\overline{\mathit{PK}{}},I_{\texttt{HORS}{}})\leftarrow{}\texttt{HORS.Kg}{}(1^{\kappa})$
(Definition 1). $\mathcal{F}$ is given the challenge
$\overline{\mathit{PK}{}}$, on which $\mathcal{A}$ aims to produce a forgery.
$\mathcal{F}$ has access to HORS signing oracle under secret key
$\overline{\mathit{sk}{}}$. $\mathcal{F}$ maintains two lists $\mathcal{LS}$
and $\mathcal{LK}$ to record $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Sig}{}(.)$ and $\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(.)$ queries and simulation/setup outputs.
$\mathcal{F}$ randomly chooses a target forgery index $w\in[1,q_{s}]$.
$\mathcal{A}$ uses identifier $ID_{i}\in\overrightarrow{ID}$.

Algorithm $\mathcal{F}$ ($\overline{\mathit{PK}{}},I_{\texttt{HORS}{}}$)

$\bullet$ Setup: $\mathcal{F}$ is run as in Definition 5:

(1)
$\mathit{msk}{}\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\\{0,1\\}^{\kappa}$.

(2) $I\leftarrow{}(I_{\texttt{HORS}}{},I_{\texttt{FHE}}{},I_{\texttt{DM}}{})$,
where $(I_{\texttt{FHE}}{},I_{\texttt{DM}}{})$ are as in Definition 2-3,
respectively.

(3)
$(\mathit{sk}{}^{\prime},\mathit{PK}{}^{\prime},I_{\texttt{FHE}{}})\leftarrow{}\texttt{FHE.Kg}{}(1^{\kappa})$.

(4)
$\mathit{MPK}{}\leftarrow{}\texttt{FHE.Enc}{}(\mathit{PK}{}^{\prime},\mathit{msk}{})$
and $PK=(\mathit{PK}{}^{\prime},\mathit{MPK}{})$.

(5) $\mathit{sk}{}_{i}^{0}\leftarrow{}\texttt{PRF}{}(\mathit{msk}{},ID_{i})$.

(6)
$sk=\\{\mathit{sk}{}_{i}^{j}\leftarrow{}\texttt{PRF}{}(\mathit{sk}{}_{i}^{0},j)\\}_{j=1,j\neq
w}^{q_{s}}$.

(7) $\\{cv_{i}^{j}\leftarrow{}\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.PKConstr}{}(\mathit{PK}{},ID_{i},j)\\}_{j=1,j\neq
w}^{q_{s}}$.

Execute $\mathcal{A}^{\texttt{INF}\mathchar
45\relax\texttt{HORS}{}_{\mathit{sk}{}}(\cdot)}(\mathit{PK}{})$:

$\bullet$ Queries: $\mathcal{F}$ handles $\mathcal{A}$ ’s queries as follows:

(1) $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}_{\mathit{sk}{}}(.)$:
$\mathcal{F}$ returns
$\sigma_{w}\leftarrow{}\texttt{HORS.Sig}{}(M_{w},\overline{\mathit{sk}{}})$ by
querying HORS signing oracle, if $j=w$. Otherwise, $\mathcal{F}$ runs
$\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.Sig}{}(.)$ algorithm
steps 2-5 to compute $\sigma_{j}$ via $\mathit{sk}{}_{i}^{j}$.

(2) $\texttt{$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$.PKConstr}{}(.)$
Queries: If $j=w$ then $\mathcal{F}$ returns
$cv_{i}^{w}=\texttt{FHE.Enc}{}(PK^{\prime},\overline{\mathit{PK}{}}$). E;se,
$\mathcal{F}$ returns $cv_{i}^{j}$.

$\bullet$ Forgery of $\mathcal{A}$ : $\mathcal{A}$ produces a forgery
$(M^{*},\sigma^{*})$ on $\mathit{PK}{}$. $\mathcal{A}$ wins the
$\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$ experiment if
$\texttt{$\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$.Ver}{}(\mathit{PK}{},M^{*},\sigma^{*})==1$ and
$M^{*}\notin\mathcal{LS}{}$ conditions hold, and returns 1, else returns $0$.

$\bullet$ Forgery of $\mathcal{F}$ : If $\mathcal{A}$ fails to win the
$\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$ experiment for
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$, $\mathcal{F}$ also fails to
win the $\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$ experiment for HORS. As
a result, $\mathcal{F}$ aborts and returns $0$. Otherwise, $\mathcal{F}$
checks if $\texttt{HORS.Ver}{}(\overline{PK},M^{*},\sigma^{*})==1$ and $M^{*}$
was not queried to the HORS signing oracle. If these conditions hold,
$\mathcal{F}$ wins the $\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$
experiment against HORS and returns 1. Otherwise, $\mathcal{F}$ aborts and
returns $0$.

$\bullet$ Success Probability Analysis: We analyze the events that are needed
for $\mathcal{F}$ to win the $\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$
experiment as follows:

(1) $\mathcal{F}$ does not abort during $\mathcal{A}$ ’s queries with
$Pr[\overline{Abort1}]$: $\mathcal{F}$ can answer all of $\mathcal{A}$ ’s
signature queries, since it knows all private keys except $j=w$, for which it
can retrieve the answer from HORS signature oracle. $\mathcal{F}$ sets
$\mathit{PK}{}_{i}^{w}=\texttt{FHE.Enc}{}(PK^{\prime},\overline{PK})$ and can
answer all other queries by running the public key construction algorithm. The
only exception occurs if $\texttt{FHE.Eval}{}(.)$ produces an incorrect
$\mathit{PK}{}_{i}^{j}$ during the simulation, which occurs with a negligible
probability in terms of $\kappa$ due to the correctness property of FHE.
Therefore, we conclude $Pr[\overline{Abort1}]\approx 1$.

(2) $\mathcal{A}$ produces a valid forgery with $Pr[Forge|\overline{Abort1}]$:
If $\mathcal{F}$ does not abort during the queries, then $\mathcal{A}$ also
does not abort, since its simulated view is computationally indistinguishable
from the real view (see indistinguishability argument below). Hence, the
probability that $\mathcal{A}$ produces a forgery against
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is
$Pr[Forge|\overline{Abort1}]=\mathit{Adv}_{\mathit{\texttt{INF}\mathchar
45\relax\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(q_{s},t)$. There are three events that may also lead
to $\mathcal{A}$ ’s forgery: (i) $\mathcal{A}$ breaks the subset-resiliency of
$H$, whose probability is negligible in terms of $\kappa$ [18]. (ii)
$\mathcal{A}$ breaks IND-CPA secure FHE and recovers the master secret key
$\mathit{msk}$, which permits a universal forgery. The probability that this
happens is negligible in terms of $\kappa$ for sufficiently large security
parameters [27]. (iii) $\mathcal{A}$ breaks the evaluation of the comparison
circuit for all $k$ signatures (i.e., $b_{\ell}^{j}=1,\forall\ell\in[1,k]$),
which occurs with a probability that is $\frac{1}{k}\times$ negligible in
relation to $\kappa$. (iv) $\mathcal{A}$ inverts DM by breaking the underlying
IND-CPA cipher, which also happens with negligible probability in terms of
$\kappa$ [29]. Therefore, they are omitted in the theorem statement.

(3) $\mathcal{F}$ does not abort after $\mathcal{A}$ ’s forgery with
$Pr[\overline{Abort2}|\overline{Abort1}\wedge Forge]$: $\mathcal{F}$ does not
abort if $\mathcal{A}$ ’s forgery is on the target public key $PK_{i}^{w}$.
Since $w$ is randomly selected from $[1,q_{s}]$, this occurs with $1/q_{s}$.

(4) $\mathcal{F}$ wins the $\texttt{EU}\mathchar 45\relax\texttt{CMA}{}$
experiment with $\mathit{Adv}_{\mathit{\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t^{\prime},q^{\prime}_{s})$:

$Pr[Win]=Pr[\overline{Abort1}]$ $\cdot Pr[Forge|\overline{Abort1}]\cdot
Pr[\overline{Abort2}$ $|\overline{Abort1}\wedge Forge]$. Therefore, $Pr[Win]$
is bounded as:

$\displaystyle\mathit{Adv}_{\mathit{\texttt{INF}\mathchar
45\relax\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t,q_{s})$ $\displaystyle\leq$ $\displaystyle
q_{s}\cdot\mathit{Adv}_{\mathit{\texttt{HORS}{}}}^{\texttt{EU}\mathchar
45\relax\texttt{CMA}{}}{}(t^{\prime},q^{\prime}_{s})$

##  VII Conclusion

In this work, we proposed a novel lightweight post-quantum signature called
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ that offers magnitudes of time
faster signing than recently selected NIST PQC standards with much smaller key
sizes and compact signatures. $\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$
achieves these significant performance advantages thanks to its innovative
algorithmic design, which transforms one-time HORS signature into
(polynomially) unbounded times via encrypted function evaluations at the
verifier. This approach lifts the one-time public key management burden from
the resource-limited signer while permitting verifiers to non-interactively
extract one-time public keys without assuming any additional entity. We
introduce an online-offline process and optional outsourcing capability to
enhance the verification performance. We formally prove that
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ is EU-CMA secure. We provided
an extensive performance analysis and comparison of $\texttt{INF}\mathchar
45\relax\texttt{HORS}{}$ with the state-of-the-art on both the commodity
hardware and embedded IoT devices. Overall, all these properties make
$\texttt{INF}\mathchar 45\relax\texttt{HORS}{}$ an ideal alternative to
provide lightweight post-quantum authentication for IoT applications.

## References

  * [1] D. C. Nguyen, M. Ding, P. N. Pathirana, A. Seneviratne, J. Li, D. Niyato, O. Dobre, and H. V. Poor, “6G internet of things: A comprehensive survey,” IEEE Internet of Things Journal, 2021.
  * [2] A. Ahad, M. Tahir, M. Aman Sheikh, K. I. Ahmed, A. Mughees, and A. Numani, “Technologies trend towards 5G network for smart health-care using iot: A review,” Sensors, vol. 20, no. 14, p. 4047, 2020.
  * [3] Y.-H. Joung, “Development of implantable medical devices: from an engineering perspective,” International neurourology journal, vol. 17, no. 3, p. 98, 2013.
  * [4] R. Behnia and A. A. Yavuz, “Towards practical post-quantum signatures for resource-limited internet of things,” in Annual Computer Security Applications Conference, pp. 119–130, 2021.
  * [5] J. Katz and Y. Lindell, Introduction to modern cryptography.  CRC press, 2020.
  * [6] D. Johnson, A. Menezes, and S. Vanstone, “The elliptic curve digital signature algorithm (ECDSA),” International journal of information security, vol. 1, no. 1, pp. 36–63, 2001.
  * [7] D. J. Bernstein, N. Duif, T. Lange, P. Schwabe, and B.-Y. Yang, “High-speed high-security signatures,” Journal of cryptographic engineering, vol. 2, no. 2, pp. 77–89, 2012.
  * [8] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM review, vol. 41, no. 2, pp. 303–332, 1999.
  * [9] NIST, “PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates.” https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4.
  * [10] S. Li, H. Song, and M. Iqbal, “Privacy and security for resource-constrained iot devices and networks: research challenges and opportunities,” Sensors, vol. 19, no. 8, p. 1935, 2019.
  * [11] A. A. Yavuz and M. O. Ozmen, “Ultra lightweight multiple-time digital signature for the internet of things devices,” IEEE Transactions on Services Computing, no. 1, pp. 215–227, 2019.
  * [12] S. E. Nouma and A. A. Yavuz, “Practical cryptographic forensic tools for lightweight internet of things and cold storage systems,” in Proceedings of the 8th ACM/IEEE Conference on Internet of Things Design and Implementation, pp. 340–353, 2023.
  * [13] G. K. Verma, B. Singh, N. Kumar, and V. Chamola, “Cb-cas: Certificate-based efficient signature scheme with compact aggregation for industrial internet of things environment,” IEEE Internet of Things Journal, vol. 7, no. 4, pp. 2563–2572, 2019.
  * [14] X. Chen, D. He, M. K. Khan, M. Luo, and C. Peng, “A secure certificateless signcryption scheme without pairing for internet of medical things,” IEEE Internet of Things Journal, vol. 10, pp. 9136–9147, 2022.
  * [15] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” J. Cryptol., vol. 17, p. 297–319, sep 2004.
  * [16] B. Glas, J. Guajardo, H. Hacioglu, M. Ihle, K. Wehefritz, and A. A. Yavuz, “Signal-based automotive communication security and its interplay with safety requirements.” ESCAR, Embedded Security in Cars Conference, Germany, November 2012, November 2012.
  * [17] D. J. Bernstein, A. Hülsing, S. Kölbl, R. Niederhagen, J. Rijneveld, and P. Schwabe, “The SPHINCS+ signature framework,” in Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pp. 2129–2146, 2019.
  * [18] L. Reyzin and N. Reyzin, “Better than BiBa: Short one-time signatures with fast signing and verifying,” in Australasian Conference on Information Security and Privacy, pp. 144–153, 2002.
  * [19] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, “Crystals-dilithium: A lattice-based digital signature scheme,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 238–268, 2018.
  * [20] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “Falcon: Fast-fourier lattice-based compact signatures over NTRU,” Submission to the NIST’s post-quantum cryptography standardization process, 2018.
  * [21] E. Karabulut and A. Aysu, “Falcon down: Breaking falcon post-quantum signature scheme through side-channel attacks,” in 2021 58th ACM/IEEE Design Automation Conference (DAC), pp. 691–696, 2021.
  * [22] L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, “Lattice signatures and bimodal gaussians,” in Cryptology Conf., pp. 40–56, 2013.
  * [23] K.-A. Shim, C.-M. Park, N. Koo, and H. Seo, “A high-speed public-key signature scheme for 8-b iot-constrained devices,” IEEE Internet of Things Journal, vol. 7, no. 4, pp. 3663–3677, 2020.
  * [24] S. Darzi, K. Ahmadi, S. Aghapour, A. A. Yavuz, and M. M. Kermani, “Envisioning the future of cyber security in post-quantum era: A survey on pq standardization, applications, challenges and opportunities,” arXiv preprint arXiv:2310.12037, 2023.
  * [25] S. E. Nouma, , and A. A. Yavuz, “Post-quantum forward-secure signatures with hardware-support for internet of things,” IEEE International Conference on Communications (ICC), p. 1–7, IEEE, 2023.
  * [26] F. Armknecht, C. Boyd, C. Carr, K. Gjøsteen, A. Jäschke, and Reuter, “A guide to fully homomorphic encryption,” Cryptology Archive, 2015.
  * [27] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, pp. 1–36, 2014.
  * [28] Y. Yu and X. Xie, “Privacy-preserving computation in the post-quantum era,” National Science Review, vol. 8, 07 2021.  nwab115.
  * [29] B. Preneel, “Davies-meyer hash function,” in Encyclopedia of Cryptography and Security, pp. 136–136, 2005.
  * [30] S. Mella and R. Susella, “On the homomorphic computation of symmetric cryptographic primitives,” in Proceedings of the 14th IMA International Conference on Cryptography and Coding - Volume 8308, IMACC 2013, (Berlin, Heidelberg), p. 28–44, Springer-Verlag, 2013.
  * [31] S. Hirose, “Some plausible constructions of double-block-length hash functions,” in Fast Software Encryption, (Berlin, Heidelberg), pp. 210–225, Springer Berlin Heidelberg, 2006.
  * [32] C. Gentry, S. Halevi, and N. P. Smart, “Homomorphic evaluation of the aes circuit,” in Advances in Cryptology – CRYPTO 2012 (R. Safavi-Naini and R. Canetti, eds.), pp. 850–867, 2012.
  * [33] S. Halevi and V. Shoup, “Design and implementation of HElib: a homomorphic encryption library,” Cryptology Archive, 2020.
  * [34] G. Hofemeier and R. Chesebrough, “Introduction to intel aes-ni and intel secure key instructions,” Intel, White Paper, vol. 62, 2012.
  * [35] A. Hülsing, L. Rausch, and J. Buchmann, “Optimal parameters for XMSS^ MT,” Cryptology ePrint Archive, Paper 2017/966, 2017.
  * [36] J. Howe and B. Westerbaan, “Benchmarking and Analysing the NIST PQC Finalist Lattice-Based Signature Schemes on the ARM Cortex M7, Paper 2022/405,” Cryptology ePrint Archive, 2022.