11institutetext:  University of Naples ’Parthenope’, Department of Engineering
11email: {lorenzo.andolfo, luigi.coppolino, salvatore.dantonio,
giovanni.mazzeo<EMAIL_ADDRESS>
22institutetext: X-Margin Inc., 141 Nantucket Cove, San Rafael, California,
94901
22email: {matthew, arne<EMAIL_ADDRESS>
# Privacy-preserving Credit Scoring via Functional Encryption

Lorenzo Andolfo 11 Luigi Coppolino 11 Salvatore D’Antonio 11 Giovanni Mazzeo
11 Luigi Romano 11 Matthew Ficke 22 Arne Hollum 22 Darshan Vaydia 22

###### Abstract

The majority of financial organizations managing confidential data are aware
of security threats and leverage widely accepted solutions (e.g., storage
encryption, transport-level encryption, intrusion detection systems) to
prevent or detect attacks. Yet these hardening measures do little to face even
worse threats posed on _data-in-use_. Solutions such as Homomorphic Encryption
(HE) and hardware-assisted Trusted Execution Environment (TEE) are nowadays
among the preferred approaches for mitigating this type of threats. However,
given the high-performance overhead of HE, financial institutions —whose
processing rate requirements are stringent— are more oriented towards TEE-
based solutions. The _X-Margin Inc._ company, for example, offers secure
financial computations by combining the Intel SGX TEE technology and HE-based
_Zero-Knowledge Proofs_ , which shield customers’ _data-in-use_ even against
_malicious insiders_ , i.e., users having privileged access to the system.
Despite such a solution offers strong security guarantees, it is constrained
by having to trust Intel and by the SGX hardware extension availability. In
this paper, we evaluate a new frontier for _X-Margin_ , i.e., performing
privacy-preserving credit risk scoring via an emerging cryptographic scheme:
_Functional Encryption (FE)_ , which allows a user to only learn a function of
the encrypted data. We describe how the _X-Margin_ application can benefit
from this innovative approach and —most importantly— evaluate its performance
impact.

###### Keywords:

Credit Scoring Data Privacy Functional Encryption Machine Learning

##  1 Introduction

Data confidentiality has significant relevance in the financial field. The
disclosure of sensitive information such as credit scoring or exchange
apikeys, can lead to, e.g., learn about users’ credit risk —and therefore
decide whether to lend money— or ultimately money theft. A data breach
inevitably leads to serious consequences affecting the reputation of the
financial institution. The importance of cyber-security is even more crucial
for the cryptocurrency industry, whose current valuation —$1.8$$ trillion in
2021— attracts a rapidly increasing number of hackers. Only in the last two
years, four large hacks occurred in the digital currency
space111https://www.investopedia.com/news/largest-cryptocurrency-hacks-so-far-
year/.
Companies are therefore pushing on equipping their platforms with state-of-
the-art security mechanisms. There are widely accepted solutions such as
storage encryption, transport-level encryption, intrusion detection systems,
firewalls, IP white-listing, which are used and help in preventing common
cyber-attacks. However, there are still open issues —especially in terms of
_data-in-use_ protection against privileged attackers (e.g., a _malicious
insider_)— that requires more advanced approaches. Companies aim for methods
where the customer does not need to trust them. There are technologies and
cryptography schemes that can be leveraged for this purpose. In this regard,
the adoption of hardware-assisted Trusted Execution Environments (TEE) (e.g.,
Intel SGX) [15] and Homomorphic Encryption (HE) [12] is making its way into
the industrial community to ensure this kind of protection. HE is extremely
powerful since it enables arbitrary computations on ciphered data and allows
the user to trust no one. A TEE such as SGX provides also strong security
guarantees enabling the execution of sensitive code in an isolated and
measurable area of CPUs, with the only limitation that the user needs to trust
the hardware manufacturers such as Intel and that the application’s state is
sealed in the hardware [6]. Unfortunately, the exclusive use of HE is not
doable since it is affected by a non-negligible execution time overhead, and
by a large cipher text expansion. Moreover, a major problem of HE is the so-
called unverifiable conditional issue, which forces a program running on a
third-party host, and processing homomorphically encrypted data, to request
that a client decrypts intermediate functional results to proceed further in
the execution [7]. This introduces additional synchronization points and
performance overhead, and increases the risk of information disclosure (e.g.
via side channel analysis of the program workflow). For this reason, the trend
for the majority of financial companies is to prefer TEEs.
The _X-Margin Inc._ 222https://xmargin.io/ company, instead, uses both
security mechanisms. It offers secure credit risk scoring by shielding
computations in Intel SGX enclaves and performs HE-based _Zero-Knowledge
Proofs_ to offer cryptographic Proof of Security, Computation and Encrypted
Input. In this paper, we explore an innovative approach for _X-Margin_ which
would allow to replace the use of SGX, thus removing Intel from the chain-of-
trust and being hardware agnostic: _Functional Encryption_ (FE) [5]. This is a
cryptographic scheme similar to HE that does both evaluation and decryption of
the _result of a function_ at the same time, without leaking the private key
for data decryption and without leaking information about the plaintexts. This
means that —unlike HE— there is no need anymore of doing synchronizations
between the client and the computation entity for intermediate results. In a
FE model, there are special “evaluation keys” that only allow the functional
evaluation of ciphered data. An additional advantage given by the FE scheme is
that it enables _Attribute-based encryption_ (ABE) schemes, where the
encrypted data is linked with a set of attributes and secret keys along with
certain policies that allow to control which ciphertexts can be decrypted
depending on the possessed attributes. Unlike the classical encryption
systems, where “ _access to the encrypted data is all or nothing, one can
either decrypt and read the entire plain or one learns nothing at all about
the plain other than its length_ ”, FE tries to change this paradigm allowing
a more fine-grained access to encrypted data and improving its flexibility. We
describe how FE can be leveraged for _X-Margin_ financial computations and
—most importantly— evaluate the performance impact of this innovative scheme.
We overview a solution that computes credit risk from an encrypted borrower’s
data with the FE, thus preserving data privacy in a cloud environment even
from the company itself. As a first step, we implemented an ad-hoc neural
network for the purpose of credit risk scoring, which acts as a binary
classifier saying whether a loan defaults. The training is conducted on a
plain dataset. The resulting weight configuration downstream the training step
is saved for the second step. We built the functional encryption scheme using
the weights configuration obtained during the first step. We used a symmetric
private key quadratic multivariate polynomial scheme called SGP [8]. As from
the definition of functional encryption, the result of decryption is not the
record itself, but the evaluation of a function of it, that is represented by
the credit risk associated to the borrower. At the end, we computed the credit
risk via two FE functions: one that computes the score to say whether the
borrower defaults, and the other one that computes the score whether the
borrower doesn’t default. Then, the final result is normalized among the
scores in order to provide the probability of default. Results from
experimental evaluation show that the FE entails a non-negligible overhead on
the classification time. Using 20 attributes, the application took 17.3s to
compute the score with 200 borrowers in the system. It is important to notice
that the scoring classification job is highly parallelizable, thus performance
can be improved using multiple nodes.
The rest of this paper is organized as follows: In Section 2, we provide a
background on credit scoring and on the FE scheme. Afterwards, in Section 3,
the X-Margin case study is presented. In Section 4, the architecture of the
proposed solution is discussed. Section 5 presents results from the
experimental evaluation. Finally, Section 6 concludes the document.

##  2 Background

In this section, we provide a background on the two main elements covered in
this work, i.e., credit scoring and functional encryption.

###  2.1 Principles of Credit Scoring

Credit scoring is a method that is historically used by banks to estimate the
risk of lending money to an individual. It determines the ability of a person
to repay the debts. The higher is the credit score, the higher is the
probability of obtaining a loan with low interest rates. On the other hand,
people with a lower credit score must pay higher interest rates on their
loans. The process of giving a loan is influenced by many factors:
characteristics of borrowers in terms of who they are, their economic
situation, the amount of the requested loan, its purpose, and the collateral
type. The risk is estimated using elements of quantitative and qualitative
analysis. The quantitative analysis takes into account an assessment of the
financial standing of customers. It could also consider cash flow analysis of
customers’ accounts together with their credit history. While the qualitative
assessment includes other information such as the education, employment,
industry in which they operate, or the way of keeping accounts.

###  2.2 Fundamentals of Functional Encryption

Functional encryption (FE) is relatively a new encryption technique, which was
introduced by Amit Sahai and Brent Water in 2008 [FE_pres]. FE enables
selective access control of sensitive data $d$ basing on specific functions
$f(d)$. In an FE scheme, a decryption key $sfKey(f)$ is associated with the
function $f$. Therefore, the decryption of an encrypted data $d$ through
$sfKey(f)$, provides the function evaluation $f(d)$, and nothing more about
$d$. Concerning differences between FE and FHE, from one side they result
similar, because once the message has been encrypted, both evaluate a function
of the message. However, FHE suffers from to the additional step of decrypting
the evaluation of the function, since the result of its computation is still
an encrypted result. With FE instead, the result of the decryption already
represents the evaluation of the function. FE has been successfully applied to
cloud environments and to obfuscation mechanisms [9], that can be useful for
example to protect intellectual property. Unfortunately, up to now, industries
seldom adopt such advanced cryptography technologies: the majority of
cryptography technologies used by industries were developed in early 2000s
[14]. Only recently, thanks to the ambitious project FENTEC (Functional
ENcryption TEChnologies) 333https://fentec.eu/, there has been a tentative to
propose FE solutions for privacy preserving in a wide range of sectors from
clinical data 444https://github.com/fentec-project/Selective-Access-to-
Clinical-Data, to public transportation 555 https://github.com/fentec-
project/FE-anonymous-heatmap.
There are several types of schemes that can be assimilated to the FE, these
are: attribute-based encryption (ABE) [10], [3], [13], identity-based
encryption (IBE) [4], the ones that implement inner product functions [1], [2]
and nonlinear (at most quadratic) polynomials. In this work, the focus is on a
symmetric private key FE scheme called SGP, that implements a two dimensional
quadratic polynomial function.

$f(x,y):\sum_{i=1,j=1}^{m,n}f_{i,j}x_{i}y_{j}=\underset{1\times
m}{X^{T}}\cdot\underset{m\times n}{\mathrm{F}}\cdot\underset{n\times 1}{Y}$
(1)

Here, $X$ and $Y$ represents the vectors we want to encrypt, while $F$ is a
custom matrix. The result of decryption in this case will be the evaluation of
the function above.

Regarding security, it provides an adaptive security under chosen-plaintext
attacks (IND-CPA security) which is based on bilinear pairings, with the
following primitives:

  1. 1.

$msk\leftarrow GenerateMasterKey()$: generates a secret key for the SGP
scheme.

  2. 2.

$c\leftarrow Encrypt(X,Y,msk)$: encrypts input vectors $X$ and $Y$ with the
secret key $msk$ and returns the appropriate ciphertext $c$.

  3. 3.

$feKey\leftarrow DeriveKey(msk,F)$: given in input a custom matrix $F$ and the
secret key $msk$, derives the FE key $feKey$.

  4. 4.

$X^{T}\cdot\mathrm{F}\cdot Y\leftarrow Decrypt(c,feKey,F)$: given in input the
ciphertext $c$ the FE key $feKey$ and the custom matrix $F$, gets the
evaluation of $f(x,y)$ that is $X^{T}\cdot\mathrm{F}\cdot Y$.

##  3 The X-Margin Case Study

_X-Margin Inc._ provides privacy-preserving credit scoring in the crypto-
currency credit market. With over $$100$B of crypto-collateral being used to
generate over $$1.25$B of interest on a quarterly basis, credit is one of the
most rapidly growing sectors of the emerging crypto-currency finance
ecosystem. _X-Margin_ allows borrowers to supply lenders with real-time
portfolio risk metrics, while preserving the privacy of trades, positions, and
other sensitive information. Borrowers benefit from improved lending terms, as
they can display their risk in real-time and assure lenders they are trading
responsibly. Lenders benefit from increased visibility and real-time
information. _X-Margin_ calculates a variety of Risk Metrics on each user’s
portfolio, including Equity, Balance, Margin Usage, Maximum Loss (SPAN or VaR
calculations), Aggregate absolute Delta, and . The company uses Zero Knowledge
technology to ensure that the credit scoring system is functioning in an
unbiased and privacy preserving way, and as the users expect.
_X-Margin_ leverages TEE technologies, along with HE-based cryptographic Proof
of Security, Computation and Encrypted Input, to ensure the privacy of users’
sensitive data and guarantee risk analysis. Intel Software Guard Extensions
(SGX), is the enabling TEE technology that is currently used to protect and
attest the sensitive computations. SGX is a recent extension of modern CPUs,
which ensures confidentiality even against super-privileged users running as
_root_. _X-Margin_ uses HE-based schemes for Proof of Computation including a
Proof of Encrypted Input. Together, the proofs demonstrate that a given
function being executed within the SGX enclave corresponds exactly to a
symbolic representation stored in the server, outside the enclave —the
untrusted ’host’— and that the data on which the function operates is received
encrypted from an external source. _X-Margin_ proves that the functions the
system is instructed to run are run in the enclave, without revealing the
functions themselves. The Proof of Computation & Encrypt ed Input uses the
Enhanced Skyline protocol, which is a proprietary protocol developed by _X-
Margin_ ’s team of cryptographers. Figure 1 shows the current architecture of
the _X-Margin_ solution. There is a SGX-based Key Management System (KMS) that
holds users’ apikeys, and a CScore unit where the actual private computation
takes place, protected by the SGX secure enclave, and proven by cryptographic
proofs. It queries spot/derivative exchanges and provide risk score metrics to
a Time Series Database (TSDB).
The goal of the company is to further improve their solution by raising the
concept of _trust_ to a higher level. In the current situation, in fact, its
customers must trust the hardware manufacturer, i.e., _Intel_. It would be
ideal for the company to remove also Intel from the _chain-of-trust_.
Furthermore, in the current status, the credit scoring application is strictly
bounded to a particular hardware where the SGX ISA extension —and the related
motherboard support— is available. This also entails migration constraints
because the application’s state is sealed in the hardware. _X-Margin_ ’s R&D
is therefore exploring new innovative security techniques to cope with the
mentioned limitations.

Figure 1: The _X-Margin_ architecture

##  4 The FE-based Credit Scoring Solution

The functional encryption paradigm represents an opportunity to overcome
limitations posed by the SGX-based credit scoring solution. It ensures
security properties similar to HE but with the advantage that it allows to
learn specific functions of the encrypted data. Overall, the FE-based credit
scoring works as follows. In a first phase, the neural network is trained
leveraging plain datasets in _X-Margin_ ’s premises. This is acceptable since
the training process does not use any customers’ sensitive data but it is
conducted on anonymous data. At the end of this learning phase, coefficients
needed to compute the credit risk of a given borrower are obtained. These are
then used to generate keys. In this regard, according to the FE scheme
principles, a trusted _key authority_ receives the coefficients and generates
two types of keys, i.e.: public/private keys for the encryption/decryption of
data, and operational keys needed to perform the functional computation on
encrypted data, which can only be used to decrypt the result of the
computation but not the data itself. At the end of this phase, the _X-Margin_
credit scoring application is finally configured. From now on, the customer
will encrypt the data along with the public keys received by the authority.
The ciphered information is then sent to the untrusted _X-Margin_ premises
running on cloud. Here, the credit risk associated to the borrower is computed
on ciphered data. It is important to notice that the computation of the credit
risk associated to the borrower does not include any confidential borrower’s
data. Only the result of this computation (i.e., the scoring evaluation) will
be accessible to _X-Margin_.

###  4.1 Architecture

Figure 2 shows the overall architecture of the FE-based credit scoring
solution, together with the steps performed during normal functioning.

Figure 2: The credit risk score architecture

  1. 1.

Data pre-processing: At startup, _X-Margin_ performs a pre-processing activity
on the data-set that will be used during the training phase. Modifications to
the dataset are needed to adapt the subsequent computation to the FE
requirements, and also to improve the accuracy of the neural network model,
such as:

    1. (a)

Removes columns and rows containing null values, discard columns with a high
percentage of null values, as well as rows with null values inside.

    2. (b)

Removes outliers.

    3. (c)

Adapt timestamps

    4. (d)

Scales and normalizes columns.

    5. (e)

Replaces object columns with dummy variables and one-hot encodes the output.

    6. (f)

Transform data in integer form in order to ensure compatibility with the FE
scheme properties,

  2. 2.

Neural Network Training: In this phase, the training phase takes place using
clear data. This is acceptable given that the leveraged dataset contains
anonymous entries. An ad-hoc neural network was defined. We leveraged and
adapted the _Adam optimization algorithm_ , with a learning rate of $10^{-4}$
and a batch size of $32$. Training epochs have been set to $50$. The neural
network has a single hidden layer and its activation layer is represented by a
_square element-wise_ , instead of _sigmoid_. This choice will be better
explained in the rest of this section.
Let $\underset{1\times n}{X}$ be our input vector, that is the borrower’s
record, $\underset{n\times d}{Pr}$ be the weight matrix of the first layer and
$\underset{d\times l}{D}$ be the weight matrix of the hidden layer. In our
case, $n=130$, $d=20$ and $l=2$. The output of the neural network is:

$\displaystyle prediction:\operatorname*{squareElemWise}(\underset{1\times
n}{X}\cdot\ \underset{n\times d}{Pr})\cdot\underset{d\times l}{D}$
$\displaystyle=\underset{1\times l}{DefaultScores}.$

The result of the classification is represented by a pair of scores, since
$l=2$, which are mutually exclusive and that are not normalized. In order to
get the final result in terms of probability, a softmax function has been
applied in the untrusted context side.

At the end of the training step, $Pr$ and $D$ are saved and used afterwards
for the encryption task and for deriving FE keys in the trusted context.

  3. 3.

Secret Key Generation The trusted authority generates a secret key for the
symmetric SGP scheme according to the FE scheme, that is:

$\displaystyle msk\leftarrow GenerateMasterKey()$ (2)

It then sends $msk$ to the _X-Margin_ user.

  4. 4.

Data Encryption The X-margin user uses $msk$ to encrypt the borrower’s data
$X$ and returns the appropriate ciphertext that is:

$\displaystyle c\leftarrow Encrypt(X,X,msk)$ (3)

Here, respect to the classical SGP scheme, we have replaced the parameter $Y$
by $X$.

  5. 5.

Encryption Projection The _X-Margin_ user takes the encryption $c$ and weight
matrix $Pr$ obtained at step 2 to produce a projection of $c$, that is:

$\displaystyle ProjC\leftarrow projectEncryption(c,Pr)$ (4)

$ProjC$ represents the encryption of $(Pr\cdot X)$, that is sent to the
untrusted context.

  6. 6.

Secret Key Projection The trusted authority takes the secret key $msk$
obtained at step 3 and the weight matrix $Pr$ obtained at step 2 to get a
projection of the secret key:

$\displaystyle ProjSecKey\leftarrow projectSecKey(msk,Pr)$ (5)

$ProjSecKey$ represents the secret key for encryption of $(Pr\cdot X)$.

  7. 7.

FE Key Generation The trusted authority provides also the FE keys to the
untrusted party to compute the credit risk of the borrower. There are two FE
keys: one used to decrypt the score of default and one used to decrypt the
score of not default of the borrower. Therefore, each FE key is used to
decrypt a different output $i$ of the neural network:

$\displaystyle feKey_{i}\leftarrow DeriveKey(ProjSecKey,Diag_{i})\forall i\in
l$ (6)

$DeriveKey$ accepts as parameter the secret key $ProjSecKey$, obtained at the
previous step, and the diagonal matrix $Diag_{i}$, that is the diagonalized
version of $D_{i}$, that represents the $i-th$ row of the matrix $D$. It
should be noted that $D_{i}$ is the vector containing the weights connected to
a single label.

Then, the trusted authority sends the obtained FE keys to the untrusted
context.

  8. 8.

Credit Score Computation The untrusted context, computes the credit risk
scores of the borrower through the FE key provided by the trusted authority at
the previous step. This means that for each label $i$ it evaluates the
function of $(Pr\cdot X)$, that is $(Pr\cdot X)^{T}\cdot Diag_{i}\cdot(Pr\cdot
X)$. In order to do that, it exploits the the following decryption primitive
of the SGP scheme:

$\displaystyle defaultScore_{i}$ $\displaystyle=(Pr\cdot X)^{T}\cdot
Diag_{i}\cdot(Pr\cdot X)$ (7) $\displaystyle\leftarrow
Decrypt(ProjC,feKey_{i},Diag_{i})\forall i\in l$

For each label $i$, $Decrypt$ accepts $ProjC$, that as we saw represents the
encryption of $(Pr\cdot X)$ sent by the _X-Margin_ user, the derived FE key
$feKey_{i}$ and the diagonal matrix $Diag_{i}$ sent by the trusted authority.

Since $l=2$, there are two functions: one that computes the score that the
borrower defaults and one that he/she doesn’t default. Such scores can be seen
as mutually exclusive, therefore we can apply the soft max function on them in
order to normalize the results and obtain the related probabilities.

$\underset{1\times
l}{DefaultProbabilities}=\operatorname*{softMax}(\underset{1\times
l}{Scores})$ (8)

Finally, the untrusted context sends back to the _X-Margin_ user the score
obtained at 8.

###  4.2 Details on the FE Scheme for Credit Risk Scoring

The aim of this section is to draw connections between the neural network
output function provided at 2 and the FE function at 1, so as to understand
what is the information needed to build the FE scheme.

Given the FE function at 1, we can transform it from a multivariate to a
single variable function.

$f(k):\underset{1\times d}{K^{T}}\cdot\underset{d\times
d}{\mathrm{F}}\cdot\underset{d\times 1}{K}$ (9)

From the other side, we can see the neural network function at 2 as the the
result obtained for each single label:

$defaultScore_{i}:\operatorname*{squareElemWise}(\underset{1\times
n}{X}\cdot\underset{n\times d}{Pr})\cdot\underset{d\times 1}{D_{i}}\forall
i\in l.$ (10)

Where $D_{i}$ is a vector containing the weights connected to a single label
$i$, $X$ is the borrower’s vector and $Pr$ is the weight matrix associated to
the first layer. Applying the following manipulation to each function $i$
obtained in 10, it is possible to get the FE function at 9:

$\displaystyle defaultScore_{i}$
$\displaystyle:\operatorname*{squareElemWise}({X}\cdot{Pr})\cdot{D_{i}}$ (11)
$\displaystyle=((Pr)^{T}\cdot(X)^{T})^{T}\cdot{Diag_{i}}\cdot((Pr)^{T}\cdot(X)^{T})$
$\displaystyle=K^{T}\cdot Diag_{i}\cdot K$ $\displaystyle\forall i\in l.$

Here, we have transformed the first matrix product, switching the operands and
applying the transpose on them. Indeed, we have removed the square element-
wise operation on it and, in order to keep the equality we have replaced
$D_{i}$ with its diagonalized version $Diag_{i}$ and we have multiplied by the
product $((Pr)^{T}\cdot(X)^{T})$. Finally, we have replaced the products with
the obtained vector $K$ in order to highlight the equivalence with the 9. The
custom matrix $F$ is the diagonal matrix $Diag_{i}$ that is different for each
label, while the other parts of the function don’t change.

We have shown that such neural network architecture computes the FE function
9, for each label $l$. Each function has, as variable, the matrix product
$((Pr)^{T}\cdot(X)^{T})$ named $K$, and produces as output respectively the
score that a borrower defaults and not. From now on $((Pr)^{T}\cdot(X)^{T})$
will be indicated without the transpose operations inside, in order to not
burden the discussion.

##  5 Experimental Performance Evaluation

We conducted an experimental evaluation of the privacy-preserving scoring
solution. The goal was to estimate the performance overhead given by the
adoption of the FE-based processing. More precisely, our focus was on the
execution time needed to encrypt borrowers’ data, and to compute the credit
risk score, i.e., the evaluation of the functional decryption occurring on _X-
Margin_ premises. These tests did not take into account the classification
algorithm accuracy since our main goal is to focus on the sole performance.

Figure 3: Encryption and credit scoring performance

We have evaluated our model on a Windows 10 machine equipped with an AMD Ryzen
3600X with 6-Core Processor at 3.80 GHz and 16GB of RAM. Execution times (in
ms) are the average of 5 repeated tests.
As a first experiment, we evaluated the encryption phase (i.e., steps 4 & 5)
by increasing the number of users in the system up to 1000 borrowers, and also
varying the number of borrowers’ attributes (in the range [5,25]).
Figure 3 shows the outcomes of the evaluation. It can be noticed that the
encryption is not significantly time consuming. The encryption of one borrower
in what we defined the worst situation —i.e., characterized by 50 attributes—
takes on average $52.3ms$, while in the best situation —i.e., 5 attributes— it
takes $14.3ms$. The execution time increases linearly with the number of
borrowers.
The second evaluation we made refers to the FE-based scoring computation time,
which is critical for the actual usability of the proposed solution. It is
important to notice that this operation includes both the actual functional
computation and the final result decryption. Figure 3 shows that the overhead
is significant, reaching in the worst condition —i.e., 50 attributes and 1000
users— a computation time of $~{}170s$. It must be noticed that in real
situations, the number of attributes is lower, in the order of 20.
Nevertheless, performance are still not acceptable. However, the type of job
we implemented with FE is highly parallelizable, and the deployment on
multiple nodes can make the adoption of the FE-based credit scoring solution
acceptable.

##  6 Conclusion

In this paper, we presented an innovative solution for privacy-preserving
credit risk scoring, which leverages the emerging _Functional Encryption_
cryptography that allows to learn the result of a specific function using only
encrypted data. We built a credit risk model using the quadratic polynomial FE
symmetric scheme SGP for the X-Margin Inc. company, whose case study was used
to validate the effectiveness of the proposed approach. Results from the
experimental campaign show that the solution performs well under certain
conditions, but the overhead needs to be properly managed in case of a real
production deployment. We discovered that with a limited number of borrowers’
attributes (e.g. $<20$) the encryption time and the classification time are
acceptable. Future developments of the current solution will be focused on
improving performance by evaluating new public key quadratic schemes (e.g.,
[11]), and setting up a multi-node parallel architecture.

## References

  * [1] Abdalla, M., Bourse, F., De Caro, A., Pointcheval, D.: Simple functional encryption schemes for inner products. In: Katz, J. (ed.) Public-Key Cryptography – PKC 2015. pp. 733–751. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)
  * [2] Abdalla, M., Catalano, D., Fiore, D., Gay, R., Ursu, B.: Multi-input functional encryption for inner products: Function-hiding realizations and constructions without pairings. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 597–627. Springer International Publishing, Cham (2018)
  * [3] Agrawal, S., Chase, M.: Fame: Fast attribute-based message encryption. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. p. 665–682. CCS ’17, Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3133956.3134014, https://doi.org/10.1145/3133956.3134014
  * [4] Boneh, D., Boyen, X.: Efficient selective-id secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) Advances in Cryptology - EUROCRYPT 2004. pp. 223–238. Springer Berlin Heidelberg, Berlin, Heidelberg (2004)
  * [5] Boneh, D., Sahai, A., Waters, B.: Functional encryption: Definitions and challenges. In: Ishai, Y. (ed.) Theory of Cryptography. pp. 253–273. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)
  * [6] Campanile, F., Coppolino, L., D’Antonio, S., Lev, L., Mazzeo, G., Romano, L., Sgaglione, L., Tessitore, F.: Cloudifying critical applications: A use case from the power grid domain. In: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP). pp. 363–370 (2017). https://doi.org/10.1109/PDP.2017.50
  * [7] Coppolino, L., D’Antonio, S., Formicola, V., Mazzeo, G., Romano, L.: Vise: Combining intel sgx and homomorphic encryption for cloud industrial control systems. IEEE Transactions on Computers pp. 1–1 (2020). https://doi.org/10.1109/TC.2020.2995638
  * [8] Dufour-Sans, E., Gay, R., Pointcheval, D.: Reading in the dark: Classifying encrypted digits with functional encryption. Cryptology ePrint Archive, Report 2018/206 (2018), https://eprint.iacr.org/2018/206
  * [9] Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing 45(3), 882–929 (2016). https://doi.org/10.1137/14095772X, https://doi.org/10.1137/14095772X
  * [10] Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology – CRYPTO 2013. pp. 479–499. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
  * [11] Gay, R.: A new paradigm for public-key functional encryption for degree-2 polynomials. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) Public-Key Cryptography – PKC 2020. pp. 95–120. Springer International Publishing, Cham (2020)
  * [12] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. pp. 169–178. STOC ’09, ACM, New York, NY, USA (2009). https://doi.org/10.1145/1536414.1536440
  * [13] Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security. p. 89–98. CCS ’06, Association for Computing Machinery, New York, NY, USA (2006). https://doi.org/10.1145/1180405.1180418, https://doi.org/10.1145/1180405.1180418
  * [14] Green, M.: A Few Thoughts on Cryptographic Engineering. . https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/ (2017)
  * [15] McKeen, F., Alexandrovich, I., Berenzon, A., Rozas, C.V., Shafi, H., Shanbhogue, V., Savagaonkar, U.R.: Innovative instructions and software model for isolated execution. In: Proceedings of the 2Nd International Workshop on Hardware and Architectural Support for Security and Privacy. pp. 10:1–10:1. HASP ’13, ACM, New York, NY, USA (2013). https://doi.org/10.1145/2487726.2488368


