# QR TPM in Programmable Low-Power Devices

Luís Fiolhais and Leonel Sousa<EMAIL_ADDRESS><EMAIL_ADDRESS>1234-5678-9012 INESC-ID, Instituto Superior Técnico,
Universidade de LisboaRua Alves Redol, 9LisboaPortugal1000-029

(2018)

###### Abstract.

Trusted Platform Modules (TPMs), which serve as the root of trust in secure
systems, are secure crypto-processors that carry out cryptographic primitives.
Should large-scale quantum computing become a reality, the cryptographic
primitives adopted in the TPM 2.0 standard will no longer be secure. Thus, the
design of TPMs that provide Quantum Resistant (QR) primitives is of utmost
importance, in particular with the restrictions imposed by embedded systems.
In this paper, we investigate the deployment of QR primitives and protocols in
the standard TPM 2.0. Cryptographic algorithms that are already in the NIST QR
cryptography standardization process, as well as an Oblivious Transfer (OT), a
fundamental cryptographic primitive, are the QR cryptographic schemes selected
to extend TPM 2.0. In particular, the Kyber algorithm for key encapsulation,
the Dilithium algorithm for digital signature, and a 3-round Random Oblivious
Transfer (ROT) protocol, supporting protocols such as Multi-Party Computation
and Private Set Intersection (PSI). The QR extended TPM 2.0 is implemented in
ARM and RISC-V embedded processors, its computational requirements are
analysed and experimentally evaluated in comparison to the standard TPM. It is
shown that Kyber and Dilithium are faster at creating keys than RSA, due to
the key size and secure random sampling required in RSA, while they meet the
same performance level as ECC. For digital signatures, both in signature
creation and verification, Dilithium is on par with RSA and ECC. The ROT
protocol shows decent performance and its support required small modifications
to the TPM. This paper also shows that it would be possible to backport the
required code to already available TPMs to ensure that current TPMs remain
secure against quantum adversaries.

Trusted Platform Module, Cryptography Quantum-Resistant, Embedded Systems

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX

##  1\. Introduction

The Trusted Platform Module (TPM) provides hardware-based support to assure
the security of computers and embedded devices. TPM provides various security
functions, such as encryption, secure key storage, and authentication, to
ensure the integrity of a system and protect sensitive information.
Fundamental functions and features of TPM are: secure boot; authentication of
themselves to other devices, by storing cryptographic keys and certificates
securely; data encryption, to perform encryption and decryption operations
securely; and remote attestation, for remote verification and attestation.

The current TPM standard relies on number-theoretic cryptography (Group, [n.
d.]). However, should quantum computers become available, these types of
cryptographic primitives, such as Rivest-Shamir-Adleman (RSA) and Elliptic
Curve Cryptography (ECC), will no longer be secure (Shor, 1997). Thus, the
National Institute of Standards and Technology (NIST) initiated, a few years
ago, a process to solicit, evaluate, and standardize quantum-resistant (QR)
public-key cryptographic algorithms (Team, 2022).

The NIST has already identified four candidate QR cryptographic algorithms for
standardization. Among these, the two primary algorithms, members of the
Cryptographic Suite for Algebraic Lattices (CRYSTALS), are the CRYSTALS-Kyber
(Bos et al., 2018) for providing key encapsulation mechanisms, and the
CRYSTALS-Dilithium (Ducas et al., 2019) for digital signatures. These
algorithms are based on the Module Ring Learning With Errors (MLWE) problem
and the Ring Learning With Errors (RLWE) problem. It is conjectured that these
problems are hard for both classical and quantum computers (Lyubashevsky et
al., 2010). Supported also on the RLWE problem, Oblivious Transfer (OT) and
Random Oblivious Transfer (ROT) primitives have been proposed (Branco et al.,
2021). These primitives are important for supporting protocols such as Multi-
Party Computation and Private Set Intersection (PSI), which are used in
applications like contact discovery, remote diagnosis, and contact tracing.

Although components complying with the TPM 2.0 standard are stable and widely
available, QR primitives have to be introduced in it for extending the actual
capabilities and assure the security of a computing platform. Recently,
research projects, such as the FutureTPM (Fiolhais et al., 2020), have
advanced in this topic, and non-Quantum Resistant TPMs have been extended
through software emulation (Fiolhais et al., 2020). It was concluded that
Kyber and Dilithium can efficiently replace most of the functionality provided
by ECC and RSA. However, there are others, such as the OT protocol, that have
not still been evaluated in the scope of the current TPM. Moreover, now that
QR cryptographic primitives are already in the standardization phase, hardware
has to be developed for TPM to keep pace with QR cryptography.

The change of paradigm to QR raises a new set of challenges, in particular on
embedded devices, including ones related to performance and memory
requirements, but also related to side-channel security. In this paper, we
analyse the computational requirements of an updated QR TPM based on low-end
range processors. To experimentally validate and evaluate a QR TPM, we have
chosen an in-order double-issue RISC-V U74 processor and the in-order double-
issue ARM Cortex-A7. The adoption of programmable processors is the right
choice in this first stage of development, not only allowing adjustments and
parametrization during the standardization phase but also assessing methods to
face the challenges of side-channel attacks. As far as we know, this is the
first time this type of research, with significant practical interest, is
performed, being a step forward for launching secure and efficient QR TPM
devices in the near future. Moreover, our approach demonstrates that it would
be possible to backport the required code to already available TPMs in order
to ensure that old TPMs remain secure against quantum adversaries.

The organization of the paper is as follows. In Section 2 we provide the
background information required to understand the material in this paper and
briefly discuss the state-of-the-art. Section 3 analyses the memory and
computational requirements of the Kyber, Dilithium, and the ROT algorithms.
The experimental results presented in Section 5 were obtained by implementing
the algorithms and protocol on ARM and RISC-V based embedded systems. Section
6 draws the conclusions.

##  2\. Background and State of the Art

The main objective of this paper is to analyse the computational requirements
of QR TPMs, and to experimentally evaluate in practice the feasibility of
these new types of secure TPMs by using low-end range programmable
microprocessors. In this section, we will discuss the current TPM standard and
the QR algorithms and primitives added to this standard classic TPM.

###  2.1. Trusted Platform Module

The TPM is a specialized hardware component designed to provide security-
related functions for computing systems The standard TPM 2.0 library, from the
Trusted Computing Group (TCG) (Group, 2016), builds upon the foundation of TPM
1.2 with enhanced capabilities. In relation to TPM 1.2, TPM 2.0 provides
enhanced cryptography, for example, ECC and more advanced hash functions,
allows for asymmetric key encryption directly within the TPM, provides
multiple hierarchies of keys, and facilitates remote management and
configuration of the TPM. Although TPM 2.0 is designed to meet the evolving
security requirements of current computing platforms, such as laptops,
servers, embedded systems, and Internet of Things (IoT) devices, they are not
quantum resistant. With that purpose, QR cryptographic primitives and
algorithms have to be implemented in hardware and integrated into the TPM.

###  2.2. Kyber and Dilithium algorithms

Kyber (Bos et al., 2018) and Dilitium (Ducas et al., 2019) are QR
cryptographic schemes based on lattice-based cryptography, which relies on the
hardness of mathematical problems related to lattices. They have been
identified for NIST as QR cryptographic algorithms for standardization.

Both algorithms require the implementation of sampling, number theoretic
transform (NTT) to speedup arithmetic, and encode/decode functions. The Kyber
algorithm provides secure key encapsulation mechanisms, for exchanging
encryption keys between two parties. It aims to achieve a balance between
security and efficiency, having reasonable computational requirements. A
standalone hardware design of the Kyber algorithm, which computes key-
generation, encapsulation (encryption), and decapsulation (decryption and
reencryption), can be found in (Xing and Li, 2021).