$\mathsf{e}\mathsf{LNDT}^{+}_{-}$ are translated to the two new initial
sequents $t\text{-}l$ and $t\text{-}r$, respectively, from Eq. 26 above. It
remains to simulate the logical steps.

The simulation of $\vee$ steps is immediate, since the $\cdot^{k}$-translation
commutes with $\vee$. Similarly for positive decisions on $p_{i}$. A left
positive decision step on $\overline{p}_{i}$,

$\Gamma,A\mbox{\Large$\,\rightarrow\,$}\Delta$$\Gamma,\overline{p}_{i},B\mbox{\Large$\,\rightarrow\,$}\Delta$
$\scriptstyle\overline{p}_{i}^{+}\text{-}l\;$ $\Gamma,A\overline{p}_{i}(A\vee
B)\mbox{\Large$\,\rightarrow\,$}\Delta$

is translated to the following derivation:

Proposition 6.8.Item 1 $(A\overline{p}_{i}(A\vee
B))^{k}\mbox{\Large$\,\rightarrow\,$}A^{k},\overline{p}_{i}^{k}$ Proposition
6.8.Item 2 $(A\overline{p}_{i}(A\vee
B))^{k}\mbox{\Large$\,\rightarrow\,$}A^{k},B^{k}$
$\Gamma^{k},\overline{p}_{i}^{k},B^{k}\mbox{\Large$\,\rightarrow\,$}\Delta$
$\scriptstyle\mathsf{cut}\;$ $\Gamma^{k},(A\overline{p}_{i}(A\vee
B))^{k},\overline{p}_{i}^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k}$
$\scriptstyle\mathsf{cut}\;$ $\Gamma^{k},(A\overline{p}_{i}(A\vee
B))^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k}$
$\Gamma^{k},A^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k}$
$\scriptstyle\mathsf{cut}\;$ $\Gamma^{k},(A\overline{p}_{i}(A\vee
B))^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k}$