The Dilithium digital signature scheme has been designed for digital signature
generation and verification, with the aim of being secure and efficient in
terms of computational and memory requirements. It allows multiple security
levels through parametrization. The Dilithium family includes different
parameter sets that offer varying levels of security and performance, which
can be chosen according to the security requirements and available resources.
An implementation of Dilithium, for a set of parameters, targeting Field
Programmable Gate Arrays (FPGAs) is proposed in (Beckwith et al., 2021).

###  2.3. ROT Protocol

Random Oblivious Transfer (ROT) is a cryptographic protocol that allows one
party (the sender) to send a set of messages to another party (the receiver),
who can then select and receive a single message from the set without
revealing which message was chosen to the sender. This protocol provides a
form of private communication where the sender remains oblivious to the choice
made by the receiver, and the receiver remains oblivious to the content of the
unchosen messages.

The concept of Oblivious Transfer (OT) was introduced in the field of
cryptography to address scenarios where one party needs to transfer
information to another party without revealing unnecessary details. ROT
extends this concept by introducing an element of randomness, making it more
suitable for certain applications. There are different variations of ROTs,
including:

  * •

1-out-of-2 ROT (1-2 ROT): In this type of ROT, the sender has two messages,
and the receiver chooses one of them without revealing the choice. This is
similar to flipping a coin where the sender does not know the outcome, and the
receiver only gets the chosen side.

  * •

k-out-of-N ROT (k-N ROT): This is a more general version where the sender has
N messages, and the receiver can choose k messages without revealing the
choices or the content of the unchosen messages.

ROT has applications in secure multiparty computation, private database
queries, and cryptographic protocols where privacy and confidentiality are
essential. It’s a fundamental building block in constructing secure protocols
that allow parties to interact without revealing sensitive information. As a
practical example consider that the TPM is being used as a secure wallet and
that the user wants to perform a payment anonymously. The usage of ROT within
the TPM would be advantageous as the contents of the secure wallet would never
have to leave the TPM when a transaction is processed, and the transfer can be
anonymous (Chiu et al., 2023). Moreover, consider the example of anonymous
remote attestation. An enterprise wants to authenticate that a laptop belongs
to its network such that it can give the laptop access to some confidential
internal documents. Once again, the TPM, which already features functionality
for attestation (Group, 2016), can be used to anonymize the attestation
procedure (Brickell et al., 2004).

###  2.4. Target Hardware: Microprocessors selection

Previous work in this topic has explored the architectural, performance, and
memory requirements of QR algorithms in a TPM (Fiolhais et al., 2020).
However, the results presented therein used a laptop-class processor, with an
out-of-order backend, to emulate the TPM hardware, thus the objective was not
to evaluate performance in a real world scenario. Even though it would be
beneficial for a TPM to have an out-of-order processor, this is not a
realistic goal. TPMs are designed for low power and low price such that they
can be used in any type of computing system. The goal of the TPM is to lower
the barrier of entry for any computing system to have strong security
guarantees. Therefore, this paper aims to perform a performance comparison
using cheaper and low-power devices. In these experiments, two low-power
processors are used: an ARM Cortex-A7 at 900 MHz and a RISC-V U74 core at 1.2
GHz. Both of these processors were selected as they fit the
power/performance/area requirements found in hardware TPMs.

The ARM Cortex-A7 is a 32-bit dual-issue in-order processor with support for
NEON instructions. It has 8 pipeline stages and can issue up to two
instructions per cycle under certain conditions. The A7 core used in the
experiments is part of the BCM2836 System-on-Chip (SoC), which features a
cluster of four A7 cores. It is unclear what cache hierarchy is being used in
the SoC (ARM, 2011).

The RISC-V U74 is a 64-bit RV64IMAFDC double-issue in-order processor with no
vector unit. It has 8 pipeline stages and can issue up to two instructions per
cycle under certain conditions. The U74 core used in the experiments is part
of the FU740 SoC, which features a cluster of four U74 cores (SiFive, 2022).
This SoC has a private 32 KiB 4-way I$ and 32 KiB 8-way D$ for each U74 core,
and a 2 MiB 16-way L2 cache shared between all cores in the cluster.

##  3\. TPM Computational Requirements

Figure 1 shows the basic architecture of the TPM. The base architecture is
composed of a cryptographic processor wherein a secure Random Number Generator
(RNG), RSA and ECC cryptographic primitives, and a hashing engine are
available; a small non-volatile memory module (64 kB) to store TPM’s state;
and a volatile memory to keep short-lived data. The TPM is both a passive and
active agent in a system. It provides security services to itself and to the
system it is embedded in. A SoC can use a TPM to enhance the security
functionality it offers. An application processor can send commands to the TPM
requesting certain operations to be completed securely. It is important to
note that the TPM only uses its resources to provide functionality to itself
or others. The TPM is independent of the system it is embedded in, both
hardware and software wise, and provides dedicated circuitry to protect
against physical attacks (Group, [n. d.]).

Figure 1. Example Number-Theoretic TPM Architecture.

Through the TPM Command Transmission Interface (TCTI) layer, a client is able
to interface with a TPM using the commands provided in the TPM Software Stack
(TSS). Physically, the TCTI layer is a bus that connects the application
processor to the TPM. This is generally achieved using SPI. Figure 2 shows a
callgraph of the chain of functions executed when a command is received. A
user will issue a command to the TPM using the TSS. Within this stack, the
user’s command will be serialized and sent to the TPM through the TCTI. The
TPM, upon receiving the command, will deserialize it and check if the caller
has sufficient privileges to execute this command. If the command passes the
check, then the TPM will execute the command and return the result of the
command back to the application processor. The TPM serializes the results and
sends them through TCTI to the application processor which will deserialize it
upon reception using the TSS. Finally, the TSS returns the result of the
command to the user.

Figure 2. Function flowgraph executed by the TPM when a valid command is
received.

TPMs can be implemented in different formats (Group, 2016). Hardware TPMs,
besides strengthening the software Trusted Computing Base (TCB) of a system
also protect against physical attacks (Group, 2016; Microsoft, 2018). Software
TPMs, as is the studied case in this paper, are used for development and
prototyping, since they have a faster implementation-debug cycle than a
hardware TPM and also do not have to wear out the non-volatile memory which
has a limited lifecycle due to the number of writes (Group, 2016). Moreover,
TPMs can also be used in virtualization scenarios where an hypervisor offers
the services of a TPM through a virtualization layer (Group, 2016; Microsoft,
2018). This can be achived through multiple Software TPMs running in the
hypervisor for each virtual machine, or the hypervisor uses a hardware TPM in
a multi-programmed manner, context switching part of the state of the TPM
between each active virtual machine.

The general implementation of a TPM features a small in-order CPU, a small on-
chip memory, and a cryptographic co-processor to accelerate cryptographic
tasks. Number-Theoretic TPMs have a co-processor that specializes in big-
number algebra due to the algebraic requirements of RSA and ECC. QR TPMs,
using the soon-to-be standardized Kyber and Dilithium algorithms, will start
moving into co-processors that specialize in lattice-based algebra. Lattice
operations are over a polynomial ring with $n$ dimensions modulus a $q$,
wherein $q$ is a prime number. Algebraic operations over the ring require
adding, subtracting, multiplying, and dividing polynomials where all
operations are modulus $q$. Therefore, QR TPMs will feature a specialized
vector engine in its cryptographic co-processor to handle the ring algebra.
Moreover, to improve performance and reduce the number of operations in
particular algebraic operations, the co-processor will first convert the
polynomials to the NTT domain. Previous work in this area has shown that a QR
TPM will possess an architecture that is similar to Figure 3 with larger
buffers. The median for the extra memory requirements is one order of
magnitude, due to the larger key sizes present in lattice-based cryptography
(Fiolhais et al., 2020; Ducas et al., 2019; Bos et al., 2018). Figure 4 shows
a public and secret key size comparison between RSA 2048 bits, ECC NISTP256,
Kyber-768, and Dilithium III. However, the security strength provided by the
QR algorithms offsets the increased memory cost. Note that, the specialized
accelerator for lattice-based cryptography will vary depending on the order of
the polynomial ring and the modulus $q$ supported. As a general rule of thumb,
cryptographers increase the order of the polynomial and the modulus $q$ to
provide stronger security (Bos et al., 2018; Ducas et al., 2019).

Figure 3. QR TPM Architecture. Figure 4. Key size comparison between RSA 2048
bits, ECC NISTP256, Kyber-768, and Dilithium III.

##  4\. TPM Emulator and ROT Implementation

To emulate the TPM, we use a fork of the IBM Software TPM (SW-TPM) and TSS (K.
Goldman and IBM, 2018b, a) that supports some QR algorithms in (Fiolhais et
al., 2019a, b). The SW-TPM emulates the TCTI layer through a TCP socket. A
command sends its data to the socket for the TPM to process. Due to the nature
of the emulation, the SW-TPM is also referred to as the TPM server. The SW-TPM
attempts to closely emulate the memory limitations found in a real TPM. There
is no reliance on dynamic memory management. The SW-TPM manages its memory by
using buffers allocated either in the stack, or the .bss and .data program
segments. The main reason behind the choice of this fork is because it already
contained the infrastructure to support QR algorithms, as it was used to
evaluate the architectural implementation of QR algorithms such as Kyber (Bos
et al., 2018), Dilithium (Ducas et al., 2019), NTTRU (Lyubashevsky and Seiler,
2019), and L-DAA (Kassem et al., 2018).

The TPM was also extended to add support for a ROT (Branco et al., 2021)
protocol to evaluate its efficiency in a TPM scenario. The ROT protocol is
implemented in C++ and Assembly (for certain optimizations) (Fiolhais et al.,
2021). However, the SW-TPM and its TSS are written in C (Fiolhais et al.,
2019a, b). C and C++ programs can be linked together if the C++ program
exposes a C Application Binary Interface (ABI). Therefore, we have modified
the ROT protocol such that it can expose functions for each of the required
messages in the protocol. Moreover, we disabled all optimizations found in the
ROT implementation, namely vector instructions for ARM, such that its
computational model would fit the TPM. With these modifications, we compiled a
static library that could be linked with the SW-TPM. Finally, to add support
for the ROT algorithm, four new TPM commands were added for each message
passed in the protocol. The CC_ROT_MSG1 command computes and transfers the
receiver’s first message. The CC_ROT_MSG2 command computes and transfers the
sender’s first message. The CC_ROT_MSG3 command computes and transfers the
receiver’s second, and final, message. Lastly, the CC_ROT_MSG4 command
computes the sender’s challenges. Furthermore, similar modifications were
employed to the TSS, in the form of new C binaries and modifications to the
TSS library, in order to create new commands to call the desired ROT
functionality in the SW-TPM.

The addition of this new algorithm to the SW-TPM and the TSS totaled 880 lines
and 3111 lines modified, respectively. The implementation of ROT in the SW-TPM
and the TSS shows that the usage of a SW-TPM to prototype features that future
TPM specifications may provide requires a small effort.

##  5\. Experimental Results

In the ARM core, the compiler used was GCC 8.3.0 and in RISC-V core the
compiler used was GCC 11.2.0, both with the -O0 optimization flag for the TPM
and the TSS. Even though the ARM cortex possesses a vector unit in the NEON
unit, no vector instructions were used either explicitly by the TPM server,
the TSS commands, or the compiler. This choice was made because the current
TPM 2.0 architecture does not contain a vector unit. To avoid cache misses due
to core migration, the TPM server and the TSS commands were executed in
different cores where each process was pinned to the same core. The frequency
was fixed at 900 MHz in the ARM core and at 1.2 GHz in the RISC-V core such
that dynamic frequency scaling would not taint the performance results.

The experiment methodology used herein is the following. The security
parameters used for each algorithm are: 2048 bits for RSA, the NISTP256 curve
for ECC, the 768 mode in Kyber ($n=256$ and $q=3329$) (Bos et al., 2018), the
level III mode in Dilithium ($n=256$ and $q=8380417$) (Ducas et al., 2019),
and the default security parameters in ROT ($n=512$ and $q=13313$) (Branco et
al., 2021). The ASCII string ”My super secret. Please don’t share.\n” is used
for encryption and signature; signed messages use the SHA3-256 hash; and all
keys are created as non-primary with the fixed TPM and parent properties. All
the measured times result from taking the median over one hundred runs running
on each of the previously described processors. The used TSS commands are:
CC_Create for key creation; CC_Sign for data signature; CC_VerifySignature for
signature verification; CC_{KYBER, RSA}_Encrypt and CC_{KYBER, RSA}_Decrypt
for Kyber and RSA encryption and decryption; CC_KYBER_Enc and CC_KYBER_Dec for
Kyber encapsulation and decapsulation; and CC_{ROT_MSG1, ROT_MSG2, ROT_MSG3,
ROT_MSG4} for the ROT operations. The performance results for each QR and
number-theoretic algorithm can be found in Table 1 for the ARM processor, and
in Table 2 for the RISC-V processor. Furthermore, Figures 5 and 6 shows the
speedups for each core between QR and number-theoretic algorithms. Note that,
in the ROT protocol the time for the receiver is the result of the addition of
the time for MSG1 and MSG3, and the time for the sender is the result of the
addition of the time for MSG2 and MSG4.

Table 1. Execution time (s) for number-theoretic and post-quantum lattice-
based algorithms in a TPM 2.0 running in an ARM Cortex-A7 processor.

| RSA | ECC | Kyber | Dilithium | ROT
---|---|---|---|---|---
| 2048 bits | NISTP256 | 768 | III |
Key Creation | 3,54 | 1,59 | 1,59 | 1,55 | -
Signature | 1,59 | 1,54 | - | 1,59 | -
Verify Signature | 1,52 | 1,55 | - | 1,55 | -
Encryption | 1,54 | - | 1,56 | - | -
Decryption | 1,61 | - | 1,55 | - | -
ROT Receiver | - | - | - | - | 3,16
ROT Sender | - | - | - | - | 3,12

Table 2. Execution time (s) for number-theoretic and post-quantum lattice-
based algorithms in a TPM 2.0 running in a RISC-V U74 processor.

| RSA | ECC | Kyber | Dilithium | ROT
---|---|---|---|---|---
| 2048 bits | NISTP256 | 768 | III | ROT
Key Creation | 4,00 | 3,28 | 3,14 | 3,51 | -
Signature | 3,22 | 3,17 | - | 2,98 | -
Verify Signature | 3,23 | 3,75 | - | 3,13 | -
Encryption | 3,12 | - | 3,05 | - | -
Decryption | 3,29 | - | 3,14 | - | -
ROT Receiver | - | - | - | - | 6,51
ROT Sender | - | - | - | - | 7,1

Figure 5. Encryption and Decryption Speedups between RSA and Kyber for the ARM
Cortex-A7 and the RISC-V U74.

Figure 6. Signature Creation and Verification Speedups between RSA, ECC, and
Dilithium for the ARM Cortex-A7 and the RISC-V U74.