A right positive decision rule on $\overline{p}_{i}$,

$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,A,\overline{p}_{i}$$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,A,B$
$\scriptstyle\overline{p}_{i}^{+}\text{-}r\;$
$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,A\overline{p}_{i}(A\vee B)$

is translated to the following derivation:

$\small{{{}{{}{}}}{}\vbox{\hbox{\kern
0.0pt\hbox{\vbox{\offinterlineskip\hbox{\hbox{\hbox{\hbox{\hbox{\kern
11.25pt\hbox{\vbox{\offinterlineskip\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$\Gamma^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k},\overline{p}_{i}^{k}$}}\kern
10.00002pt}\hbox{\kern
11.25pt\hbox{\vbox{\offinterlineskip\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$\Gamma^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k},B^{k}$}}\kern
10.00002pt}\hbox{\kern
0.0pt\hbox{\vbox{\offinterlineskip\hbox{\hbox{\hbox{\hbox{$\text{\lx@cref{creftype~refnum}{Truth-
refthr}.\lx@cref{creftype~refnum}{item:truth-refthr-1case-
impliesposdec}}$}}}}\kern 1.43518pt\kern-0.7pt\hbox{\kern 0.0pt\hbox
to0.0pt{\hss\hbox{$\smash{\lower-0.7pt\hbox{$$}}$}}\vbox{\vbox
to1.8pt{\vfill\hbox to323.90062pt{\hrulefill}\kern 1.0pt\hbox
to323.90062pt{\hrulefill}\vfill}}\hbox
to0.0pt{\hbox{$\smash{\lower-0.7pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern
1.43518pt\kern-0.7pt\hbox{\kern 120.30327pt\hbox{\hbox{$\kern
0.0pt\hbox{$\overline{p}_{i}^{k},B^{k}\mbox{\Large$\,\rightarrow\,$}A\overline{p}_{i}(A\vee
B)^{k}$}\kern 0.0pt$}}\kern 120.30327pt}}}\kern 0.0pt}}}}\kern
1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower
0.0pt\hbox{$\scriptstyle\mathsf{cut}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox
to275.08057pt{\hrulefill}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower
0.0pt\hbox{$$}}$}\hss}\kern 120.30327pt}\kern 1.43518pt\hbox{\kern
83.56229pt\hbox{\hbox{$\Gamma^{k},\overline{p}_{i}^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k},A\overline{p}_{i}(A\vee
B)^{k}$}}\kern 203.86555pt}}}\kern 0.0pt}}}}\kern 1.43518pt\hbox{\kern
0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower
0.0pt\hbox{$\scriptstyle\mathsf{cut}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox
to269.42722pt{\hrulefill}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower
0.0pt\hbox{$$}}$}\hss}\kern 203.86555pt}\kern 1.43518pt\hbox{\kern
85.35379pt\hbox{\hbox{$\Gamma^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A^{k},A\overline{p}_{i}(A\vee
B)^{k}$}}\kern 289.21935pt}}}\kern 0.0pt}\kern 10.00002pt}\hbox{\kern
0.0pt\hbox{\vbox{\offinterlineskip\hbox{\hbox{\hbox{\hbox{$\text{\lx@cref{creftype~refnum}{Truth-
refthr}.\lx@cref{creftype~refnum}{item:truth-refthr-0case-implies-
posdec}}$}}}}\kern 1.43518pt\kern-0.7pt\hbox{\kern 0.0pt\hbox
to0.0pt{\hss\hbox{$\smash{\lower-0.7pt\hbox{$$}}$}}\vbox{\vbox
to1.8pt{\vfill\hbox to326.90062pt{\hrulefill}\kern 1.0pt\hbox
to326.90062pt{\hrulefill}\vfill}}\hbox
to0.0pt{\hbox{$\smash{\lower-0.7pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern
1.43518pt\kern-0.7pt\hbox{\kern 127.43552pt\hbox{\hbox{$\kern
0.0pt\hbox{$A^{k}\mbox{\Large$\,\rightarrow\,$}A\overline{p}_{i}(A\vee
B)^{k}$}\kern 0.0pt$}}\kern 127.43552pt}}}\kern 0.0pt}}}}\kern
1.43518pt\hbox{\kern 96.60379pt\hbox to0.0pt{\hss\hbox{$\smash{\lower
0.0pt\hbox{$\scriptstyle\mathsf{cut}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox
to597.40408pt{\hrulefill}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower
0.0pt\hbox{$$}}$}\hss}\kern 127.43552pt}\kern 1.43518pt\hbox{\kern
352.71228pt\hbox{\hbox{$\Gamma^{k}\mbox{\Large$\,\rightarrow\,$}\Delta^{k},A\overline{p}_{i}(A\vee
B)^{k}$}}\kern 383.544pt}}}\kern 0.0pt}}}\qed$