In the ARM core, the QR algorithms Kyber and Dilithium fully replace the
functionality provided by RSA and ECC. Regarding performance, Kyber and
Dilithium are faster at creating keys than RSA, due to the key size and secure
random sampling required in RSA. However, they meet the same performance level
as ECC. For digital signatures, both in signature creation and verification,
Dilithium is on par with both RSA and ECC. In data encryption and decryption,
Kyber is also on par with RSA. With respect to ROT, since the TPM does not yet
offer commands or requires an implementation there is no one-to-one comparison
with a number-theoretic counterpart. However, it has been previously shown
that QR OTs and ROTs significantly outperform number-theoretic OTs and ROTs
(Branco et al., 2021). Therefore, only the QR variants are analyzed. Still,
the performance results for the ROT commands both for a sender and a receiver
are approximately double that of Kyber and Dilithium even though they possess
more complex lattice arithmetic. The ROT results show that it would be
possible for a QR TPM to support ROTs and OTs with minimal architectural
efforts and quite decent performance.

In the RISC-V U74 core, there are some improvements in the QR algorithms.
Kyber and Dilithium create their keys faster than RSA but on par with ECC.
However, in signature operations, Dilithium shows a speedup of at least 6%
when compared with ECC and RSA. The same is true for encryption operations.
Kyber outperforms RSA by at least 3%. For ROT operations, the same conclusions
can be drawn from the ARM experiments, despite ROT having more complex
operations than Kyber and Dilithium, it still provides quite reasonable
performance.

##  6\. Conclusions

This paper showed how to extend the current Number-Theoretic base TPMs to be
QR. By substituting the RSA and ECC algorithms by the Kyber, for key
encapsulation and data encryption/decryption, and the Dilithium primitives,
for digital signature, quantum resistance is ensured by the hardness of
mathematical problems related to lattices. Moreover, the TPM was also
extended, for the first time, to add support for a ROT protocol, useful for
example to Multi-Party Computation, which is based on the same type of
mathematical problems. Not only were the computational and memory requirements
for this TPM extension analysed, but it was experimentally evaluated by
implementations on ARM and RISC-V low-power processors. It is shown that the
security strength provided by the QR algorithms increased memory requirements,
while maintaining or even decreasing the execution time of the QR algorithms.
The ROT protocol was implemented without significant changes to the
architectural model of the TPM and it possesses decent performance. Finally,
we show that the usage of programmable microprocessors in future TPMs would
allow a vendor to add new algorithms remotely to older hardware TPMs, in order
to improve its security features, with minimal changes to the architectural
model. This paper paves the way for the design of QR TPMS based on low-power
programmable devices.

## References

  * (1)
  * ARM (2011) ARM. 2011.  Cortex-A7.  https://developer.arm.com/Processors/Cortex-A7.
  * Beckwith et al. (2021) L. Beckwith, D. Nguyen, and K. Gaj. 2021.  High-Performance Hardware Implementation of CRYSTALS-Dilithium. In _2021 International Conference on Field-Programmable Technology (ICFPT)_. 1–10.  https://doi.org/10.1109/ICFPT52863.2021.9609917
  * Bos et al. (2018) J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehle. 2018\.  CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In _2018 IEEE European Symposium on Security and Privacy (EuroS P)_. 353–367.  https://doi.org/10.1109/EuroSP.2018.00032
  * Branco et al. (2021) P. Branco, L. Fiolhais, M. Goulão, P. Martins, P. Mateus, and L. Sousa. 2021\.  ROTed: Random Oblivious Transfer for embedded devices.  _IACR Transactions on Cryptographic Hardware and Embedded Systems_ 2021, 4 (Aug. 2021), 215–238.  https://doi.org/10.46586/tches.v2021.i4.215-238
  * Brickell et al. (2004) E. Brickell, J. Camenisch, and L. Chen. 2004\.  Direct anonymous attestation. In _Proceedings of the 11th ACM conference on Computer and communications security_. 132–145.
  * Chiu et al. (2023) W. Chiu, W. Meng, and W. Li. 2023.  TPMWallet: Towards Blockchain Hardware Wallet using Trusted Platform Module in IoT. In _2023 International Conference on Computing, Networking and Communications (ICNC)_. IEEE, 336–342.
  * Ducas et al. (2019) L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé. 2019.  Dilithium - Submission to the NIST post-quantum project.  https://pq-crystals.org/dilithium/data/dilithium-specification-round2.pdf.  [Online; accessed 5-September-2019].
  * Fiolhais et al. (2019a) L. Fiolhais, P. Martins, and L. Sousa. 2019a.  SW-TPM.  https://github.com/FutureTPM/sw-tpm.
  * Fiolhais et al. (2019b) L. Fiolhais, P. Martins, and L. Sousa. 2019b.  TSS.  https://github.com/FutureTPM/tss.
  * Fiolhais et al. (2020) L. Fiolhais, P. Martins, and L. Sousa. 2020.  Software Emulation of Quantum Resistant Trusted Platform Modules.. In _ICETE (2)_. 477–484.
  * Fiolhais et al. (2021) L. Fiolhais, P. Martins, and L. Sousa. 2021.  ROTed.  https://github.com/FutureTPM/ROTed.
  * Group ([n. d.]) Trusted Computing Group. [n. d.].  Trusted Platform Module (TPM) Summary.  https://trustedcomputinggroup.org/wp-content/uploads/Trusted-Platform-Module-Summary_04292008.pdf
  * Group (2016) Trusted Computing Group. 2016\.  _Trusted Platform Module (TPM) 2.0: A BRIEF INTRODUCTION_.  Technical Report. Trusted Computing Group.  https://www.trustedcomputinggroup.org/wp-content/uploads/TPM-2.0-A-Brief-Introduction.pdf.
  * K. Goldman and IBM (2018a) K. Goldman and IBM. 2018a.  IBM’s Software TPM 2.0.  https://sourceforge.net/projects/ibmswtpm2/.
  * K. Goldman and IBM (2018b) K. Goldman and IBM. 2018b.  IBM’s TPM 2.0 TSS.  https://sourceforge.net/projects/ibmtpm20tss/.
  * Kassem et al. (2018) N. EL Kassem, L. Chen, R. El Bansarkhani, A. El Kaafarani, J. Camenisch, P. Hough, P. Martins, and L. Sousa. 2018\.  Lattice-based Direct Anonymous Attestation (LDAA).  Cryptology ePrint Archive, Paper 2018/401.  https://eprint.iacr.org/2018/401 https://eprint.iacr.org/2018/401.
  * Lyubashevsky et al. (2010) V. Lyubashevsky, C. Peikert, and O. Regev. 2010.  On Ideal Lattices and Learning with Errors over Rings. In _Advances in Cryptology – EUROCRYPT 2010_ , Henri Gilbert (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–23.
  * Lyubashevsky and Seiler (2019) V. Lyubashevsky and G. Seiler. 2019.  NTTRU: Truly Fast NTRU Using NTT.  Cryptology ePrint Archive, Paper 2019/040.  https://eprint.iacr.org/2019/040 https://eprint.iacr.org/2019/040.
  * Microsoft (2018) Microsoft. 2018\.  TPM recommendations.  https://docs.microsoft.com/en-us/windows/security/information-protection/tpm/tpm-recommendations.
  * Shor (1997) P. W. Shor. 1997\.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.  _SIAM J. Comput._ 26, 5 (oct 1997), 1484–1509.  https://doi.org/10.1137/s0097539795293172
  * SiFive (2022) SiFive. 2022.  SiFive FU740-C000 Manual v1p6.  https://sifive.cdn.prismic.io/sifive/1a82e600-1f93-4f41-b2d8-86ed8b16acba_fu740-c000-manual-v1p6.pdf.
  * Team (2022) The NIST PQC Team. 2022\.  PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth Round Candidates.  https://www.nist.gov/news-events/news/2022/07/pqc-standardization-process-announcing-four-candidates-be-standardized-plus#standardization
  * Xing and Li (2021) Y. Xing and S. Li. 2021\.  A Compact Hardware Implementation of CCA-Secure Key Exchange Mechanism CRYSTALS-KYBER on FPGA.  _IACR Transactions on Cryptographic Hardware and Embedded Systems_ 2021, 2 (Feb. 2021), 328–356.  https://doi.org/10.46586/tches.v2021.i2.328-356


#  DESY 08-136
LTH 805

Wilson twisted mass fermions in the epsilon regime

K. Jansen, A. Nube,
DESY Zeuthen, Platanenallee 6
D-15738 Zeuthen, Germany
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
Theoretical Physics Division,
Dept. of Mathematical Sciences,
University of Liverpool
Liverpool L69 7ZL, UK
E-mail

###### Abstract:

In this proceeding contribution we report on the ongoing effort to understand
and simulate Wilson twisted mass fermions in the so called $\epsilon$ regime.

##  1 Introduction

Simulations in the $\epsilon$ regime are complementary to standard large
volume simulations. They allow to extract low energy constants of the chiral
Lagrangian, in some cases with less contaminations from chiral logs coming
from higher order corrections. For a long time it has been thought that
simulations in the $\epsilon$ regime are restricted to chirally invariant
lattice formulations. In ref. [1] we have argued that actually this is not the
case, and that simulations in the $\epsilon$ regime can be performed also with
non chirally invariant lattice actions such as Wilson like fermions.

In particular in [1] we suggested that a combination of algorithmic and
theoretical understanding of Wilson twisted mass makes it possible to actually
perform simulations in the $\epsilon$ regime with Wilson twisted mass
fermions.

Recently it has been shown that with suitable and related algorithmic ideas
[2] it possible to reach or get close to the $\epsilon$ regime also with
improved Wilson fermions. At this lattice conference further results in this
directions have been presented [3].

In this proceeding we consider a second lattice spacing and we extend to NLO
the analysis performed in [1]. Our setup is a $L^{3}\times T$ euclidean
lattice with spacing $a$. The lattice action

$S[\chi,\overline{\chi},U]=S_{G}[U]+S_{F}[\chi,\overline{\chi},U],$ (1)

is the sum of the so called tree-level improved Symanzik gauge action [4]

$S_{G}[U]=\frac{\beta}{3}\sum_{x}\left\\{b_{0}\sum_{\mu<\nu}\mathbb{R}{\rm
e}~{}{\rm{Tr}}\left[\mathbbm{1}-P^{(1\times
1)}(x;\mu,\nu)\right]+b_{1}\sum_{\mu\neq\nu}\mathbb{R}{\rm
e}~{}{\rm{Tr}}\left[\mathbbm{1}-P^{(2\times 1)}(x;\mu,\nu)\right]\right\\},$
(2)

where

$b_{0}=1-8b_{1},\quad b_{1}=-{1\over 12},$ (3)

with Wilson twisted mass [5]

$S_{\rm
F}[\chi,\overline{\chi},U]=a^{4}\sum_{x}\overline{\chi}(x)\Big{[}D_{\rm
W}+i\mu_{\rm q}\gamma_{5}\tau^{3}\Big{]}\chi(x),$ (4)

where

$D_{\rm
W}=\frac{1}{2}\\{\gamma_{\mu}(\nabla_{\mu}+\nabla^{*}_{\mu})-a\nabla^{*}_{\mu}\nabla_{\mu}\\}+m_{0}.$
(5)

The basic idea of [1] is that by sampling all topological sectors in the
ensemble generation, it is not necessary to have an unambiguous definition of
topology at finite lattice spacing. To achieve this goal it was suggested [1]
to use a PHMC algorithm [6] treating the low modes exactly and reweighting the
observables. This could allow to perform simulations at very low quark masses
without encountering instabilities or metastabilities.

##  2 $\epsilon$ expansion

Lowering the quark mass at finite lattice spacing with Wilson-like fermions
requires a detailed understanding of the interplay between the genuine chiral
behaviour induced by the ’pion’ dynamics and the one generated by cutoff
effects. A review on the phase diagram and cutoff effects with Wilson twisted
mass (Wtm) can be found in ref. [7]. In the $\epsilon$ regime this is
equivalent to saying that it is necessary to understand the coupling of the
zero modes with the relevant operators describing the effect of the lattice
artifacts. The actual values of the lattice spacing, the physical volume and
the quark mass determine the appropriate power counting, which ought to be
used to perform computations using chiral effective theories. In the continuum
the exact integration over the constant zero modes can be achieved in the
chiral effective theory modifying the $p$ regime power counting, in the so
called $\epsilon$ expansion where the would-be pion mass is small compared to
the linear size of the box

$\frac{1}{T}={\rm O}(\epsilon),\quad\frac{1}{L}={\rm O}(\epsilon),\quad
M_{\pi}={\rm O}(\epsilon^{2}).$ (6)

As a result of the exact integration the order parameter, or the equivalent
ratio $R=\frac{\langle\bar{q}q\rangle}{B_{0}F^{2}}$, vanishes in the chiral
limit at fixed finite volume [8], obtaining restoration of chiral symmetry.
One possible way to include the effects of the lattice artifacts in this
analysis is to include with an appropriate power counting the lattice spacing.
Here we modify the standard power counting in the following way [9]

$M=O(\epsilon^{4}),\quad\frac{1}{L}=O(\epsilon),\quad\frac{1}{T}=O(\epsilon)\quad{a^{2}=O(\epsilon^{4})},$
(7)

where $M$ indicates generically a quark mass. The partition function at
leading order reads

${\mathcal{Z}}=\int{\mathcal{D}}[U_{0}]{\rm
e}^{\frac{c_{1}V}{2}{\rm{Tr}}\left[U_{0}+U_{0}^{\dagger}\right]-\frac{c_{2}V}{4}{\rm{Tr}}\left[U_{0}+U_{0}^{\dagger}\right]^{2}+\frac{c_{3}V}{2}{\rm{Tr}}\left[i\tau^{3}\left(U_{0}^{\dagger}-U_{0}\right)\right]},$
(8)

where the scaling variables are

$z_{1}=c_{1}V=B_{0}F^{2}m^{\prime}V,\qquad
z_{2}=c_{2}V=-\frac{F^{2}w^{\prime}Va^{2}}{4},\qquad
z_{3}=c_{3}V=B_{0}F^{2}\mu_{\rm R}V.$ (9)

To argue that this is a proper power counting for actual numerical simulations
we list here some values

$M\simeq 5{\rm MeV},\quad a\simeq 0.1{\rm fm},\quad L\simeq 1.5{\rm fm}$ (10)
$\quad F\simeq 90{\rm MeV},\quad B_{0}\simeq 5.5{\rm
GeV},\quad|w^{\prime}|\simeq(570{\rm MeV})^{4}.$ (11)

Using these values to estimate the relevant scaling variables in this regime
one obtains

$MF^{2}B_{0}V\simeq 0.75,\quad a^{2}F^{2}|w^{\prime}|V\simeq
0.75,\quad\frac{MB_{0}}{a^{2}|w^{\prime}|}\simeq 1,$ (12)

which indicates that this is an appropriate power counting.111If the lattice
spacing is much smaller a different power counting ought to be used where the
lattice artifacts only appear at NNLO.The chiral condensate can be computed in
the standard way

$R=\frac{1}{N_{\rm f}}\frac{\partial}{\partial z_{3}}\log{\mathcal{Z}},\qquad
z_{1}=0,$ (13)

Figure 1: Quark mass (left plot) and lattice spacing (right plot) dependence
for the single flavour chiral condensate normalized with its LO value in the
continuum and infinite volume

and fig. 1 shows the quark mass (left plot) and lattice spacing (right plot)
dependence of the chiral condensate. We can certainly conclude that the
dependence on the quark mass is, as expected, smooth, and the cutoff effects
are under control. Extension of this computation to NLO including standard
2-point functions is currently in progress [9]. The power counting introduced
is general and valid also for plain Wilson fermions ($z_{3}=0$). The same
power counting could be used to develop an expansion with staggered fermions
and to check the chiral properties of the spectrum in the presence of roots of
the staggered determinant.

##  3 Numerical results

Details of the algorithm used to generate the gauge ensemble can be found in
ref. [1]. In this proceeding we complement the results obtained in [1] with a
second lattice spacing with a NLO analysis. The inversions for the quark
propagator have been performed with a stochastic $Z_{2}\times Z_{2}$ source
located randomly along the euclidean time. Table 1 summarizes the simulation
setup.

$\beta$ |  $\kappa$ |  $L/a$ |  $T/a$ |  $a\mu_{\rm q}$
---|---|---|---|---
$4.05$ | $0.157010$ | $20$ | $40$ | $0.00039$

$N_{\rm traj}$ |  $N_{\rm ana}$ |  $\tau_{\rm int}(P)$ |  $\tau_{\rm int}(m_{\rm PCAC})$
---|---|---|---
$2500$ | $421$ | $\sim 0.5$ | $\sim 0.5$

$r_{0}/a$ |  $a[{\rm fm}]$ |  $L[{\rm fm}]$ |  $am_{\rm PCAC}$
---|---|---|---
$6.61(3)$ | $0.0656(11)$ | $1.31$ | $0.00045(12)$

Table 1: Summary of the simulation setup and of the basic ensemble parameters.

In the left plot of fig. 2, we show in the first strip the plaquette MC
history and its distribution. In the second strip we show the MC history and
distribution of the lowest eigenvalue, compared with the value of the infrared
cutoff (horizontal red line) provided by the twisted mass. In the third strip
we show the MC history of the reweighting factor and its distribution.

Figure 2: Left plot: MC histories and distributions of the plaquette (first
strip) smallest eigenvalue (second strip) and reweighting factor (third
strip). The smallest eigenvalue is compared with the infrared cutoff provided
by the twisted mass (horizontal line). Right plot: MC history and distribution
at $x_{0}=T/4$ (first strip) together with the euclidean time dependence of
the PCAC mass (second strip).

One crucial parameter for stability issues and for controlling discretization
errors is the PCAC mass. In the right plot of fig. 2, we show the MC history
and the distribution of the PCAC mass at $x_{0}=T/4$, together with the
euclidean time dependence of the PCAC mass. It is remarkable that there is
almost no sign of boundary O($a$) cutoff effects. The analysis gives with the
corresponding Z factors [10]

$am_{\rm PCAC}=0.00045(12)\qquad\Rightarrow\qquad aM_{\rm
R}^{{\rm\overline{MS\kern-0.35002pt}\kern 0.35002pt}}(2{\rm GeV})=0.0012(2),$
(14)

where

$M_{\rm R}^{{\rm\overline{MS\kern-0.35002pt}\kern 0.35002pt}}(2{\rm
GeV})=\frac{1}{Z_{\rm P}}M\qquad M=\sqrt{\left(Z_{\rm A}m_{\rm
PCAC}\right)^{2}+\mu_{\rm q}^{2}}.$ (15)

We are clearly not at full twist. It is important to remark that this is not
so relevant in the regime where chiral symmetry is restored. Automatic O($a$)
improvement [11] actually holds in a finite volume and with suitable boundary
conditions also for massless Wilson fermions [12]. This is somehow related to
the fact that in the region where chiral symmetry is restored only O($am_{\rm
PCAC}$) cutoff effects are expected, i.e. very small effects. On the other
hand if the mass is of O($a^{2}$) in general the latter could be the cutoff
effects to become visible.

###  3.1 Low energy constants

The values of the low energy constants (LEC) can be extracted comparing the
results of the numerical simulations for the euclidean time dependence of
basic two-point functions with the prediction of $\chi$PT [13, 14]. In this
proceeding we consider the correlation function

$C_{\rm P}(x_{0})=\frac{a^{3}}{L^{3}}\sum_{\bf x}C_{\rm P}({\bf
x},x_{0})\qquad\delta^{ab}C_{\rm P}({\bf x},x_{0})=\langle P^{a}({\bf
x},x_{0})P^{b}({\bf 0},0)\rangle$ (16)

between charged pseudoscalar currents

$P^{a}(x)=\overline{\chi}(x)i\gamma_{5}\frac{\tau^{a}}{2}\chi(x).$ (17)

The euclidean time dependence of the correlation function in $\chi$PT is given
by

$C_{\rm P}(x_{0})=a_{\rm P}+\frac{T}{L^{3}}b_{\rm
P}\left[\frac{y^{2}}{2}-\frac{1}{24}\right]+\ldots\qquad
y=\frac{x_{0}}{T}-\frac{1}{2},$ (18)

where we have defined the following variables

$a_{\rm P}=\frac{B_{0}^{2}F^{4}\rho^{2}}{8}G_{1}(u),\qquad b_{\rm
P}=F^{2}B_{0}^{2}\left[1-\frac{1}{8}G_{1}(u)\right].$ (19)

Details on the definitions of $\rho$, $u$ and $g_{1}$ can be found in [13,
14]. We can thus fit the results from the numerical simulations with the
following fit formulæ

$C_{\rm P}(x_{0})=A_{0}+A_{2}y^{2}\qquad\Rightarrow\qquad a_{\rm
P}=A_{0}+\frac{A_{2}}{12}\qquad b_{\rm P}=A_{2}\frac{2L^{3}}{T}$ (20)

In the left plot of fig. 3, we show the euclidean time dependence of $C_{\rm
P}(x_{0})$ together with the result of the fit (red curve). The line is solid
along the fit range and it becomes dashed where the points are not included in
the fit.

Figure 3: Left plot: Euclidean time dependence of $C_{\rm P}(x_{0})$ together
with the result of the fit. The solid line indicates the fit range, while the
dashed line indicates the same curve outside the fit range. Right plot: fit
results for chiral condensate (first strip) and decay constant (second strip)
as a function of the number of points included in the fit around the middle
point $T/2$. The circles indicate the actual values quoted in the text and the
dashed lines indicate the range of values used to determine the systematic
error.

The results of the analysis are

$a^{3}L^{3}A_{0}=(5.94(36))\cdot 10^{-3},\qquad
a^{3}L^{3}A_{2}=(4.81(30))\cdot 10^{-2}$ (21)

where the errors have been computed with a nested Jackknife/bootstrap
procedure. It is important to check the stability of the fit results with
respect to the number of data $N_{\rm data}$ included in the fit. This is
especially important if we want to make sure that the parabolic time
dependence is a real feature coming from simulating in the $\epsilon$ regime
and not just accidental, i.e. coming from the standard $cosh$ dependence which
can reproduce a fake parabolic behaviour around the $T/2$.

In the right plot of fig. 3, we show the stability of the effective chiral
condensate and decay constant as a function of the number of data points (i.e
time slices) around the middle point included in the fits. While the chiral
condensate shows a remarkably stable result including more points in the fit,
the decay constant shows a somehow not completely flat dependence on the
number of data included in the fit. Although this is not worrisome, it might
be an indication of a physical volume not sufficiently large to suppress
higher order corrections. A perfectly well defined way to proceed would be to
include in the systematic error for $F$ the spread of its value in the region
between the 2 dashed lines. The preliminary result of this analysis is

$r_{0}\Sigma^{1/3}=0.620(8),\qquad r_{0}F=0.220(8)(10)$ (22)

which agrees rather well with results obtained in the $\epsilon$ regime using
improved Wilson fermions [15].

##  4 Conclusions and outlook

We are establishing the basic knowledge to simulate with Wilson-like fermions
in the $\epsilon$ regime. To do this we have introduced a power counting to
study the $\epsilon$ expansion with Wilson-like fermions. The LO computation
for the chiral condensate confirms the absence of any phase transition, and a
NLO extension for the condensate and other observables is currently ongoing.

Numerical simulations in the $\epsilon$ regime with Wtm are feasible using a
PHMC with exact reweighting. This particular choice allows to lower
significantly the quark mass. The extraction of LEC such as $\Sigma$ and $F$
becomes then feasible. Moreover the NLO $\epsilon$ expansion is not
contaminated by chiral logs, which could be a benefit in reducing the
systematic errors.

Computations in this extreme region with Wilson-like fermions require a
detailed understanding of the usual systematics: discretization errors, quark
mass and volume dependence.

We remark that it might be advantageous to combine $p$ and $\epsilon$ regime
simulations both as a tool to attack $2+1(+1)$ simulations, and to further
constrain the values of the LEC.

###### Acknowledgments.

We thank the organizers of “Lattice 2008” for the very interesting conference
realized in Williamsburg. We thank J. Gonzalez Lopez, C. Michael and G.C.
Rossi for a careful reading of this proceeding, and all the members of ETMC
for valuable discussions.

## References

  * [1] K. Jansen, A. Nube, A. Shindler, C. Urbach and U. Wenger, Exploring the epsilon regime with twisted mass fermions, PoS LAT2007 (2007) 084 [0711.1871].
  * [2] A. Hasenfratz, R. Hoffmann and S. Schaefer, Reweighting towards the chiral limit, Phys. Rev. D78 (2008) 014515 [0805.2369].
  * [3] A. Hasenfratz and F. Palombi. Talks presented at this lattice conference.
  * [4] P. Weisz, Continuum Limit Improved Lattice Action for Pure Yang- Mills Theory. 1, Nucl. Phys. B212 (1983) 1.
  * [5] Alpha Collaboration, R. Frezzotti, P. A. Grassi, S. Sint and P. Weisz, Lattice QCD with a chirally twisted mass term, JHEP 08 (2001) 058 [hep-lat/0101001].
  * [6] R. Frezzotti and K. Jansen, A polynomial hybrid Monte Carlo algorithm, Phys. Lett. B402 (1997) 328–334 [hep-lat/9702016].
  * [7] A. Shindler, Twisted mass lattice QCD, Phys. Rept. 461 (2008) 37–110 [0707.4093].
  * [8] J. Gasser and H. Leutwyler, Thermodynamics of Chiral Symmetry, Phys. Lett. B188 (1987) 477.
  * [9] A. Shindler, In preparation, .
  * [10] P. Dimopoulos, R. Frezzotti, V. Lubicz and G. Rossi, ETMC internal notes, .
  * [11] R. Frezzotti and G. C. Rossi, Chirally improving Wilson fermions. I: O(a) improvement, JHEP 08 (2004) 007 [hep-lat/0306014].
  * [12] S. Sint, The Schroedinger functional with chirally rotated boundary conditions, PoS LAT2005 (2006) 235 [hep-lat/0511034].
  * [13] P. Hasenfratz and H. Leutwyler, Goldstone boson related finite size effects in field theory and critical phenomena with O(N) symmetry, Nucl. Phys. B343 (1990) 241–284.
  * [14] F. C. Hansen, Finite size effects in spontaneously broken SU(N) x SU(N) theories, Nucl. Phys. B345 (1990) 685–708.
  * [15] A. Hasenfratz, R. Hoffmann and S. Schaefer, Low energy chiral constants from epsilon-regime simulations with improved Wilson fermions, 0806.4586.


$\tilde{Y}_{j^{1}}^{*}\cap\tilde{Y}_{j^{2}}^{*,1}\cap\dots,\cap\tilde{Y}_{j^{i}}^{*,1,2,\dots,i-1}\neq\emptyset.$
(B.47)

This concludes the proof of the first part of the theorem.

(Theorem 2) By combining Lemma 1 (set sequence) and Lemma 2, the theorem will
be proven by showing that $S_{i}^{*}=\bar{S}_{i},\,\,\forall i=1,\dots,N$. We
first focus on the case of connected graph $\mathcal{G}_{c}=(R,E)$ and then
extended the proof to the case of non connected graphs.

Taking into account (13) and Lemma 1, we immediately have that
$\bar{S}_{i}\subseteq S_{i}^{*}$.

To prove the equality between the two sets let us suppose, by contradiction,
that at least for one $i$, we have $S_{i}^{*}\neq\bar{S}_{i}$ and so that the
strict inclusion $\bar{S}_{i}\subset S_{i}^{*}$ holds. From such strict
inclusion assumption, by setting

$\tilde{S}_{i}^{*}=S_{i}^{*}\backslash\bar{S}_{i},$ (B.48)

it follows that $\tilde{S}_{i}^{*}\neq\emptyset$.

For the sake of brevity, we use the same simplified notation adopted in the
proof of Theorem B.1. Specifically, we set
$Y_{j}^{*}=\mathcal{E}_{\mathcal{B}_{j}}^{\bar{\mathcal{B}}}(S_{j}^{*})$ and
$\tilde{Y}_{j}^{*}=\mathcal{E}_{\mathcal{B}_{j}}^{\bar{\mathcal{B}}}(\tilde{S}_{j}^{*})$
(the latter with the possibility of reporting in the superscript the inducing
subsets, as done for (B.47)). The subsets $\tilde{S}_{j}^{*}$, with $j\neq i$,
will be determined next.

The following relation holds

$\tilde{Y}_{i}^{*}\cap\bigcap_{j=1,j\neq i}^{N}Y_{j}^{*}=\emptyset.$ (B.49)

Indeed, we have

$\displaystyle\tilde{Y}_{i}^{*}$ $\displaystyle\cap\bigcap_{j=1,j\neq
i}^{N}Y_{j}^{*}=$ $\displaystyle\tilde{Y}_{i}^{*}$
$\displaystyle\cap\bigcap_{j=1}^{N}Y_{j}^{*}=$
$\displaystyle\tilde{Y}_{i}^{*}$ $\displaystyle\cap\bar{S}=\emptyset,$

where, in the last step we applied Lemma 2 point ii. and considered that, in
case of nonempty intersection, we would have had points
$\bar{s}_{i}\in\mathcal{P}_{\mathcal{B}_{i}}^{\bar{\mathcal{B}}}(\bar{S})$
such that $\bar{s}_{i}\in\tilde{S}_{i}^{*}$ and $\bar{s}_{i}\in\bar{S}_{i}$,
contradicting the (B.48).

Let us now order the nodes as $j^{1},j^{2},\dots,j^{N}$ according to a
connected path and with $j^{1}=i$. We call

$\mathcal{A}_{0}=\tilde{Y}_{j^{1}}^{*}\cap Y_{j^{2}}^{*}\cap
Y_{j^{3}}^{*}\cap\dots\cap Y_{j^{N}}^{*}.$

We rewrite (B.49) as $\mathcal{A}_{0}=\emptyset$. Since
$\tilde{S}_{j^{1}}^{*}\neq\emptyset$, it induces a nonempty subset to
$S_{j^{2}}^{*}$ along the connected path, according Theorem B.1. Let now
consider

$\mathcal{A}_{1}=\tilde{Y}_{j^{1}}^{*}\cap\tilde{Y}_{j^{2}}^{*,1}\cap
Y_{j^{3}}^{*}\cap\dots\cap Y_{j^{N}}^{*}.$

We obviously have $\mathcal{A}_{1}\subseteq\mathcal{A}_{0}$. Considering now
the induced $\tilde{Y}_{j^{3}}^{*,1,2}$ and defining $\mathcal{A}_{2}$ in
analogous way, we have
$\mathcal{A}_{2}\subseteq\mathcal{A}_{1}\subseteq\mathcal{A}_{0}$.
Generalizing the iterations up to node $j^{i+1}$, with $i=1,\dots,N-1$, and by
iteratively applying Theorem B.1 we have

$\mathcal{A}_{i}=\tilde{Y}_{j^{1}}^{*}\cap\tilde{Y}_{j^{2}}^{*,1}\cap\tilde{Y}_{j^{3}}^{*,1,2}\cap\dots\cap\tilde{Y}_{j^{i+1}}^{*,1,2,\dots,i}\cap
Y_{j^{i+1}}^{*}\cap\dots\cap Y_{j^{N}}^{*},$

with $\mathcal{A}_{i}\subseteq\mathcal{A}_{i-1}$.

Iterating the process up to node $j^{N}$ we have that, according to (B.47),
$\mathcal{A}_{N-1}\neq\emptyset$. On the other hand, since from (B.49)
$\mathcal{A}_{0}=\emptyset$, we have

$\emptyset\neq\mathcal{A}_{N-1}\subseteq\mathcal{A}_{0}=\emptyset.$ (B.50)

The contradiction implies that $\bar{S}_{i}=S_{i}^{*}$.

The poof can be easily extended to the case of non connected graphs. Indeed
suppose that, without loss of generality, the graph is partitioned in $p$
connected components, i.e.,
$\mathcal{G}_{c1}=(R_{1},E_{1}),\mathcal{G}_{c2}=(R_{2},E_{2}),\dots,\mathcal{G}_{cp}=(R_{p},E_{p})$,
with $N_{1},N_{2},\dots,N_{p}$ elements each.

Notice that, for any $\mathcal{G}_{c_{m}}=(R_{m},E_{m})$ and
$\mathcal{G}_{c_{l}}=(R_{l},E_{l})$ different components, i.e., with $m\neq
l$, we always have $\tilde{Y}_{j}^{*}\cap\tilde{Y}_{h}^{*}\neq\emptyset$ with
$j\in R_{m}$ and $h\in R_{l}$ since
$\mathcal{B}_{j}\cap\mathcal{B}_{h}=\emptyset$. Hence, for the whole graph we
can manipulate each connected component independently and, at the same time,
write again $\mathcal{A}_{0}=\emptyset$. By using similar arguments as for
(B.50), we obtain

$\emptyset\neq\mathcal{A}_{N_{1}-1}\cap\mathcal{A}_{N_{2}-1}\cap\dots\cap\mathcal{A}_{N_{p}-1}\subseteq\mathcal{A}_{0}=\emptyset.$

The above contradiction implies $\bar{S}_{i}=S_{i}^{*}$.

(Lemma 3) The proof is trivial. It suffices to notice that the solution of
system (14) satisfies the conditions in Definition 5 and vice-versa.

(Lemma 4) Consider the set
$\bar{S}_{k}:=\mathcal{P}_{\bar{\mathcal{B}}_{x,0}}^{\bar{\mathcal{B}}^{H}}(\bar{S}_{kh})$.
It is trivial to notice that for all the $\bar{\mathbf{z}}\in\bar{S}_{k}$
there exist $\mathbf{z}\in\bar{S}_{kh}$ such that
$\mathcal{P}_{\bar{\mathcal{B}}_{x,0}}^{\bar{\mathcal{B}}^{H}}(\mathbf{z})\in\bar{S}_{k}$.
Since $\bar{S}_{kh}$ is the solution of (14), then
$\bar{S}_{k}\rightrsquigarrow\bar{S}_{h}$.

On the other hand, by setting
$\breve{S}_{k}=\mathbb{R}^{n}\backslash\bar{S}_{k}$, we trivially have
$\breve{S}_{k}\nrightrsquigarrow\bar{S}_{h}$. Indeed,
$\forall\mathbf{z}\in\mathbb{R}^{(H+1)(n+m)}$ such that
$\mathcal{P}_{\bar{\mathcal{B}}_{x,0}}^{\bar{\mathcal{B}}^{H}}(\mathbf{z})\in\breve{S}_{k}$,
we have that $\mathbf{z}\notin\bar{S}_{kh}$. Therefore,
$\bar{S}_{k}=\mathrm{Pre}(\bar{S}_{h})$.

(Lemma 5) The proof is trivial since the left hand side of equation (16) is
the solution of system (14), while the right hand side is the solution of the
system obtained by considering the (15) for all $i=1,\dots,N$. The latter is
an equivalent way of expressing system (14).

(Theorem 3) The proof is a direct result of the application of Theorem 2.

(Theorem 4) It is immediate to notice that, for all $i=1,\dots,N$,
$\bar{S}_{k,i}=\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}^{H}}(\bar{S}_{kh})$.
Indeed,
$\bar{S}_{k,i}=\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}_{x,0}}(\bar{S}_{k})=\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}_{x,0}}\left[\mathcal{P}_{\bar{\mathcal{B}}_{x,0}}^{\bar{\mathcal{B}}^{H}}(\bar{S}_{kh})\right]=\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}^{H}}(\bar{S}_{kh})$.