###  6.5. Putting it all together

We are now ready to assemble the proof our main simulation result, Theorem
6.1. Recall that we are still working with the fixed
$\mathsf{e}\mathsf{LNDT}^{+}_{-}$ proof $P$ of a positive sequent
$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta$ from Section 6.4, over extension
axioms $\mathcal{A}=\\{e_{i}\mbox{\Large$\,\leftrightarrow\,$}A_{i}\\}_{i<n}$
and propositional variables $\mathbf{p}=p_{0},\dots,p_{m-1}$. We continue to
write $\mathbf{p}_{i}$ for $p_{0},\dots,p_{i-1},p_{i+1},\dots,p_{m-1}$, i.e.
$\mathbf{p}$ with $p_{i}$ removed.

######  Proposition 6.13.

For $k\geq 0$, there are polynomial size $\mathsf{e}\mathsf{LNDT}^{+}$ proofs
of,

(27) $\displaystyle
p_{i},t^{\mathbf{p}_{i}}_{k}\mbox{\Large$\,\rightarrow\,$}$ $\displaystyle
t^{\mathbf{p}}_{k+1}$ (28) $\displaystyle
t^{\mathbf{p}}_{k}\mbox{\Large$\,\rightarrow\,$}$ $\displaystyle
p_{i},t^{\mathbf{p}_{i}}_{k}$

over extension axioms $\mathcal{T}$.

###### Proof.

We derive Eq. 27 as follows:

$\begin{array}[]{r@{\ \seqar\ }ll}t^{p_{i}}_{1},t^{\mathbf{p}_{i}}_{k+1}\
\mbox{\Large$\,\rightarrow\,$}&t^{p_{i}\mathbf{p}_{i}}_{k+1}&\text{by
\lx@cref{creftype~refnum}{further-counting-results-splitting-and-
merging}.\lx@cref{creftype~refnum}{merging} }\\\ p_{i},t^{\mathbf{p}_{i}}_{k}\
\mbox{\Large$\,\rightarrow\,$}&t^{p_{i}\mathbf{p}_{i}}_{k+1}&\text{by
\lx@cref{creftype~refnum}{eq:p-implies-thrp1} and $\mathsf{cut}$}\\\ \
\mbox{\Large$\,\rightarrow\,$}&t^{\mathbf{p}}_{k+1}&\text{by
\lx@cref{creftype~refnum}{thresh-case-analysis} and
$\mathsf{cut}$}\end{array}$

We derive Eq. 28 as follows:

$\begin{array}[]{r@{\ \seqar\ }ll}t^{\mathbf{p}}_{k}\
\mbox{\Large$\,\rightarrow\,$}&t^{p_{i}\mathbf{p}_{i}}_{k}&\text{by
\lx@cref{creftype~refnum}{thresh-case-analysis}}\\\ \
\mbox{\Large$\,\rightarrow\,$}&t^{p_{i}}_{1},t^{\mathbf{p}_{i}}_{k}&\text{by
\lx@cref{creftype~refnum}{further-counting-results-splitting-and-
merging}.\lx@cref{creftype~refnum}{splitting} and $\mathsf{cut}$}\\\ \
\mbox{\Large$\,\rightarrow\,$}&p_{i},t^{\mathbf{p}_{i}}_{k}&\text{by
\lx@cref{creftype~refnum}{eq:p-implies-thrp1} and
$\mathsf{cut}$}\qed\end{array}$

######  Lemma 6.14.

For $k\geq 0$, there are polynomial size $\mathsf{e}\mathsf{LNDT}^{+}$ proofs
of,

$t^{\mathbf{p}}_{k},\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,t^{\mathbf{p}}_{k+1}$

over extension axioms $\mathcal{T}\cup\mathcal{A}^{k}$.

###### Proof.

By Lemma 6.12, we already have a polynomial-size proof
$\mathsf{e}\mathsf{LNDT}^{+}_{k}(P)$ proof $P^{k}$ of
$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta$. By definition of
$\mathsf{e}\mathsf{LNDT}^{+}_{k}(P)$, we construe $P^{k}$ as an
$\mathsf{e}\mathsf{LNDT}^{+}$ derivation of
$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta$ over extension axioms
$\mathcal{T}\cup\mathcal{A}^{k}$ from hypotheses:

(29) $\displaystyle
p_{i},t^{\mathbf{p}_{i}}_{k}\mbox{\Large$\,\rightarrow\,$}$ (30)
$\,\rightarrow\,$ $\displaystyle p_{i},t^{\mathbf{p}_{i}}_{k}$

We obtain the required proof by adding $t^{\mathbf{p}}_{k}$ to the LHS of each
sequent and $t^{\mathbf{p}}_{k+1}$ to the RHS of each sequent in $P^{k}$. Each
local inference step remains correct, except that some weakenings may be
required to repair initial steps. Finally we replace occurrences of the
hypotheses Eq. 29 and Eq. 30 above by the proofs of Eq. 27 and Eq. 28
respectively from Proposition 6.13. ∎

We are now ready to prove our main result, that $\mathsf{e}\mathsf{LNDT}^{+}$
polynomially simulates $\mathsf{e}\mathsf{LNDT}$ over positive sequents:

###### Proof of Theorem 6.1 .

By Corollary 6.5, without loss of generality let $P$ be a
$\mathsf{e}\mathsf{LNDT}^{+}_{-}$ proof of a positive sequent
$\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta$ over extension axioms
$\mathcal{A}$. By Lemma 6.14 we construct, for each $k\leq m+1$, polynomial-
size proofs of
$t^{\mathbf{p}}_{k},\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,t^{\mathbf{p}}_{k+1}$,
over $\mathcal{T}\cup\mathcal{A}^{k}$, and we simply ‘cut’ them all together
as follows:

Proposition 4.5.Item 1 $\mbox{\Large$\,\rightarrow\,$}t^{\mathbf{p}}_{0}$
Lemma 6.14
$t^{\mathbf{p}}_{0},\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,t^{\mathbf{p}}_{1}$
$\cdots$ Lemma 6.14
$t^{\mathbf{p}}_{m},\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta,t^{\mathbf{p}}_{m+1}$
Proposition 4.5.Item 3 $t^{\mathbf{p}}_{m+1}\mbox{\Large$\,\rightarrow\,$}$
$\scriptstyle(m+2)\mathsf{cut}\;$ $\Gamma\mbox{\Large$\,\rightarrow\,$}\Delta$

The resulting proof is an $\mathsf{e}\mathsf{LNDT}^{+}$ proof of the required
sequent, over extension axioms
$\mathcal{T}\cup\mathcal{A}^{0}\cup\mathcal{A}^{1}\cup\cdots\cup\mathcal{A}^{m+1}$.
Note that this set of extension axioms is indeed well-founded, since each
$\mathcal{A}^{k}$ is only used in distinct subproofs. ∎

## References

  * [1] Miklos Ajtai and Yuri Gurevich.  Monotone versus positive.  J. ACM, 34(4):1004–1015, October 1987.
  * [2] Albert Atserias, Nicola Galesi, and Ricard Gavaldà.  Monotone proofs of the pigeon hole principle.  Math. Log. Q., 47(4):461–474, 2001.
  * [3] Albert Atserias, Nicola Galesi, and Pavel Pudlák.  Monotone simulations of non-monotone proofs+.  J. Comput. Syst. Sci., 65(4):626–638, 2002.
  * [4] Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, and Alan R. Woods.  Exponential lower bounds for the pigeonhole principle.  In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 200–220. ACM, 1992.
  * [5] Sam Buss, Anupam Das, and Alexander Knop.  Proof complexity of systems of (non-deterministic) decision trees and branching programs.  In CSL, volume 152 of LIPIcs, pages 12:1–12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [6] Sam Buss, Valentine Kabanets, Antonina Kolokolova, and Michal Koucký.  Expander construction in VNC1.  In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 31:1–31:26, 2017\.
  * [7] Samuel R. Buss.  Towards NP-P via proof complexity and search.  Ann. Pure Appl. Log., 163(7):906–917, 2012.
  * [8] Stephen Cook and Phuong Nguyen.  Logical Foundations of Proof Complexity.  Cambridge University Press, 2010.
  * [9] Stephen A. Cook.  The complexity of theorem-proving procedures.  In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, page 151–158, New York, NY, USA, 1971. Association for Computing Machinery.
  * [10] Stephen A. Cook and Robert A. Reckhow.  The relative efficiency of propositional proof systems.  J. Symb. Log., 44(1):36–50, 1979.
  * [11] Anupam Das and Isabel Oitavem.  A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions.  In Dan Ghica and Achim Jung, editors, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), volume 119 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [12] Michelangelo Grigni.  Structure in monotone complexity.  PhD thesis, Citeseer, 1991.
  * [13] Michelangelo Grigni and Michael Sipser.  Monotone complexity, 1990.
  * [14] Johan Håstad, Ingo Wegener, Norbert Wurm, and Sang-Zin Yi.  Optimal depth, very small size circuits for symmetric functions in ac${}^{\mbox{0}}$.  Inf. Comput., 108(2):200–211, 1994.
  * [15] N. Immerman.  Nondeterministic space is closed under complementation.  In [1988] Proceedings. Structure in Complexity Theory Third Annual Conference, pages 112–115, 1988.
  * [16] Emil Jerábek.  A sorting network in bounded arithmetic.  Ann. Pure Appl. Logic, 162(4):341–355, 2011.
  * [17] M. Karchmer and A. Wigderson.  On span programs.  In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 102–111, 1993.
  * [18] Mauricio Karchmer and Avi Wigderson.  Monotone circuits for connectivity require super-logarithmic depth.  In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 539–550, New York, NY, USA, 1988. Association for Computing Machinery.
  * [19] Jan Krajícek.  Bounded arithmetic, propositional logic, and complexity theory, volume 60 of Encyclopedia of mathematics and its applications.  Cambridge University Press, 1995.
  * [20] Jan Krajícek.  The cook-reckhow definition.  CoRR, abs/1909.03691, 2019.
  * [21] Jan Krajíček.  Proof Complexity.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2019.
  * [22] Clemens Lautemann, Thomas Schwentick, and Iain Stewart.  Positive versions of polynomial time.  Inf. Comput., 147:145–170, 01 1998.
  * [23] Clemens Lautemann, Thomas Schwentick, and Iain A. Stewart.  On positive p.  In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, CCC ’96, page 162, USA, 1996. IEEE Computer Society.
  * [24] L. Levin.  Universal sequential search problems.  Problemy Peredachi Informatsii, 9:115–116, 1973.
  * [25] A. A. Markov.  Minimal relay-diode bipoles for monotonic symmetric functions.  Problemy Kibernetiki, 8:117–121, 1962.
  * [26] Pavel Pudlák and Samuel R. Buss.  How to lie without being (easily) convicted and the length of proofs in propositional calculus.  In Computer Science Logic, 8th International Workshop, CSL ’94, Kazimierz, Poland, September 25-30, 1994, Selected Papers, pages 151–162, 1994.
  * [27] Alexander A Razborov.  Lower bounds for the monotone complexity of some boolean functions.  In Soviet Math. Dokl., volume 31, pages 354–357, 1985.
  * [28] Alexander A Razborov.  Lower bounds on monotone complexity of the logical permanent.  Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485–493, 1985.
  * [29] Róbert Szelepcsényi.  The method of forced enumeration for nondeterministic automata.  Acta Inf., 26(3):279–284, 1988.
  * [30] Ingo Wegener.  Branching Programs and Binary Decision Diagrams.  SIAM, 2000.


# Learning Robust Policies for Generalized Debris Capture with an Automated
Tether-Net System

Chen Zeng1 , Grant Hecht1 , Prajit KrisshnaKumar1 , Raj K. Shah2 , Souma
Chowdhury3 , Eleonora M. Botta4
1 Ph.D. Student, Department of Mechanical and Aerospace Engineering2 M.S.
Student, Mechanical and Aerospace Engineering3 Associate Professor, Mechanical
and Aerospace Engineering, Corr. author email<EMAIL_ADDRESS>Assistant
Professor, Mechanical and Aerospace Engineering University at Buffalo,
Buffalo, NY, 14260

###### Abstract

Tether-net launched from a chaser spacecraft provides a promising method to
capture and dispose off large space debris in orbit. This tether-net system is
subject to several sources of uncertainty in sensing and actuation that affect
the performance of its net launch and closing control. Earlier reliability
based optimization approaches to design control actions however remain
challenging and computationally prohibitive to generalize over varying launch
scenarios and target (debris) state relative to chaser. To search for a
general and reliable control policy, this paper presents a reinforcement
learning framework that integrates a proximal policy optimization (PPO2)
approach with net dynamics simulations. The latter allows evaluating the
episodes of net-based target capture, and estimate the capture quality index
that serves as the reward feedback to PPO2. Here, the learnt policy is
designed to model the timing of the net closing action based on the state of
the moving net and the target, under any given launch scenario. A stochastic
state transition model is considered in order to incorporate synthetic
uncertainties in state estimation and launch actuation. Along with notable
reward improvement during training, the trained policy demonstrates capture
performance (over a wide range of launch/target scenarios) that is close to
that obtained with reliability based optimization run over an individual
scenario. ††**This work was supported by the NSF award CMMI 2128578. Any
opinions, findings, conclusions, or recommendations expressed in this paper
are those of the authors and do not necessarily reflect the views of the NSF.