We will prove that $\underline{S}_{k,i}=\bar{S}_{k,i}$ via showing the double
inclusion $\bar{S}_{k,i}\subseteq\underline{S}_{k,i}$ and
$\underline{S}_{k,i}\subseteq\bar{S}_{k,i}$, with $i=1,\dots,N$.

Let us call
$\underline{S}_{k}=\bigcap_{j=1}^{N}\mathcal{E}_{\mathcal{B}_{x,0,j}}^{\bar{\mathcal{B}}_{x,0}}(\underline{S}_{k,j})$.
First of all, notice that by construction
$\bar{S}_{k}\subseteq\underline{S}_{k}$. Since for every point $\bar{s}_{k,i}$
there exist points $\bar{s}_{k}\in\bar{S}_{k}$ such that
$\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}_{x,0}}(\bar{s}_{k})=\bar{s}_{k,i}$
and since $\bar{s}_{k}\in\underline{S}_{k}$, then
$\bar{s}_{k,i}\in\underline{S}_{k,i}$. Therefore,
$\bar{S}_{k,i}\subseteq\underline{S}_{k,i}$.

To prove that for every point $\underline{s}_{k,i}\in\underline{S}_{k,i}$ we
also have $\underline{s}_{k,i}\in\bar{S}_{k,i}$ it suffices to notice that
there exist points $\bar{s}_{kh}\in\bar{S}_{kh}$ such that
$\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}^{H}}(\bar{s}_{kh})=\underline{s}_{k,i}$.
Since the projection of such points $\bar{s}_{kh}$ onto the space generated by
the axis set $\bar{\mathcal{B}}_{x,0}$ gives points $\bar{s}_{k}$ such that
$\mathcal{P}_{\mathcal{B}_{x,0,i}}^{\bar{\mathcal{B}}_{x,0}}(\bar{s}_{k})=\underline{s}_{k,i}$,
then $\underline{s}_{k,i}\in\bar{S}_{k,i}$. This concludes the proof.

(Theorem 5) The proof follows analogous steps as for the proof of Theorem 4.