Keywords: Active Debris Removal, Reinforcement Learning, Tether-Net,
Uncertainty

##  I Introduction

Active Debris Removal (ADR) using tether-net systems has been proposed and
studied as a promising solution to the space debris problem [1, 2, 3, 4, 5, 6,
7]. Among others, Botta et al. [8, 9, 10] conducted extensive research on the
dynamics of the deployment and capture phases of net-based debris removal
missions.

The majority of existing works are based on the assumptions of capturing a
specific target with ideal launch conditions, with a handful of pioneering
works (Salvi [11], Botta et al. [9, 8], and Endo et al. [12]) looking into the
robustness of deployment or capture under various net launch conditions in the
absence of a closing mechanism. In this type of mission, it is crucial to
guarantee a successful capture of the target in the presence of uncertainties,
and to ensure that the target remains wrapped by the net when the chaser tugs
it to its disposal orbit. These uncertainties can be attributed to measurement
errors, inaccuracies in net launch control, and to the estimation of the
debris and chaser vehicle inertial and attitude states. However, to date, very
little work has been performed to study the effects of uncertainties on the
system robustness, especially in the presence of a closing mechanism, with the
exception of work by Chen et al. [13].

The tether-net capture system presents a multidisciplinary robust design-
control problem with pertinent constraints under uncertainties. In our
preceding research[14], a reliability-based design optimization process was
proposed to optimize the launching and/or closure of the net under the
influences of uncertainties for a known fixed debris target. This process
models uncertainties and performs Bayesian optimization to determine launch
strategies that maximize the capture success rate. However, such a method only
searches for a single strategy that applies to a predefined debris status,
meanwhile requiring considerable computing power. Therefore, while it provided
valuable insight on robust debris capture under uncertainty, this approach is
ultimately not suitable as a flexible and flight-worthy solution.

Figure 1: Proposed Policy Learning Process for the Tether-Net System

Artificial Neural Networks (ANN) are playing an emerging role as decision-
support models in various intelligent autonomous systems [15]. As a universal
function approximator, an ANN is capable of mapping states to actions in
autonomous systems, a.k.a. a policy model. Various ANN fitting (learning)
methods have seen demonstrations on robotics and control applications. Popular
learning methods include Reinforcement Learning[16, 17], Supervised
Learning[18], Imitation Learning[19], Neuroevolution[20, 21], etc., among
which the advanced reinforcement learning[22] and neuroevolution[23] methods
are directly applicable to launching and wrapping control of tether-net
systems. These aforementioned machine learning methods bring capabilities of
adapting to system uncertainties, and selecting optimal actions (policies)
according to various debris characteristics. Computation-heavy reliability
analyses required in the optimizations can also be reduced, retaining the
computing load similar to that of reliability-based optimizations.

This paper proposes a machine-learning-based policy optimization of a one-shot
robotics system with environment adaptability and robustness under
uncertainties. The case study features the launching and wrapping process for
a tether-net space debris capture system. The machine learning framework
adapts to various environmental parameters (including net geometry and states
of the chaser and the target), considers multiple sources of uncertainties
(including inaccuracies of state estimation, errors in launching and wrapping
parameters, and sensing errors), and determines the optimal wrapping
parameters that maximize the probability of a successful capture. Environment
parameters are relative to the capture system (e.g., the mass of the corner
masses and the geometry of the net) and the state of the debris (e.g., the
distance to the chaser, its orientation, and its motion). The wrapping policy
comprises only triggering of the closing mechanism. The capture success is
evaluated by the Capture Quality Index, or CQI (interpreted later in the
manuscript). A case study scenario is presented with standalone wrapping
policy learning with programmed launching employing a state-of-the-art
learning technique, Proximal Policy Optimization 2 (PPO2)[22].

The remainder of this paper is organized as follows: In Section II, the
architecture of the simulator is presented briefly, together with the models
implemented for the different components of the system. In Section III, the
adopted machine-learning-based policy optimization is discussed. Section IV
presents validation of the optimization results, and Section V concludes the
paper with a discussion of results and limitations of the work, and associated
planned future work.

##  II Modeling: Tether-Net Launching and Wrapping Mechanics

Inherited from the preceding work[10, 24, 14], the modeled system comprises of
a chaser carrying a square-shaped net with 4 corner masses and a closing
mechanism around the perimeter. The tether-net system is simulated in Vortex
Studio, a powerful multibody dynamics simulation platform designed for real-
time simulation of complex mechanics. The net is modeled with the standard
lumped-parameter approach. The mass properties of the net are lumped into
small spherical rigid bodies placed at the physical knots of the net, herein
referred to as nodes. The axial stiffness and damping properties of the net’s
threads are represented with massless springs and dampers in parallel between
the nodes.

The chaser spacecraft is modeled as a cubic rigid body in the simulation. The
main tether, linking the net to the chaser, is modeled with a series of
slender rigid bodies, modeled as relaxed prismatic joints to simulate the
axial and bending stiffness and damping properties.

The closing mechanism applies a drawstring interlaced with the perimeter of
the net, as shown in Fig. 2. The drawstring passes through 8 nodes on the
perimeter as well as the 4 corner masses, and is winched independently from
the main tether[10]. When the closing mechanism is activated, constant forces
are made to act between each pair of adjacent nodes along the drawstring,
pulling the nodes together until contact. Upon contact, the node pairs are
locked to keep the mouth of the net closed for the rest of the maneuver.

The detailed design of the tether-net system is fixed as the derived result
from preceding work[14]. Table I lists the design parameters.

Figure 2: Sketch of the Modeled Tether-net System TABLE I: Design and properties of the tether-net system Variable | Description | Value
---|---|---
$L$ | Side Length of Net | 22.0 m
$L_{\texttt{mesh}}$ | Side Length of Mesh | 1.375 m
$r_{\texttt{n}}$ | Thread Radius | 6 mm
$m_{\texttt{n}}$ | Total Mass of Net | 100 kg
$m_{c}$ | Mass of Corner Mass | 10.0 kg
$\mathbf{V}_{\texttt{eb}}$ | Launching Velocity |  $[3.30,3.54,7.16]$ m/s

##  III Learning the Optimal Launching and Closing Policies

###  III-A Defining the learning task

Reinforcement learning models the actions as Markov Decision Processes [25]
(MDP) that comprise a comprehensive state space with a relatively compact
action space. There are 2 sets of actions (launching and closing) taking
effect on different stages of the capture operation, we are focusing on
closing within the scope of this paper.

The policy model of the closing signal is time variant, while the action
itself is a logical variable (boolean). The observations (state space) are
assumed to be estimated by employing readily available sensors, including: 1)
internal measurement units (IMUs), cameras, or Lidar mounted on the chaser
vehicle, 2) IMUs and cameras attached to the corner masses, as well as 3)
monitoring from the Earth. Therefore, the state space mainly consists of the
position, orientation, and velocities of the target, as well as the positions
of the corner masses of the net. In addition, the velocity of launching the
corner masses, the simulation time, and a flag indicating the actuation of
closing are also part of the observation. Some parameters, like the position
of the net’s center of mass, are obtained from the simulation for calculations
of the reward and the constraints, but excluded from the state space since
they are unattainable with the conceived sensors. Table II lists the state
space and the action space parameters.

TABLE II: Parameters of State and Action Spaces Type | Variable | Data Type | Boundaries
---|---|---|---
State | Time | Scalar |  $0$ to $120$ s
Target Coordinates ($p_{\texttt{target}}$) | Cartesian |  $[-10,-10,0]$ to $[10,10,50]$ m
Target Orientation | Euler angles |  $[0,0,0]$ to $[2\pi,2\pi,2\pi]$ rad
Target Angular Velocity | Euler angles |  $[-1,-1,-1]$ to $[1,1,1]$ rad/s
Pos. of Corner Masses (4) | Cartesian |  $[-22,-22,0]$ to $[22,22,72]$ m
Closure Flag ($f_{c}$) | Boolean | -
Launching Velocity | Cartesian |  $[1,1,1]$ to $[5,5,10]$ m/s
Action | Closing Signal | Boolean |  $0$ and $1$

The objective of reinforcement learning is to train the policy model to find
the optimal timing of sending the closing signal, based on observations
regarding the states of the net and the target. The policy model adapts a
reward function defined as:

$\displaystyle\underset{\mathbf{Q}}{\text{max:}}\quad$ $\displaystyle
R_{A}=\left(\sum_{t_{0}}^{t_{\texttt{close}}}r(t)+r_{\texttt{end}}\right)/n_{\texttt{steps}}$
(1a) where: $\displaystyle
r(t)=\begin{cases}w_{1}\cdot\left(C_{1}-\left|\frac{V_{\texttt{n}}-V_{\texttt{t}}}{V_{\texttt{t}}}\right|\right)+w_{2}\cdot\left(C_{2}-\left|\frac{S_{\texttt{n}}-S_{\texttt{t}}}{S_{\texttt{t}}}\right|\right)+w_{3}\cdot\left(C_{3}-\left|\frac{q_{\texttt{n}}}{q_{\texttt{t}}}\right|\right)+w_{4}\cdot(N_{\texttt{L}}-C_{4})+\dots\\\
\hskip
25.60747pt0.4\cdot(\min(t,t_{1})-4.6)-(0.12\cdot(\max(t,t_{2})-t_{2}))^{2}+C_{5}\quad\text{(no
premature closing)}\\\ -(t_{1}-t_{\texttt{close}})^{2}\hskip
200.59192pt\text{(with premature closing)}\end{cases}$ (1b) $\displaystyle
r_{\texttt{end}}=\begin{cases}w^{\prime}_{1}\cdot\left(C^{\prime}_{1}-\left|\frac{V^{\prime}_{\texttt{n}}-V_{\texttt{t}}}{V_{\texttt{t}}}\right|\right)+w^{\prime}_{2}\cdot\left(C^{\prime}_{2}-\left|\frac{S^{\prime}_{\texttt{n}}-S_{\texttt{t}}}{S_{\texttt{t}}}\right|\right)+w^{\prime}_{3}\cdot\left(C^{\prime}_{3}-\left|\frac{q^{\prime}_{\texttt{n}}}{q_{\texttt{t}}}\right|\right)+\dots\\\
\hskip
157.91278ptw^{\prime}_{4}\cdot(N^{\prime}_{\texttt{L}}-C^{\prime}_{4})+C^{\prime}_{5}\quad\text{(closing
started before 60 s)}\\\ C_{6}\hskip 273.14645pt\text{(not closing by 60
s)}\end{cases}$ (1c)

In which $\mathbf{Q}$ represents the policy model; $R_{A}$ represents the
episodic (mean) reward; $t$ represents the simulation time; $t_{0}$ stands for
the initial and final time steps; $t_{\texttt{close}}$ represents the time
when the closing signal is issued; $t_{1}$ and $t_{2}$ are manually configured
time triggers; $n_{\texttt{steps}}$ stands for the number of (learning) steps
in the episode; $r(t)$ represents the reward at time step $t$;
$r_{\texttt{end}}$ represents the bonus end-of-episode reward;
$V_{\texttt{n}}$, $S_{\texttt{n}}$, and $q_{\texttt{n}}$ stand for the
enclosed volume, surface area, and the center-of-mass position of the net at
time $t$; $V^{\prime}_{\texttt{n}}$, $S^{\prime}_{\texttt{n}}$, and
$q^{\prime}_{\texttt{n}}$ stand for those at time ($t_{\texttt{close}}+20$
seconds); $V_{\texttt{t}}$, $S_{\texttt{t}}$, and $q_{\texttt{t}}$ stand for
the volume, surface area, and the center-of-mass position of the target;
$N_{\texttt{L}}$ is the number of locked node-pairs around the edge (12 pairs
in total); $C_{1}$ through $C_{6}$, as well as $w_{1}$ through $w_{4}$ are
tuning weights, in addition to $C^{\prime}_{1}$ through $C^{\prime}_{5}$ and
$w^{\prime}_{1}$ through $w^{\prime}_{4}$; $f_{C}$ refers to the closure flag.

A premature closing is defined as:

$\begin{cases}\text{{True} }&\text{if
}(f_{C}=1)\cap(t_{\texttt{close}}<15\text{ s})\cap\dots\\\
&[(q_{\texttt{n}}(t_{\texttt{close}})>12\text{
m})\cup(|\overline{p}_{\texttt{cm}}-p_{\texttt{target}}|>10\text{ m})]\\\
\text{{False} }&\text{otherwise}\end{cases}$ (2)

where $\overline{p}_{\texttt{cm}}$ represents the mean position of the corner
masses, and $p_{\texttt{target}}$ represents the position of the target.

A crucial part of the reward is largely dependent on the distances between the
net and the target in terms of position, surface area, and volume. Such
formulation is inspired by the Capture Quality Index (CQI)[26], which
estimates the successfulness of a capture with the aforementioned
measurements. The number of locked node-pairs ($N_{\texttt{L}}$) indicates the
possibility of the target slipping out of the net, and is also considered in
the formulation for added robustness.

The conditional formulations in the reward function ensures some substantial
penalties for premature closing (too far away from the target) or delayed
closing (too late), and a substantial bonus ($C^{\prime}_{5}$) for
appropriately-timed closing. Timing is vital for a successful capture, but the
time-variant nature of the closing signal makes it difficult for the policy
model to learn to avoid premature action. A reward function solely based on
the CQI is insufficient to distinguish between an obvious failure and a
possibly successful scenario, hence the added penalty that overrules the
reward is necessary to avoid possible exploitation of the CQI formulation.
Since the reward function returns positive rewards through the majority of an
episode, the policy model could exploit the formulation by not closing at all.
The bonus reward ($C^{\prime}_{5}$) for well-timed closing and the penalty
($C_{6}$) for not closing at all would work together to prevent the policy
model from refusing to close throughout the episode.

We train the policy model in stages controlled by step count, while adjusting
the tuning weights as the stages progress. The CQI part of the end-of-episode
reward $r_{\texttt{end}}$ is gradually magnified as the policy model learns to
avoid premature closing. Penalty for delayed closing ($C_{6}$) is inactive
until the policy model learns to refuse to close. Table III lists the values
of the adjustable parameters applied through various stages of training.

TABLE III: Coefficients for the Reward Formulation Unchanged | $w_{1}$ | $w_{2}$ | $w_{3}$ | $w_{4}$ | $C_{1}$ | $C_{2}$ | $C_{3}$ | $C_{4}$ | $C_{5}$ | $t_{1}$ | $t_{2}$
---|---|---|---|---|---|---|---|---|---|---|---
0.025 | 0.025 | 0.2 | 0.125 | 3 | 3 | 5 | 2 | 2 | 15 | 20
| $w^{\prime}_{1}$ | $w^{\prime}_{2}$ | $w^{\prime}_{3}$ | $w^{\prime}_{4}$ | $C^{\prime}_{1}$ | $C^{\prime}_{2}$ | $C^{\prime}_{3}$ | $C^{\prime}_{4}$ | $C^{\prime}_{5}$ | $C_{6}$ |
0 to 66,000 steps | 0.05 | 0.05 | 0.4 | 0.125 | 3 | 4 | 6 | 0 | 50 | 0 |
66,001 to 300,000 steps | 0.1 | 0.1 | 0.8 | 0.25 | 3 | 3 | 6 | 0 | 50 | 0 |
300,001 to 800,000 steps | 1 | 1 | 8 | 2.5 | 3 | 3 | 6 | 0 | 50 | -50 |
800,001 to 1,500,000 steps | 2 | 2 | 16 | 5 | 3 | 3 | 3 | 2 | 100 | -50 |

Two scenarios were conceived: 1) learning a standalone wrapping policy while
launching is programmed; 2) learning launching and wrapping policies
simultaneously. Scenario 2 calls for training two policy models in one
simulation, which brings in questions like reward crediting [27] and the
orders of execution. Limited by time and computing constraints, the case study
in this paper is confined to scenario 1). The programmed launching policy for
scenario 1 was presented in a previous work [14] (values listed in Table I).

###  III-B Design of experiments and uncertainty modeling

The Design of Experiments samples a range of the target’s distance, initial
orientation, and initial rotating angular velocity. Every episode of training
is sampled with random choices of the forementioned initial states of the
target. Table IV lists the variations of DoE.

TABLE IV: Initial States of the Target Name | Minimum | Maximum
---|---|---
Dist. to chaser | 25 m | 35 m
Orientation |  $[0,0,0]$ rad |  $[\frac{\pi}{2},0,0]$ rad
Angular Vel. |  $[0,-\frac{\pi}{18},-\frac{\pi}{18}]$ rad/s |  $[0,\frac{\pi}{18},\frac{\pi}{18}]$ rad/s

The Simulation cannot directly simulate the onboard sensors and actuators in
high fidelity, therefore uncertainties are modeled in sensing, state
estimation, and actuation of the system by applying stochastic noises to the
parameters. Sources of uncertainties include: 1) estimated state of the debris
target and the corner masses of the net, 2) velocity of launching the net, 3)
timing of triggering the closing mechanism, and uniquely 4) soft dynamics of
the net. The uncertainty of the net dynamics is aleatoric and unavoidable,
while the majority of the uncertainties in estimation and control are
epistemic [28].

Figure 3: The Workflow of Reinforcement Learning on the Tether-Net Capture
Mission

Gaussian noises modeled after Table V are applied upon the observed parameters
from the simulation before delivery to the learning algorithm. Noises of the
constant parameters (target orientation and launching velocity) are one-shot,
while those of the continuously monitored parameters are sampled at every time
step of learning.

TABLE V: Noise Levels of Modeled Uncertainties Sampled During: | Noise Source | Data Type | Margin of Error ($2\sigma$)
---|---|---|---
Step-wise | Target Orientation | 3D Vector |  $\pm[\pi/36,\pi/36,\pi/36]$ rad
Target Angular Velocity | 3D Vector |  $\pm[\pi/36,\pi/36,\pi/36]$ rad/s
Corner Masses Position | 3D Vector |  $\pm[0.1,0.1,0.25]$ m
Only Once | Target Position (CoM) | 3D Vector |  $\pm[0.1,0.1,0.25]$ m
Launching Velocity | 3D Vector |  $\pm[0.05,0.05,0.1]$ m/s

###  III-C Learning and validation techniques

Herein, the learning technique known as Proximal Policy Optimization 2 (PPO2)
from stable baselines [29] is applied within a case study to provide an
opportunity to evaluate and compare advanced reinforcement learning with prior
results obtained by robust optimization under a fixed environment [14]. PPO2
is a state-of-the-art actor-critic reinforcement learning method which has
demonstrated high efficiency, wide adaptability, and robust reliability [30].

PP02 employs a gradient update based on the experiences collected on the mini-
batch of interactions with the environment. Upon update completion, the
experiences collected are then discarded and the next update is based on new
experiences. PPO2 has been proven to demonstrate less variance during the
training process when compared to alternative learning techniques which
ensures a smoother training process [31]. A multi-layer perceptron model
consisting of 2 layers with 64 neurons is used within the deep Q network. This
network is trained for 500 episodes and the trained policy is then validated
for 100 episodes. Parameters used for the learning process are provided in
Table VI.

TABLE VI: Reinforcement Learning Parameters Algorithm | PPO2
---|---
Neural Network type | Multi-Layer Perceptron
Total Timesteps | 1,500,000
Learning Rate | 2.5e-4
Discount Factor | 0.999
Number of Steps | 128
Entropy Coefficient | 0.01
Clip Range | 0.2
Value Function Coefficient | 0.5
Max. Gradient Norm | 0.5

For the final evaluation, a reliability sampling process was performed to
examine the probability of success for the trained policy model. This involved
a Monte Carlo sampling process to sample the impact of the uncertainties, in
which $N=100$ is number of independent simulations executed with the trained
policy model. The evaluated probabilities of success are then compared to the
success rate achieved by robust optimization under a fixed environment[14].

##  IV Results

The learning trials were executed on a Windows workstation with 16 CPU cores
with parallel computing with 30 workers for the episode evaluations. The
learning process progresses in 20,000-to-500,000-step stages as we examine the
learning rate and adjust the reward weights in between stages. By the
conclusion of this paper, a total of 1.5 million steps of learning have been
finished. The time cost of learning was 41.2 hours.

The history of episodic reward from one of the 30 workers is displayed in
Figure 4. This specific worker finished 549 episodes in 46,437 steps. Since
the episode tends to extend longer as the learning progresses, the later 89%
of the steps only contributed to 80 episodes. The lowest episodic reward is
-69.0, and the highest episodic reward is 9.7.

The episodic reward plot shows strong fluctuations, indicating the learning
rate is unstable throughout the learning process and has yet to approach
convergence. The 10-episode mean reward is also shown within the figure, which
provides a more stable indication of the range and the trend of the reward
values. The policy model received negative rewards throughout most of the
episodes, but just managed to receive near-zero or positive rewards after 460
episodes. The trend of the rewards and the fluctuations are both signs of
insufficient training. The episodic mean reward is unsuitable as a direct
measurement of capture quality (for the successfully closed cases),
considering the lengths of episodes fluctuate in a wide margin.

Figure 4: History of Episodic Rewards

To evaluate the quality of the trained policy models, we tested all the neural
networks obtained via different stages of learning with a Monte Carlo sample
set sampled from the same initial states as shown in Table IV and applied the
same level of uncertainties as shown in Table V. The best-performing policy
model so far is from the end of 120,000 steps, which is compared to results
from the previous work. The CQI values of the test result are calculated and
compared with an optimized closing time under a static initial condition
obtained from the predeceasing paper[14] (only closing was optimized for a
single initial state). The mean CQI value of the policy model tests is 1.035,
and the percentage of the samples with CQI values lower than 2 (seen as secure
captures) is 94%. In contrast, the optimized fixed close timing managed to
achieve 96% success rate and a mean CQI of 1.010 for the single initial state.
The policy model of closing achieves a high success rate in a range of initial
states, near that for the fixed close timing optimized for a single initial
state, suggesting the policy model is approaching the maximal possible
reliability. The policy model should keep improving if given more learning
steps, and we expect the converged policy model to outperform the optimization
results, especially in situations with large deviations.

##  V Concluding Remarks

A machine-learning-based tether-net system wrapping policy optimization for
ADR with environment adaptability and robustness under uncertainties was
proposed and a trade study involving standalone wrapping policy learning with
programmed launching employing a state-of-the-art learning technique, Proximal
Policy Optimization 2 (PPO2), was performed.

Despite cutting off the learning process early, evaluation of the policy
learning results shows that the proposed approach for wrapping policy learning
proves promising, resulting in capture reliability comparable to earlier
robust Bayesian optimization which involved a similar computational load,
despite optimizing the wrapping strategy under a much wider range of state
scenarios with larger uncertainty.

Future work will investigate standalone launching policy learning with
programmed wrapping, and simultaneous learning of launching and wrapping
policies. Additional machine learning tools, including reinforcement learning
algorithms and advanced neruoevolution techniques[23] will also be applied for
experiments.

## References

  * [1] Guang, Z. and Jing-rui, Z., “Space tether net system for debris capture and removal,” 2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics, Vol. 1, IEEE, 2012, pp. 257–261.
  * [2] Wormnes, K., De Jong, J., Krag, H., and Visentin, G., “Throw-nets and tethers for robust space debris capture,” International Astronautical Congress, 2013.
  * [3] Benvenuto, R., Salvi, S., and Lavagna, M., “Dynamics analysis and GNC design of flexible systems for space debris active removal,” Acta Astronautica, Vol. 110, 2015, pp. 247–265.
  * [4] Botta, E., Deployment and Capture Dynamics of Tether-nets for Active Space Debris Removal, Ph.D. thesis, McGill University Libraries, 2018.
  * [5] Hausmann, G., Haarmann, R., Wieser, M., Brito, A., and Scheper, M., “OHB Concepts for Active Space Debris Removal and On-Orbit Servicing,” 66th International Astronautical Congress, IAC, 2015.
  * [6] Benvenuto, R. and Carta, R., Implementation of a net device test bed for space debris active removal feasibility demonstration, Ph.D. thesis, MS thesis, Politecnico di Milano, 2012.
  * [7] BOMBELLI, A., “Multidisciplinary design of a net-based device for space debris active removal,” 2012.
  * [8] Botta, E. M., Sharf, I., and Misra, A., “Evaluation of net capture of space debris in multiple mission scenarios,” 26th AAS/AIAA Space Flight Mechanics Meeting, Napa, CA, AAS, 2016, pp. 16–254.
  * [9] Botta, E. M., Sharf, I., and Misra, A. K., “Energy and momentum analysis of the deployment dynamics of nets in space,” Acta Astronautica, Vol. 140, 2017, pp. 554–564.
  * [10] Botta, E. M., Sharf, I., and Misra, A. K., “Simulation of tether-nets for capture of space debris and small asteroids,” Acta Astronautica, Vol. 155, 2019, pp. 448–461.
  * [11] SALVI, S., “Flexible devices for active space debris removal: the net simulation tool,” 2014.
  * [12] Endo, Y., Kojima, H., and Trivailo, P. M., “Study on acceptable offsets of ejected nets from debris center for successful capture of debris,” Advances in Space Research, Vol. 66, No. 2, 2020, pp. 450–461.
  * [13] Chen, S., Woods, C. T., Boonrath, A., and Botta, E. M., “Analysis of the robustness and safety of net-based debris capture,” AIAA SCITECH 2022 Forum, 2022, p. 1001.
  * [14] Kalpeshkumar Shah, R., Zeng, C., Botta, E., and Chowdhury, S., “Reliability-Based Launch and Closure Optimization for a Net-Based Space Debris Capture System,” 2021 Multidisciplinary Analysis and Optimization Conference, AIAA AVIATION Forum (accepted), Jun 2021.
  * [15] Dounis, A. I. and Caraiscos, C., “Advanced control systems engineering for energy and comfort management in a building environment—A review,” Renewable and Sustainable Energy Reviews, Vol. 13, No. 6-7, 2009, pp. 1246–1261.
  * [16] Baxter, J., Tridgell, A., and Weaver, L., “Knightcap: a chess program that learns by combining td (lambda) with game-tree search,” arXiv preprint cs/9901002, 1999.
  * [17] Peters, J., Vijayakumar, S., and Schaal, S., “Reinforcement learning for humanoid robotics,” Proceedings of the third IEEE-RAS international conference on humanoid robots, 2003, pp. 1–20.
  * [18] Caruana, R. and Niculescu-Mizil, A., “An empirical comparison of supervised learning algorithms,” Proceedings of the 23rd international conference on Machine learning, 2006, pp. 161–168.
  * [19] Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C., “Imitation learning: A survey of learning methods,” ACM Computing Surveys (CSUR), Vol. 50, No. 2, 2017, pp. 1–35.
  * [20] Risi, S. and Togelius, J., “Neuroevolution in games: State of the art and open challenges,” IEEE Transactions on Computational Intelligence and AI in Games, Vol. 9, No. 1, 2015, pp. 25–41.
  * [21] Hansen, N., Müller, S. D., and Koumoutsakos, P., “Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES),” Evolutionary computation, Vol. 11, No. 1, 2003, pp. 1–18.
  * [22] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O., “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347, 2017.
  * [23] Behjat, A., Chidambaran, S., and Chowdhury, S., “Adaptive genomic evolution of neural network topologies (agent) for state-to-action mapping in autonomous agents,” 2019 International Conference on Robotics and Automation (ICRA), IEEE, 2019, pp. 9638–9644.
  * [24] Botta, E. M., Deployment and capture dynamics of tether-nets for active space debris removal, Ph.D. thesis, McGill University, Montreal, QC, 2017.
  * [25] Bellman, R., “A Markovian decision process,” Journal of mathematics and mechanics, Vol. 6, No. 5, 1957, pp. 679–684.
  * [26] Barnes, C. M. and Botta, E. M., “A quality index for net-based capture of space debris,” Acta Astronautica, Vol. 176, 2020, pp. 455–463.
  * [27] Nguyen, D. T., Kumar, A., and Lau, H. C., “Credit assignment for collective multiagent RL with global rewards,” 2018.
  * [28] Hora, S. C., “Aleatory and epistemic uncertainty in probability elicitation with an example from hazardous waste management,” Reliability Engineering & System Safety, Vol. 54, No. 2-3, 1996, pp. 217–223.
  * [29] Hill, A., Raffin, A., Ernestus, M., Gleave, A., Kanervisto, A., Traore, R., Dhariwal, P., Hesse, C., Klimov, O., Nichol, A., Plappert, M., Radford, A., Schulman, J., Sidor, S., and Wu, Y., “Stable Baselines,” https://github.com/hill-a/stable-baselines, 2018.
  * [30] Ilyas, A., Engstrom, L., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., and Madry, A., “Are Deep Policy Gradient Algorithms Truly Policy Gradient Algorithms?” CoRR, Vol. abs/1811.02553, 2018.
  * [31] Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D., “Deep Reinforcement Learning that Matters,” CoRR, Vol. abs/1709.06560, 2017.