\section{Introduction}

Initial value problems of autonomous differential equations arise in many applications and define a dynamical system. Many tools have been developed to study the long-term behaviour of solutions and classify different behaviour depending on the initial conditions. One of the classical and fundamental tools is a Lyapunov function, which is a generalization of the energy in a dissipative system. It is a scalar-valued function, which is non-increasing along orbits of the dynamical system.
Complete Lyapunov functions, introduced by \cite{Auslander1964,Conley1978}, are scalar-valued functions, which are strictly decreasing along orbits outside the chain-recurrent set and satisfy additional properties for the values on the chain-recurrent set.

A complete Lyapunov function
 describes the qualitative behaviour of orbits by separating the phase space into two disjoint areas with fundamentally different behaviour of the flow: the  chain-recurrent set and its complement, where the flow is gradient-like. On the chain-recurrent set the flow is (almost) recurrent, it contains all equilibria, periodic and almost periodic orbits, as well as local attractors and repellers. The flow on the chain-recurrent set is sensitive to infinitesimal perturbations, while the gradient-like flow is robust to infinitesimal perturbations.
 Moreover, complete Lyapunov functions reveal stability properties of the chain transitive components of the chain recurrent set as well as the flow between them.

  If the complete Lyapunov function is differentiable,
  then the conditions can be expressed by the derivative along solutions, the orbital derivative: points with vanishing orbital derivative characterize the chain-recurrent set, while the orbital derivative is strictly negative in the area of gradient-like flow.

 The existence of  complete Lyapunov functions was first shown on  compact phase spaces
 \cite{Conley1978} and later on noncompact phase spaces  \cite{Hurley1991,hurley95,hurley1998,complete2011patrao}. The existence of $C^\infty$ complete Lyapunov functions on compact state spaces was shown in \cite{FaPa2019smoothingLya}, and in noncompact spaces in \cite{SuHa2020complya}. The latter proof used the connection of complete Lyapunov functions to  time functions in general relativity \cite{Hawking};  this relation was first noted by \cite{Fathi2012} and further explored in \cite{BeSu2018smmothConeLya}, which gave the first general existence results for $C^\infty$  Lyapunov functions
 on arbitrary  manifolds.

 The main condition on complete Lyapunov functions is that the orbital derivative is strictly negative in the gradient-flow part, i.e.~the complement of the chain-recurrent set. Hence, complete Lyapunov functions are  not unique and  a natural question is whether one can prescribe the values of the orbital derivative by a given negative function on the gradient-flow part.

 The main result of the paper is that, indeed, the orbital derivative can be prescribed by an arbitrary, sufficiently smooth function on any compact set, which is contained in the complement of the chain-recurrent set, see Theorem \ref{T1}. In the proof we first show that we can reduce the problem to the case where the orbital derivative is fixed to $-1$ and then we modify an existing $C^\infty$ complete Lyapunov function on the compact set, while preserving it away from it; this is achieved by modifying it on flow boxes.
The resulting complete Lyapunov function is as smooth as the vector field defining the system.

 This result has implications on the numerical construction of complete Lyapunov functions. There exist a number of numerical approaches to compute complete Lyapunov functions. One approach  divides the phase space into cells and computes the flow between these cells to construct a complete Lyapunov function \cite{Ban2006}.
Other approaches, however, fix the orbital derivative by a prescribed function and use collocation methods to solve the resulting partial differential equation for the complete Lyapunov function \cite{paper1,completeAGH2019} -- or optimization methods with a mixture of equality and inequality constraints \cite{min-quad}.  So far no existence result for these approaches using equations was available. The results of this paper can be used to ensure that numerical methods for constructing complete Lyapunov functions with prescribed orbital derivative are successful, and thus they deliver a theoretical foundation for these methods.

Let us give an overview of the paper: In Section \ref{def} we define complete Lyapunov functions and state the main result. In Section \ref{proof} we prove the results, before we conclude the paper in Section \ref{sec:conclusions}.

\section{Definition \& Main Result}
\label{def}
Let $U\subset \mathbb R^n$ be open and let $X\colon U\to\mathbb R^n$ be $C^l$ with $l\in\mathbb N\cup\{\infty\}$, where $\mathbb N:=\{1,2,3,4,5,\ldots\}$.
We consider the dynamical system defined by  solutions of the  ODE $\dot{x}=X(x)$.

\begin{definition}
The {\bf local flow} of $X$ is the map $\Phi\colon \Omega\to U$, $(t,p)\mapsto \Phi_t(p)$ such that
\begin{itemize}
\item[(i)] $\Omega\subset \mathbb R\times U$ is open with $\{0\}\times U\subset \Omega$.
\item[(ii)] For every $p\in U$ the orbit $t\mapsto \Phi_t(p)$ is the unique maximally extended solution to the initial value problem
\[
\begin{cases}
\frac{\partial}{\partial t}\Phi_t(p)&=X(\Phi_t(p)) \\
\Phi_0(p)&=p.
\end{cases}
\]
\end{itemize}
\end{definition}

\begin{remark}
\begin{itemize}
\item[(1)] The attribute ``local'' for the flow refers to local in time. We do not assume  that flowlines of $X$ exist on the whole of $\mathbb R$ for all initial values $p\in U$.
\item[(2)] With the regularity assumption on $X$ the existence of $\Phi$ is implied by the Theorem of Picard-Lindel\"off. Note that the local flow
enjoys the same regularity as the generator $X$, i.e. $\Phi\in C^l$.
\end{itemize}
\end{remark}

Let us now define the chain recurrent set. We denote by $\|.\|$ the Euclidian norm on $\mathbb R^n$.

\begin{definition}
Let $T>0$ and $\e \colon U\to (0,\infty)$ be continuous.
A finite collection of points $p_0,\ldots,p_m\in U$ $(m\ge 1)$ is an ${(\varepsilon,T)}${\bf-chain} if there exist $t_i\ge T$ with
\[
\|\Phi_{t_i}(p_i)-p_{i+1}\|\le \e(\Phi_{t_i}(p_i))
\]
for all $0\le i\le m-1$.
\end{definition}

\begin{definition}
A point $p\in U$ is {\bf chain recurrent for} $\mathbf{X}$ if  for all $T>0$ and all continuous $\e \colon U\to (0,\infty)$  there exists an $(\e,T)$-chain
$p_0=p,p_1,\ldots, p_m=p$.
\end{definition}

Denote by
$$\mathcal{R}_{X}$$
the set of chain recurrent points for $X$.

Recall that the {\bf chain transitive components} of the chain recurrent set are the equivalence classes with respect to the equivalence relation $\sim$, where
$p\sim q$ for two points $p,q\in \mathcal{R}_X$ if there exists $T>0$ such that for all continuous $\e\colon U\to (0,\infty)$ there is an $(\e,T)$-chain
$p=p_0,p_1,\ldots,p_m=p$ containing $q$.

The following definition of Lyapunov functions is very closely related to \cite[Definition 1.4]{BeSu2018smmothConeLya}. Here we omit the smoothness
of the functions in favor of a lower regularity and consider only the case of vector fields. Recall that a point $p\in U$ is regular for a differentiable function
$f\colon U\to \mathbb R$ if $\nabla f(p)\neq 0$.

\begin{definition}
\label{coneLyaXYX}
Let $X\colon U\to\mathbb R^n$ be $C^l$ with $l\in\mathbb N\cup\{\infty\}$. The  function $\tau:U\to \mathbb R$ is a {\bf Lyapunov function for $\mathbf{X}$} if it is $C^l$ regular,
\[\dot{\tau}(p):=
\nabla\tau(p)\cdot X(p)\leq 0
\]
for each $p\in U$, and if, at each regular point $p$ of $\tau$, we have
$\dot{\tau}(p)<0$.
\end{definition}

\begin{remark}
This definition of a Lyapunov function is not the usual one, but particulary useful when studying numerical methods for the computation of Lyapunov functions; c.f.~\cite{opti} where similar Lyapunov functions are referred to as
\it{complete Lyapunov function candidates}.  Note that a classical $C^1$ Lyapunov function for one attractor is also a Lyapunov function in the sense above and a Lyapunov function as above, with the additional assumption
 that it is constant on the attractor where it attains its strict minimum, is a classical weak, i.e.~non-strict, Lyapunov function.
\end{remark}

In order to state the theorem we adopt the notion of complete Lyapunov function from \cite[II.\S6.4]{Conley1978}, see also
\cite[Definition 4.5]{SuHa2020complya}:

\begin{definition}
\label{comLyaDef}
A Lyapunov function $\tau\colon U\to \mathbb R$ for the vector field $X$ is {\bf complete} if it is strictly decreasing
along orbits outside of $\mathcal{R}_X$  and such that (1) $\tau(\mathcal{R}_X)$ is nowhere dense and (2) for $t\in \tau(\mathcal{R}_X)$ the set
$\tau^{-1}(t)\cap \mathcal{R}_X$ is a chain transitive component.
\end{definition}

\begin{remark}
The original definition in \cite[II.\S6.4]{Conley1978} of a complete Lyapunov function requires for $t\in \tau(\mathcal{R}_X)$ the preimage $\tau^{-1}(t)$ to be a chain transitive component. In general we
cannot expect the critical levels of $\tau$ to be equal to chain transitive components. As an example consider $U=\mathbb R^2$ and a vector field
$X=\chi\cdot e_1$ with $\chi\ge 0$ and $\chi(x,y)=0$ iff $(x,y)=(0,0)$. It is obvious that the chain recurrent set $\mathcal{R}_X$ consists only of the origin $(0,0)$
although the critical level $\{\tau=\tau((0,0))\}$ of any complete Lyapunov function $\tau\colon \mathbb R^2\to \mathbb R$ is strictly larger than $\{(0,0)\}$.
To see this note that $\tau(x,0)>\tau(0,0)$ for $x<0$ and $\tau(x,0)<\tau(0,0)$ for $x>0$, because $\tau$ is continuous and strictly decreasing along solution trajectories.  Thus
the critical level $\{\tau=\tau((0,0))\}$
divides the plane into at least two connected components. Since a single point does not divide the plane we arrive at the conclusion that the critical
level is strictly larger than $\{(0,0)\}$.
\end{remark}

\begin{remark}
Our definition of a complete Lyapunov function is stricter than that of Conley: $\tau$ is $C^1$, whereas Conley's function is merely continuous, and in our definition $p\in\mathcal{R}_X$ implies $\nabla\tau(p)=0$, which is not necessarily the case in Conley's work, even for a differentiable $\tau$.  The advantage of this stricter definition is that the decrease condition can be written $\nabla \tau(p)\cdot X(p) <0$ for every $p\in U\setminus \mathcal{R}_X$,
 which is much more accessible for numerical methods.  Note that a complete Lyapunov function from Definition \ref{comLyaDef} is also a complete Lyapunov function in the sense of Conley \cite{Conley1978}
and it was proved in \cite{SuHa2020complya} that such a complete Lyapunov function always exists, i.e.~our definition is not more restrictive.
\end{remark}

Now we are ready to state our main result:

\begin{thm}\label{T1}
Let $U\subset \mathbb R^n$ be open and let $X\colon U\to\mathbb R^n$ be $C^l$ with $l\in \mathbb N\cup\{\infty\}$. Then for every compact set $K\subset U\setminus \mathcal{R}_X$
and every $C^l$-function $g\colon U_K\to (-\infty,0)$
defined on a neighborhood $U_K$ of $K$ there exists a complete $C^l$-Lyapunov
function
\[
\tau_K\colon U\to \mathbb R
\]
with $\dot{\tau}_K|_K\equiv g$ and $\dot\tau_K<0$ on $U\setminus \mathcal{R}_X$.
\end{thm}

\begin{remark}\label{R1}
\begin{itemize}
\item[(a)] In the proof we will w.l.o.g.~assume that the local flow is complete.
Note that for every continuous function $f\colon U\to (0,\infty)$ the chain recurrent sets of $X$ and $f X$ coincide.

Further we can choose a
$C^\infty$-function $f\colon U\to \mathbb R$ with $f|_K\equiv 1$ such  that the local flow $\Psi$ of $f X$ is complete, i.e.
$$\Psi\colon \mathbb R\times U\to U,\quad (t,p)\mapsto \Psi_t(p)$$
is well defined. Note that $\Psi$ coincides with the local flow of $X$ on $K$. Further the set $\mathcal{R}_{X}=\mathcal{R}_{f X}$ is
$\Psi$-invariant. Thus proving Theorem \ref{T1} for $f X$ instead of $X$ yields the claim for the initial vector field as well. We will continue to use the
notation $X$ for the vector field under consideration.

\item[(b)]
Note that the regularity of $\tau_K$ is i.g.~optimal. As an example consider a vector field $X\colon \mathbb R^2\to \mathbb R^2$ of the form $X(x,y)=\chi(y)e_1$ for
some $C^l$-function $\chi\colon \mathbb R\to (0,\infty)$ which is nowhere $C^{l+1}$; e.g.~the $l$th derivative might be the Weierstrass function.
 Let $K:=[0,1]\times [0,1]\subset \mathbb R^2$ and $g\equiv -1$. By  Theorem
\ref{T1} we have a complete
$C^l$-Lyapunov function $\tau_K\colon \mathbb R^2\to \mathbb R$ with $\dot{\tau}_K|_K\equiv -1$. The flow of $X$ is given by $\Phi_t(x,y)=(x+t\chi(y),y)$ and
\begin{equation}
\label{OPTREG}
\tau_K(x+t\chi(y),y)-\tau_K(x,y)=-t
\end{equation}
as long as $\{(x+s\chi(y),y)\,|\; s\in[0,t]\}\subset K$. Assume that $\tau_K$ is $C^{l+1}$ on an open set $V\subset K$. Choose $0<t_0$, $(x_0,y_0)$ and $\delta>0$ such
that
\[
(x+t\chi(y),y)\in V
\]
for all $t\in [0,t_0]$ and all $|x-x_0| < \delta$ and $|y-y_0| < \delta$. Since $\tau_K$ is $C^{l+1}$ by assumption and for all $t$ and $(x,y)\in V$ in question, we have by \eqref{OPTREG}
for all small enough $h>0$ that
$$
\frac{\tau_K(x+h,y)-\tau_K(x,y)}{h}=\frac{-1}{\chi(y)},
$$
in particular
$$
\partial_1\tau_K(x,y)=\lim_{h\to 0+}\frac{\tau_K(x+h,y)-\tau_K(x,y)}{h}=\frac{-1}{\chi(y)} \neq 0.
$$
Further,
 the level sets $\{\tau_K=\tau_K(x_0,y_0)\}$ and $\{\tau_K=\tau_K(x_0+t_0\chi(y_0),y_0)\}$ are
graphs
\[
\{(\phi_i(y),y)|\; y\in I\},\quad i=0,1
\]
of two $C^{l+1}$ functions $\phi_0\colon I\to \mathbb R$ and $\phi_1\colon I\to\mathbb R$ respectively, where $I\subset \mathbb R$ is a sufficiently small interval around $y_0$.
 Hence
 $$
 \frac{-t_0}{\phi_1(y)-\phi_0(y)}=\frac{\tau_K(\phi_1(y),y)-\tau_K(\phi_0(y),y)}{\phi_1(y)-\phi_0(y)}=\frac{-1}{\chi(y)},
 $$
 i.e.~$\phi_1(y)-\phi_0(y)=t_0\chi(y)$ for all $y\in I$, from which $\chi$ in $C^{l+1}$ on $I$follows, a contradiction to the assumption.
\end{itemize}
\end{remark}

\section{Proof of Theorem \ref{T1}}
\label{proof}

The proof consists of modifying a sufficiently fast descending Lyapunov function on $K$ while preserving it away from $K$. This is accomplished in
Proposition \ref{P1}. The proposition in turn relies on the main technical Lemma \ref{L1} which gives the construction on a single flow box (see
definition below). The proof of the proposition is then a repeated application of the lemma.

By \cite{SuHa2020complya} we know that $X$ admits a complete $C^\infty$-Lyapunov function, $\tau'\colon U\to \mathbb R$.
We define {\bf flow boxes} as follows. For $r\in \mathbb R$ let $V_{\tau',r}$ be a precompact relatively open subset of $ \{\tau'=r\}\setminus \mathcal{R}_X$, i.e.
$V_{\tau',r}$ is open in $\{\tau'=r\}\setminus \mathcal{R}_X$ and the closure $\overline{V_{\tau',r}}$ is a compact subset of $U\setminus \mathcal{R}_X$. The map
$$\Phi\colon \mathbb R\times V_{\tau',r}\to U\setminus \mathcal{R}_X,\quad (t,q)\mapsto \Phi_t(q)$$
is a diffeomorphism onto its image. For $T>0$ the set
$$\mathcal{V}_{\tau',r,T}:=\Phi((-T,T)\times V_{\tau',r})\subset U\setminus \mathcal{R}_X$$
is called a {\it flow box}, cf.~Figure \ref{flowbox}.
\begin{figure}[ht]
	\centering
 \includegraphics[width=0.7\textwidth]{FLOWBOXtest.pdf}
	\caption{Schematic figure of a flow box $\mathcal{V}_{\tau',r,T}$.}
	\label{flowbox}
\end{figure}

Choose $r_1>\ldots >r_N\in \mathbb R$ and $V_{\tau',r_i}\subset \{\tau'=r_i\}\setminus \mathcal{R}_X$ such that the flow boxes
$$\mathcal{V}_{\tau',r_i,1}:=\Phi((-1,1)\times V_{\tau',r_i})$$
form an open cover of $K$, i.e.
\[
K\subset \bigcup_{i=1}^N \mathcal{V}_{\tau',r_i,1}.
\]
Choose  precompact relatively open subsets $\overline{V_{\tau',r_i}}\subset W_{\tau',r_i}\subset \{\tau'=r_i\}$.
Then the flow boxes satisfy
$$\overline{\mathcal{V}_{\tau',r_i,1}}\subset \mathcal{W}_{\tau',r_i,i+1}=\Phi((-(i+1),i+1)\times W_{\tau',r_i}).$$
Choose a constant $0<C<\infty$ such that $C\dot{\tau}'<-N-3$ on $\bigcup_{i=1}^N \mathcal{W}_{\tau',r_i,i+1}$.
Set $\tau:=C\tau'$, $s_i:= Cr_i$, $V_{s_i}:=V_{\tau',r_i}$, $W_{s_i}:=W_{\tau',r_i}$, $\mathcal{V}_{s_i,1}:=\mathcal{V}_{\tau',r_i,1}$,
and $\mathcal{W}_{s_i,i+1}:=\mathcal{W}_{\tau',r_i,i+1}$.
We then have
\begin{equation}\label{E2}
\dot{\tau}(p)<-N-3\text{ for all }p\in \bigcup_{i=1}^N \mathcal{W}_{s_i,i+1}.
\end{equation}

We will deduce Theorem \ref{T1} from the following modification result.

\begin{prop}\label{P1}
Let $X\colon U\to \mathbb R^n$ be $C^l$ with $l\in\mathbb N\cup\{\infty\}$ and let $K\subset U\setminus \mathcal{R}_X$ compact be given. If \eqref{E2} holds, then there exists a complete
$C^l$-Lyapunov function $\overline{\tau}_K\colon U\to \mathbb R$ such that
\begin{itemize}
\item[(i)] $\overline{\tau}_K$ and $\tau$ coincide on $U\setminus \bigcup_i \mathcal{W}_{s_i,i+1}$,
\item[(ii)] $\nabla\overline{\tau}_K\cdot X\equiv -1$ on a neighborhood of $K$, and
\item[(iii)] the critical set of $\overline{\tau_K}$ is equal to $\mathcal{R}_X$, i.e. $\{p\in U|\; \nabla \tau_K=0\}=\mathcal{R}_X$.
\end{itemize}
\end{prop}

\begin{proof}[Proof of Theorem \ref{T1}]
From Proposition \ref{P1} we obtain a complete Lyapunov function $\overline{\tau}_K$ which satisfies all claims of Theorem \ref{T1} except
$\nabla\overline{\tau}_K\cdot X|_K\equiv -1$ and not $\nabla\overline{\tau}_K\cdot X|_K\equiv g$ for a given  $g\colon U_K\to (-\infty,0)$.
Choose a closed neighborhood $V_K$ of $U\setminus U_K$
disjoint from $K$. Extend $g$ to a negative $C^l$-function on $U$ with $g|_{V_K}\equiv -1$ and consider the vector field $X_g:=-X/g$.
Choose
a Lyapunov function $\tau_K$ for $X_g$ according to Proposition \ref{P1}. Then we have $\nabla\tau_K\cdot X_g|_K\equiv -1$ which is
equivalent to $\nabla \tau_K\cdot X|_K=\dot{\tau}_K|_K\equiv g$.
\end{proof}

Proposition \ref{P1} follows from the next lemma by repeated application.

\begin{lemma}\label{L1}
Let $\tau\colon U\to\mathbb R$ be a complete $C^l$-Lyapunov function and $M\subset U\setminus \mathcal{R}_X$ be closed and assume that
$\nabla\tau\cdot X\equiv -1$ on a neighborhood of $M$.
Let $V_s,W_s\subset \{\tau=s\}\setminus\mathcal{R}_X$ be relatively open precompact sets with $\overline{V_s}\subset W_s$ and $k\in\mathbb N$ such that
\begin{equation}\label{E1}
\dot{\tau}(p)<-k-3
\end{equation}
for all $p\in \Phi([k,k+1]\times \overline{W_s})$.
Then there exists a complete $C^l$-Lyapunov function $\tilde{\tau}\colon U\to\mathbb R$ with
\begin{itemize}
\item[(i)] $\tilde{\tau}\equiv \tau$ on $U\setminus \mathcal{W}_{s,k+1}$ and
\item[(ii)] $\nabla\tilde{\tau}\cdot X\equiv -1$ on a neighborhood of $\overline{\mathcal{V}_{s,1}}\cup M$,
\end{itemize}
where $\mathcal{V}_{s,1}:=\Phi((-1,1)\times V_s)$ and $\mathcal{W}_{s,k+1}:=\Phi((-(k+1),k+1)\times W_s)$ are the flow boxes around
$V_s$ and $W_s$.
\end{lemma}

\begin{proof}[Proof of Proposition \ref{P1}]
First note that since we assume that $\tau$ is a complete Lyapunov function and the critical values of $\tau$ and $\overline{\tau}_K$ coincide, it
follows trivially that $\overline{\tau}_{K}$ is also a complete Lyapunov function.

The construction of $\overline{\tau}_K$ proceeds by induction over $k=1,\ldots,N$.

For $k=1$ apply Lemma \ref{L1} to $M=\emptyset$ and $\mathcal{V}_{s,1}=\mathcal{V}_{s_1,1}$ and $\mathcal{W}_{s,2}=\mathcal{W}_{s_1,2}$.
Condition \eqref{E1} is satisfied by assumption \eqref{E2}.
This yields a Lyapunov function $\tilde{\tau}_1\colon U\to \mathbb R$ with $\tilde{\tau}_1\equiv \tau$ on $U\setminus \mathcal{W}_{s_1,2}$ and
$\nabla\tilde{\tau}_1\cdot X\equiv -1$ on a neighborhood of $\overline{\mathcal{V}_{s_1,1}}$.

Now let $k\ge 2$ and assume that a Lyapunov function $\tilde{\tau}_{k-1}\colon U\to \mathbb R$ with
$$\tilde{\tau}_{k-1}\equiv \tau\text{ on }U\setminus \bigcup_{i< k} \mathcal{W}_{s_i,i+1}$$
and
$$\nabla\tilde{\tau}_{k-1}\cdot X\equiv -1\text{ on a neighborhood of }\bigcup_{i< k}\overline{\mathcal{V}_{s_i,1}}$$
has been constructed.

Set $M=\bigcup_{i< k}\overline{\mathcal{V}_{s_i,1}}$.
We show that
\[
\Phi([k,k+1]\times \overline{W_{s_k}})\cap \bigcup_{i< k} \mathcal{W}_{s_i,i+1}=\emptyset.
\]
This especially implies $ \Phi([k,k+1]\times \overline{W_{s_k}})\cap M =\emptyset$.
Assume on the contrary that for a $p\in \overline{W_{s_k}}$ and $t_p\in [k,k+1]$
 there exist for an $i<k$ a  $q\in W_{s_i}$ and $t_q\in (-(i+1),i+1)$ such  that $\Phi(t_q,q)=\Phi(t_p,p)$.  Then we have $q=\Phi(t_p-t_q,p)$ with $t_p-t_q >0$ and
it follows that
$$
s_k < s_i=\tau(q)=\tau(\Phi(t_p-t_q,p))<\tau(p)=s_k,
$$
a contradiction.

Thus we have $\tilde{\tau}_{k-1}\equiv\tau$ on $\Phi([k,k+1]\times \overline{W_{s_k}})$. With the assumption of \eqref{E2} we conclude that
Condition \eqref{E1} is satisfied.

Now Lemma \ref{L1} with $s=s_k$ yields a complete Lyapunov function $\tilde{\tau}_k\colon U\to\mathbb R$ with $\tilde{\tau}_k\equiv \tilde{\tau}_{k-1}$ on $U\setminus
\mathcal{W}_{s_k,k+1}$, i.e. $\tilde{\tau}_k\equiv \tau$ on $U\setminus \cup_{i\le k} \mathcal{W}_{s_i,i+1}$ and
\[
\nabla\tilde{\tau}_{k}\cdot X\equiv -1\text{ on a neighborhood of }\bigcup_{i\le k}\overline{\mathcal{V}_{s_i,1}}.
\]
This finishes the induction. Setting $\overline{\tau}_K=\tilde{\tau}_N$ completes the proof.
\end{proof}

\begin{proof}[Proof of Lemma \ref{L1}]

\underline{\it Prelude:} Recall that $\mathcal{R}_X$ is the set of critical points of the Lyapunov function $\tau$ and $\overline{\mathcal{W}_{s,k+1}}\subset U\setminus \mathcal{R}_X$. Therefore the restriction of the flow
\[
\Phi\colon [-(k+1),k+1]\times \overline{W_s}\to \overline{\mathcal{W}_{s,k+1}}
\]
is a $C^l$-diffeomorphism. Note that since $\Phi$ is the flow of $X$ we have $X(p)=D\Phi(t,q)e_1$ for $p=\Phi(t,q)$,
where $e_1$ is the direction of the $\mathbb R$-factor of $\mathbb R\times \overline{W_s}$. We can thus equivalently consider the Lyapunov function $\tau\circ \Phi$ for the
constant vector field $e_1$ on $[-(k+1),k+1]\times \overline{W_s}$, because
$$
\dot\tau(p)=\nabla \tau(p)\cdot X(p) = \nabla\tau(p)\cdot D\Phi(t,q)e_1=\nabla (\tau\circ \Phi)(t,q)\cdot e_1.
$$
Further, we can equivalently write the orbital derivative  $\nabla (\tau\circ \Phi)\cdot e_1$ as $\partial_{e_1}(\tau\circ \Phi)$.
Thus, we have established that it suffices to construct the function $\tilde\tau$ on $[-(k+1),k+1]\times \overline{W_s}$ such that it coincides with
$$\tau\circ \Phi\colon [-(k+1),k+1]\times \overline{W_s}\to \mathbb R$$
on a neighborhood of the relative boundary

$$
\{-(k+1)\}\times W_s\cup\{k+1\}\times W_s\cup [-(k+1),k+1]\times \partial W_s,$$
where $\partial W_s:= \overline{W_s}\setminus W_s$.
We will drop the notation $\tau\circ \Phi$ for simply $\tau$ in the following and only consider the constant vector field $e_1$.
With the same argument we replace $M$ by the preimage of $M$ under $\Phi$.  Note that we do not change $\tau$ near the boundary of $\overline{\mathcal{W}_{s,k+1}}$ and therefore do not have to consider the complement of $\overline{\mathcal{W}_{s,k+1}}$.

The proof proceeds in several steps. In the first step we construct $\tilde{\tau}$ in a neighborhood of $[-1,1]\times\overline{V_s}$.
The second step then carefully interpolates $\tilde\tau$ with $\tau$ near $\{-(k+1)\}\times W_s$ in order not to destroy the property that
$\partial_{e_1}\tau\equiv -1$ on a neighborhood of $M$. The third step then takes care of the interpolation near $\{k+1\}\times W_s$.
Finally the fourth step interpolates $\tilde{\tau}$ with $\tau$ near $[-(k+1),k+1]\times \partial W_s$ again carefully in order not to destroy
the property that $\partial_{e_1}\tau\equiv -1$ on a neighborhood of $M\cup [-1,1]\times \overline{V_s}$.

\begin{figure}[ht]
	\centering
 \includegraphics[width=\textwidth]{f1.pdf}
	\caption{The first step.}
	\label{fig1}
\end{figure}

\underline{\it 1$^{st}$ step:}

In this first step we will construct a Lyapunov function $\tau_1$ on $[-(k+1),k+1]\times W_s$ with $\partial_{e_1} \tau_1 \equiv -1$ on
$[-1,1]\times \overline{V_s}$, see Figure \ref{fig1}.

Choose a smooth monotone function $\mu_-\colon \mathbb R\to[0,1]$ with:
\begin{itemize}
\item[(1)] $\mu_-\equiv 0$ for $t\le -3/2$ and
\item[(2)] $\mu_-\equiv 1$ for $t\ge -5/4$.
\end{itemize}
Define $\tau_1\colon [-(k+1),k+1]\times W_s\to \mathbb R$ by
$$\tau_1(t,q):=(1-\mu_-(t))\tau(t,q)+\mu_-(t)\left[\tau(-1,q)-\left(t+\frac{3}{2}\right)\right].$$
It is easy to see that $\tau_1$ is $C^l$-regular with $\partial_{e_1}\tau_1<0$ on $[-(k+1),k+1]\times \overline{W_s}$
and $\partial_{e_1} \tau \equiv -1$ on $[-5/4,k+1]\times \overline{W_s}$.
Indeed we have
\begin{align*}
\partial_{e_1} \tau_1=&(1-\mu_-(t))\partial_{e_1} \tau(t,q)-\mu_-(t)\\
&+ \mu'_-(t)\left[\tau(-1,q)-\left(t+\frac{3}{2}\right)-\tau(t,q)\right].
\end{align*}
The term
$$(1-\mu_-(t))\partial_{e_1} \tau(t,q)-\mu_-(t)$$
is everywhere negative, since $\tau$ is a Lyapunov function
for $e_1$ and constant to $-1$ for $t\ge -5/4$. The term
\[
\tau(-1,q)-\tau(t,q)-\left(t+\frac{3}{2}\right)
\]
is negative for $-3/2\le t \le -5/4$ because $\tau(t,q)\ge \tau(-1,q)$. Since $\mu'_-\ge 0$ and $\supp \mu'_-\subset [-3/2,-5/4]$ we conclude that  $\tau_1$ is Lyapunov. Note that $\tau_1\equiv \tau$ on $[-(k+1),-3/2]\times \overline{W_s}$.

\underline{\it 2$^{nd}$ step:} In this step, we construct a function $\tau_2$ from $\tau_1$, such that $\partial_{e_1}\tau_2 \equiv -1$ on an appropriate set involving $M$ and $[-1,1]\times \overline{V_s}$, see the later claim in this step and Figure \ref{fig2}.
\begin{figure}[ht]
	\centering
 \includegraphics[width=\textwidth]{f2.pdf}
	\caption{The second step. }
	\label{fig2}
\end{figure}

Fix a neighborhood $U_M\subset [-(k+1),k+1]\times \overline{W_s}$ of $M$ (in the relative topology), such that
$\partial_{e_1}\tau|_{U_M}\equiv -1$.
For $(t,p)\in M\cap [-3/2,-5/4]\times \overline{W_s}$ consider the level set
$$\{\tau=\tau(t,p)\}\cap [-7/4,-1]\times \overline{W_s}.$$
Choose a neighborhood $U_{p}$ of $p$ in $\overline{W_s}$ such that there exists an open interval $I_p$ containing $\tau(t,p)$ and
\[
\{\tau\in I_p\}\cap [-7/4,-1]\times \overline{U_p}\subset U_M.
\]

Note that $\partial_{e_1}\tau\equiv -1$ on $\{\tau\in I_p\}\cap [-7/4,-1]\times \overline{U_p}$ according to the choice of $U_M$.
By the Implicit Function Theorem there exists a $C^l$-function
$$\phi_p\colon U_p\to [-7/4,-1]$$
with $\tau(u,q)=\tau(t,p)$ iff $u=\phi_p(q)$, i.e. a parameterization of a part of the level set $\{\tau=\tau(t,p)\}$ (if necessary, shrink $U_p$).
Note that we can assume (possibly after further shrinking $U_p$) that
\begin{equation}\label{E4}
\tau(u,q)=\tau(\phi_p(q),q)-u+\phi_p(q)
\end{equation}
in a neighborhood of $\{(\phi_p(q),q)|\; q\in U_p\}$ since the points $(\phi_p(q),q)$ belong to $U_M$  and $\partial_{e_1}\tau\equiv -1$ on $U_M$.
Define a function
\begin{align*}
\sigma_p\colon [-(k+1),k+1]\times U_p&\to \mathbb R,\\
\sigma_p(u,q)&:=\begin{cases}
\tau(u,q),&\text{ for }u\le \phi_p(q)\\
\tau(\phi_p(q),q)-u+\phi_p(q)&\text{ for }u\ge \phi_p(q).
\end{cases}
\end{align*}
The function $\sigma_p$ is $C^l$-regular by \eqref{E4}. Further we have
$\partial_{e_1} \sigma_p<0$ everywhere with $\equiv -1$ on $\{(u,q)|\; u\ge \phi_p(q)\}\subset [-(k+1),k+1]\times U_p$.

We  select a finite subcover $\{U_j:=U_{p_j}\}_{j=1,\ldots, R}$ of the compact set
$$M_s:=\{p\in \overline{W_s}|\; \exists t\in [-7/4,-5/4]: (t,p)\in M\}.$$
Let $\{\lambda_j\}_j$ be a smooth partition of unity subordinate to $\{U_j\}_j$. Then
\begin{align*}
\sigma\colon [-(k+1),k+1]\times \bigcup_{1\le j \le R}  U_j&\to \mathbb R, \\
\sigma(t,q)&:=\sum_j \lambda_j(q) \sigma_{p_j}(t,q)
\end{align*}
is a $C^l$-function with $\partial_{e_1} \sigma \equiv -1$ on $[-1,k+1]\times(\cup_j  U_j)$. Note that $\sigma\equiv \tau$ on $[-(k+1),-7/4]\times (\cup_j U_j)$.

Let $\mathbb{U}_1$ be a neighborhood of $M_s$ (in the relative topology of $\overline{W_s}$) with closure in $\cup_j  U_j$ and let $\nu_1\colon \overline{W_s}\to [0,1]$ be smooth with
$\nu_1|_{\mathbb{U}_1}\equiv 1$ and $\supp\nu_1\subset \cup_j  U_j$.

Now the function
\begin{align*}
\tau_2\colon [-(k+1),k+1]\times \overline{W_s}&\to \mathbb R,\\
\tau_2(t,q)&:= \nu_1(q) \sigma(t,q) +[1-\nu_1(q)]\tau_1(t,q)
\end{align*}
is $C^l$ and Lyapunov for $e_1$.

{\it Claim:} We claim that $\partial_{e_1} \tau_2\equiv -1$ on
a neighborhood of
$$M\cup [-1,1]\times \overline{V_s}.$$

{\it Proof of the claim:}
We have $\partial_{e_1} \sigma \equiv -1$ on a neighborhood of $[-1,k+1]\times \supp \nu_1$ and $\partial_{e_1} \tau_1\equiv -1$ on $[-5/4,k+1]\times
\overline{W_s}$. Therefore
$$
\partial_{e_1} \tau_2 (t,q) = \nu_1(q) \partial_{e_1} \sigma(t,q)+(1-  \nu_1(q))\partial_{e_1} \tau_1(t,q)\equiv -1
$$
and the claim is obvious on a neighborhood of $[-1,k+1]\times \overline{W_s}$.  In particular we obtain $\partial_{e_1}
\tau_2\equiv -1$
 on a neighborhood of
$(M\cap [-1,k+1]\times \overline{W_s})\cup [-1,1]\times \overline{V_s} \subset [-1,k+1]\times \overline{W_s}$.

It only remains to consider the set $M\cap [-(k+1),-1)\times \overline{W_s}$ because $M \subset  [-(k+1),k+1]\times \overline{W_s}$.

For $(t,p)\in M$ with $t\in (-5/4,-1)$  there are two cases: If $p\notin \supp \nu_1$ we have $\tau_2\equiv \tau_1$ in a neighborhood of $(t,p)$. It follows
that $\partial_{e_1} \tau_2 \equiv \partial_{e_1} \tau_1\equiv -1$ in a neighborhood of $(t,p)$. If $p\in \supp \nu_1$ note that $\partial_{e_1} \sigma_{p_j}
\equiv -1$ in a neighborhood of $(t,p)$ for all $1\le j\le N$ such that $p\in U_j$. This implies $\partial_{e_1}\sigma\equiv -1$ near $(t,p)$.
Since $\partial_{e_1}\tau_1\equiv -1$ in a neighborhood
of $(t,p)$ we obtain again $\partial_{e_1} \tau_2 \equiv -1$ in a neighborhood of $(t,p)$.

For $(t,p)\in M$ with $t\in [-3/2,-5/4]$ we have $\nu_1\equiv 1$ near $p$. As in the previous case we have $\partial_{e_1}\sigma\equiv -1$
in a neighborhood of $(t,p)$, i.e. $\partial_{e_1}\tau_2\equiv -1$ near $(t,p)$.

Finally for $(t,p)\in M$ with $t\in [-(k+1),-3/2)$ we again distinguish two cases: First assume $p\notin \supp \nu_1$. Then $\tau_2\equiv \tau_1\equiv
\tau$ in a neighborhood of $(t,p)$. Since $(t,p)\in M$ we conclude $\partial_{e_1}\tau_2\equiv -1$ near $(t,p)$.  Now assume
$p\in\supp \nu_1$. For $1\le i\le N$ such that $\phi_i(p)$ is defined, i.e.~$p\in U_{p_i}$, and $t<\phi_i(p)$ we have $\sigma_{p_i}\equiv \tau$ near $(t,p)\in M$, i.e. $\partial_{e_1}
\sigma_{p_i}\equiv -1$ near $(t,p)$.
For $1\le i\le N$ such that $\phi_i(p)$ is defined and $t\ge \phi_i(p)$ we have $\partial_{e_1}\sigma_{p_i}\equiv -1$ in a neighborhood of $(t,p)$ trivially by construction.
Since $\tau_1\equiv \tau$ near $(t,p)$ and $(t,p)\in M$ we also have $\partial_{e_1}\tau_1\equiv -1$ near $(t,p)$.
Summing up we conclude $\partial_{e_1}\tau_2\equiv -1$ in a neighborhood of $(t,p)$.

This concludes the proof of the claim.

\underline{\it 3$^{rd}$ step:}
Next we modify $\tau_2$ on $[k,k+1]\times \overline{W_s}$ so that it coincides with $\tau$ near $\{k+1\}\times \overline{W_s}$, see Figure \ref{fig3}.
\begin{figure}[ht]
	\centering
 \includegraphics[width=\textwidth]{f3.pdf}
	\caption{The third step }
	\label{fig3}
\end{figure}
We start with estimating $\tau_2(k+1,q)$ from below. Note that by construction
\[
\tau_1(k+1,q)=\tau(-1,q)-k-5/2
\]
and for   $q\in U_j$ we have
\begin{align*}
\sigma_{p_j}(k+1,q)&=\tau(\phi_{p_j}(q),q)-(k+1)+\phi_{p_j}(q)\\
&\ge \tau(-1,q)-(k+1)-7/4,
\end{align*}
because $\phi_{p_j}(q)\in [-7/4,-1]$.
Combining both, the definition of $\tau_2$ implies
$$\tau_2(k+1,q)\ge \tau(-1,q)-k-11/4$$
for all $q\in \overline{W_s}$.
By \eqref{E1} we have
$$\tau(k+1,q)\le \tau(k,q)-k-3\le \tau(-1,q)-k-3$$
and therefore there exists $\e \in (0,1/2)$ such that $\tau<\tau_2$ on $[k+1-2\e,k+1]\times \overline{W_s}$. Choose a smooth monotone function $\mu_+\colon
\mathbb R\to[0,1]$ with:
\begin{itemize}
\item[(1)] $\mu_+\equiv 0$ for $t\le k+1-2\e$ and
\item[(2)] $\mu_+\equiv 1$ for $t\ge k+1-\e$
\end{itemize}
Define $\tau_3\colon [-(k+1),k+1]\times \overline{W_s}\to \mathbb R$ by
$$\tau_3(s,q):=(1-\mu_+(s))\tau_2(s,q)+\mu_+(s)\tau(s,q).$$
As before we see that $\tau_3$ is Lyapunov for $e_1$, using $\tau<\tau_2$ on the support of the derivative of $\mu_+$. Note that by assumption \eqref{E1} the sets
$M$ and $[k,k+1]\times \overline{W_s}$ are disjoint. Since $\tau_3\equiv \tau_2$ on $[-(k+1),k+1-2\epsilon]\times \overline{W_s}$ and $k<k+1-2\epsilon$
we continue to have $\partial_{e_1} \tau_3\equiv -1$ on a neighborhood of
\[
M\cup [-1,1]\times \overline{V_s}.
\]
Moreover, $\tau\equiv \tau_3$ near $\{-(k+1),k+1\}\times \overline{W_s}$.

\underline{\it 4$^{th}$ step:}
It remains to interpolate $\tau_3$ with $\tau$ near $[-(k+1),k+1]\times \partial W_s$, see Figure \ref{fig4}.
\begin{figure}[ht]
	\centering
  \includegraphics[width=\textwidth]{f4.pdf}
	\caption{The fourth step }
	\label{fig4}
\end{figure}
Choose a neighborhood $\mathbb{U}_2$ of $\overline{V_s}$ with closure in $W_s$ and a smooth function
$\nu_2\colon \overline{W_s}\to [0,1]$ with $\nu_2\equiv 1$ on $\mathbb{U}_2$ and $\supp\nu_2\subset W_s$.
Then
\begin{align*}
\tau_4\colon [-(k+1),k+1]\times \overline{W_s}&\to \mathbb R,\\
\tau_4(s,q)&:=\nu_2(q)\tau_3(s,q)+(1-\nu_2(q))\tau(s,q)
\end{align*}
is a $C^l$-function which coincides with $\tau$ near the boundary of $[-(k+1),k+1]\times \overline{W_s}$ and
$\partial_{e_1}\tau_4\equiv -1$ on a neighborhood of $[-1,1]\times \overline{V_{s}}\cup M$.
Indeed the property holds for  $\tau_3$, and for $\tau$ outside of $[-1,1]\times\overline{V_s}$. Since $\nu_2|_{[-1,1]\times \overline{V_s}}\equiv 1$
the claim follows immediately. Setting $\tilde{\tau}:=\tau_4$ concludes the proof.
\end{proof}

\section{Conclusions}
\label{sec:conclusions}
We consider a dynamical system, given by the flow of a $C^l$-vector field $X\colon U \to\mathbb R^n$. For any compact subset $K$ of the complement of the chain recurrent set $U\setminus \mathcal{R}_X$ and any $C^l$-function $g\colon U\to (-\infty,0)$, we have established the existence of a $C^l$-regular complete
Lyapunov function $\tau$ for the system that fulfills $\dot{\tau}(p)=\nabla \tau(p)\cdot X(p) = g(p)$ for every $p\in K$.   These results are of essential importance for methods to numerically compute complete Lyapunov functions.  Indeed, they present a major leap forward in analyzing and improving
several methods that rely on solving PDEs or convex optimization problems containing equality constraints.

\bibliographystyle{amsplain}


\section{Introduction}
Given a master key that can unlock all your secrets and derive any encryption key you may have in your system, how would you securely store and hide that key? You can encrypt it, but then all security relies on another secret key or password used when encrypting the master key. You may put it in a Hardware Security Module (HSM) or a vault but again it would only be protected by another key or password. It seems that no matter which approach is used for securing a secret key, you must use yet another key, hence the problem is only moved one layer ahead - we can suspect this problem unsolvable!
\\
\\
Assuming that no fully secure way to protect a secret key exists, we can only do our best to make it as difficult as possible for an adversary to break our system and steal the key (or at least get access and make use of the key).
Securing secret keys is a pretty normal concept in modern software development, especially in web applications, API:s and microservices that utilizes TLS or integrates to other systems using secure channels. Due to the nature of secure communication, we need all of these private and secret keys to establish and perform symmetric encryptions and digital signatures.
It is not too uncommon to find that the secret key is embedded in the service itself, sometimes in plain text and sometimes in a keystore. We would argue it is pretty common to use property- or configuration files to point to a keystore or the actual key, which the service then reads to memory when requested to perform encryption.
If an adversary manages to compromise the underlying server or memory, it would be theoretically possible to steal that key, or if a vault is used, then the adversary would be able to intercept the password or key used for unlocking the vault.
\\
\\
Note that we are assuming systems where the usage of secret keys are automated and not manually handled by a human; in those cases there might be a reason for a person to actually input a device and/or typing a secret password to unlock a master key or other highly sensitive data.
\\
\\
Upcoming sections will briefly overview current techniques and crypto protocols for securing master secrets, both on what is adopted into commercial products and discovered in recent research. Afterwards, we are ready to conclude best solutions for storing master keys and propose a set of solutions based on secret sharing with multi-party computations.

\section{Securing secret keys}

For larger organizations it is standard practice to use HSMs for storing secret keys and performing cryptographically important operations such as digital signatures or generating symmetric keys, especially if there is a demand for high level security. An HSM is basically a piece of hardware, specifically constructed for crypto operations or secure storage of data, which often is hardened and tamper-resistant. Usually the HSM is FIPS-140 certified as well, meaning fulfilling US government requirements for cryptography modules \cite{brown1994security}.

Popular commercial HSM vendors are Thales \cite{thales} and Utimaco \cite{utimaco} who offer a wide range of different models and functions. Depending on the setup of the HSM, or rather the cluster of HSMs for redundancy, applications request a signature or encryption of a message $m$ using the master key inside the HSM. Typically $m$ is sent from the application to the HSM along with some access such as password or secret key, and if authenticated correctly the HSM will perform the requested crypto operation. Moreover, the HSM can be accessed for operational or maintenance purposes, then a secure channel is needed and a specific administration account can be used for login. For Thales SafeNet HSM this is typically done by using an admin account with a secret PIN code.
\\
\\
If not using an HSM it is common to use a virtual safe, often referred to as a \emph{vault}.

\section{Secret Sharing}
The purpose of secret sharing is for a party $P_i$ to spread a secret across other parties in such a way that only $P_i$ can recreate the secret. As an example, assume that a party $P_1$ wants to share a secret integer $x$ in $\mathbb{Z}_p$, where $p$ is a prime. By finding three other integers such that
$$
x = r_1 + r_2 + r_3
$$
it is possible for $P_1$ to secretly share $x$ with two other parties $P_2, P_3$. This is accomplished by sending $r_1$ and $r_3$ to $P_2$, $r_1$ and $r_2$ to $P_3$, and $r_2$ and $r_3$ to $P_1$ itself. $P_1$ has successfully managed to secretly share the secret. Neither party alone can compute $x$, but it can be reconstructed by using shares from at least two parties \cite{cramerbook}. One of the more widely used secret sharing schemes was created by Adi Shamir and is called Shamir's secret sharing \cite{shamir1979share}, which we will explain in greater detail below. However, it is worth pointing out that other schemes exists, for example Blakley's secret sharing \cite{blakley1979safeguarding}. Secret sharing is a key tool used in secure multi-party computation.

\subsection{Shamir's secret sharing}
As stated by Shamir \cite{shamir1979share}, a $(k,n)$-threshold scheme is a scheme where a secret $D$ is divided into $n$ shares (or pieces): $D_1,...,D_n$ such that:
\\
\begin{enumerate}
\item{$D$ is easily computed by knowing $k$ or more pieces, and}
\item{$D$ cannot be computed by knowing $k-1$ or less pieces.}
\end{enumerate}
\ \\
The idea behind a threshold scheme is that they are helpful for managing cryptographic keys. Shamir states that in order to protect data we encrypt it. However, it is not possible to encrypt the keys themselves, since these are needed for encryption and decryption. Thus, Shamir proposes a robust key management scheme by using a $(k,n)$-threshold scheme where $n = 2k-1$. This way the key can be recovered even if $n/2 = k-1$ shares are destroyed \cite{shamir1979share}.

The scheme Shamir proposed is based on polynomial interpolation. Given $k$ points in the 2-dimensional plane $(x_1,y_1), ..., (x_k, y_k)$ there is only one polynomial $q(x)$ of degree $k-1$ such that $q(x_i) = y_i$ for all $i$, given that all $x_i$ are distinct \cite{shamir1979share}.

In order to divide the secret $D$ into $n$ shares, a random $k-1$ degree polynomial $q(x)$ is chosen, where $q(x) = a_0 + a_1x + a_2x^2 + ... + a_{k-1}x^{k-1}$ and $a_0 = D$. The share $D_i$ is then calculated by evaluating:

$$
D_1 = q(1), ..., D_n = q(n)
$$

Given any subset with $k$ shares, the coefficients of $q(x)$ can be found by interpolation. The secret is found by evaluating $q(0) = D$ \cite{shamir1979share}.

\subsection{Verifiable secret sharing}
A problem with secret sharing is that any of the involved parties might become malicious, for example the dealer or any of the participating parties. In the former case, the dealer would send incorrect shares to the other parties. In the latter case, a bad party might interfere with the protocol and send a faulty share to the dealer. This would break the protocol, since even if there are enough good players to recover the secret, no one can distinguish good shares from faulty ones. In order to solve this problem, verifiable secret sharing schemes can be used instead, where each party can verify that their share is consistent. Paul Feldman \cite{feldman1987practical} proposed a modification of Shamir's protocol utilizing homomorphic encryption in order to make it verifiable.

\section{Secure Multi-Party Computation}
Assume two parties want to find out who is richer, without revealing their wealth to each other. How would you solve that? Andrew Yao \cite{yao1982protocols} answered this question in 1982, thus creating a subfield within cryptography known as \emph{secure multi-party computation} (SMPC). The basic idea is that a set of parties keeps a bit of a secret each, which all (or at least a threshold thereof) is needed when restoring the original secret and input it to some secure function which computes a desired outcome everyone are interested in. Therefore all parties will not reveal their own secrets but can take part of a common output, e.g. the answer to who is richest.

Nowadays with increased utilization of cloud services and distributed infrastructures, SMPC-based protocols could be something both relevant and focused on if theory can be bridged over to secure and stable implementations. Also, from Garner's Hype Cycle for security in 2019, multi-party computations are put under the category \emph{on the rise} \cite{gartner} which indicates that this technology might be something to start look into more seriously.
\\
\\
In a SMPC problem there are $n$ players, or parties, that participate: $P_1, P_2, ..., P_n$. Each player $P_i$ holds a secret input $x_i$ which they do not want to reveal to any of the other players. The players agree on a function $f$ that takes $n$ parameters as input and outputs an answer $y$, such that $y = f(x_1, x_2, ..., x_n)$. At the same time, two conditions must be satisfied:
\\
\begin{enumerate}
\item{\emph{Correctness}: the correct value of $y$ is computed.}
\item{\emph{Privacy}: $y$ is the only new information released.}
\end{enumerate}
\ \\
If both condition 1) and 2) are satisfied when computing function $f$, it is said that $f$ has been computed securely \cite{cramerbook}.
\\
\\
A trivial solution to this problem is that all parties agree on a trusted third party $\mathcal{T}$ which would gather all the inputs and compute the function $f$ \cite{cramerbook}. $\mathcal{T}$ announces the result to the parties and then discards all computation results. As pointed out by Cramer et al \cite{cramerbook} there are at least two problems with this approach. Firstly, it creates a single point of failure. If an adversary gets access to the third party, all private data could be stolen. Secondly, all parties must now trust $\mathcal{T}$. If they do not even trust each other, how are they supposed to trust $\mathcal{T}$?

\subsection{SMPC protocols and homomorphic encryption}
Some SMPC protocols are combined with \emph{homomorphic encryption} (HE),  i.e. encryption schemes where you can compute on ciphertexts without decryption. This is particularly interesting since then all parties $P_i$ can encrypt their inputs under some HE scheme, next they evaluate function $f$ using the ciphertexts and finally execute the distributed decryption to get the result. The problem is that in theory so called \emph{fully homomorphic encryption} (FHE) is needed but is in practice too slow for real implementations \cite{damgaard2012multiparty}. The field is still in its infancy but some progress on the practical development is initiated, e.g. IBM has released an open-source library for various forms of homomorphic encryption \cite{halevi2013design} and Inpher has its open-source library called \emph{TFHE: Fast Fully Homomorphic Encryption over the Torus} \cite{tfhe}.
\\
\\
Rivest et al. proposed in the late 70s \cite{fontaine2007survey} the idea of HE when trying to solve the problem of performing computations on encrypted data without decrypting it, thus it would be possible to run such operations on sensitive data on untrusted computers. More formally we could define an encryption scheme to be \emph{homomorphic} if
$$
\forall m_1, m_2 \in \mathcal{M}, E(m_1 \odot_\mathcal{M} m_2) = E(m_1) \odot_\mathcal{C} E(m_2)
$$

where $\mathcal{M}$ is the plaintext space and $\mathcal{C}$ ciphertext space respectively. Several other properties are also considered to gain different type of HE but the range of different schemes also have varying levels of security analysis \cite{fontaine2007survey}. More importantly we must differentiate \emph{fully homomorphic encryption} (FHE) which is the strongest notion meaning it would be possible to do arbitrary computations on the cipher texts; with weaker notions we loose the arbitrarily part. In any case, many SMPC protocols with FHE and variants thereof are proposed \cite{hui2017secure}, \cite{huang}, \cite{das} and \cite{damgaard2012multiparty}, and seemingly hints of increased interest of such protocols is to be found due to the increasing number of use cases to apply: \cite{song2020iris}, \cite{wei2020pairing}, \cite{wood2019homomorphic}, \cite{8962262} and more.

\section{Implementations and technology}
This section overviews commercial and open-source projects utilizing secret sharing, secure multi-party computations and similar. These are not too widely adopted yet but some commercial products outside of cryptocurrencies claim to use these algorithms and protocols; we often see that cryptocurrencies also uses more and other type of cryptographical primitives such as zero-knowledge proofs \cite{sanchez2019zero}, accumulators \cite{6547123} and others.
\subsection{Docker secrets}
Using containerization is common today and Docker \cite{docker} is one of the more well known technologies adopted. Having a cluster of Docker containers, possibly communicating among each other or with external services, the need for storing private keys and other sensitive data is of importance. Therefore Docker built \emph{Docker secrets} \cite{dockersecrets} which handles any secret or sensitive data within a Docker ecosystem, or swarm. A pre-setup of a public key infrastructure is generated for all containers in a swarm, with purpose of being able to have mutually authenticated TLS with the \emph{swarm manager}. The manager is a node within the swarm and makes use of a Raft log \cite{ongaro2016search} to encrypt and store any sensitive data or keys which the container nodes needs. According to \cite{dockersecretsblog}, \cite{dockersecrets2} the encryption uses Salsa20Poly1305 with 256-bit keys. Furthermore, as mentioned in \cite{dockersecretsblog}:
\\
\\
\emph{"Secrets get saved to the internal Raft store using NACL’s Salsa20Poly1305 with a 256-bit key. When a swarm manager starts up, the encrypted Raft logs containing the secret is decrypted using a data encryption key that is unique per-node.
\\
Nodes cannot request access to the secrets themselves – they must be provided access by the swarm manager. When you grant access to a secret, it is sent over the already established TLS connection."}
\\
\\
To conclude we see that Docker solves the problem of accessing secrets by encrypting secret keys in a Raft log, which by nature builds on consensus algorithms meaning having several nodes work coherently (distributed) in a fault-tolerance context. Moreover, Salsa20Poly1305 cipher with 256-bit keys are used for encryption. Obviously the security boils down to the TLS part which each Docker node uses to access the secret from the swarm manager.

\subsection{Vault12}
Cryptocurrencies have become vastly popular since the release of Bitcoin and in order to protect such digital currencies, investors store them in hardware or software wallets. The founders of Vault12 \cite{vault12} argue that using these wallets for storing cryptocurrency assets has a major drawback in the case of availability. If the wallet is lost, so is some of the most valuable assets a person owns. Instead, they propose Vault12 - a new decentralized cryptographic security platform.

Vault12 utilizes Shamir's secret sharing to split critical data, such as keys, into $m$ number of shares, where $n$ shares are required to reconstruct the data. When creating the vault the owner recruits people to act as parties in the secret sharing scheme. Each party gets a share, including the owner. Their phones will also serve as distributed storage nodes. In order to unlock the vault the owner has to use social verification to request the shares from the other parties. Availability is strengthened by making sure that private keys (setup on the master device) are also divided into shares, however they are only sent to the other parties. In case the owner loses his master device, the owner can contact the parties and thus request restoration shares, used to restore the master device setup on a completely new phone.

\subsection{HashiCorp Vault}
HashiCorp offers a software solution vault \cite{vault} called Vault for storing and managing access to secret keys, tokens, passwords and certificates which in turn gives access to sensitive data. Vault makes it possible to manage these secrets centrally and with a cloud-based infrastructure in mind where nodes and systems are spread across platforms and networks. Furthermore, Vault can issue short-term certificates and act as a certificate authority.

As with any type of vault solution there is also an associated access management layer; for Vault many integrations to cloud- and SAML-based solutions exists. This means that the product still relies on the authentication of the chosen method, e.g. AWS or Azure authentication, to secure the keys inside Vault. The protection against extraction is most likely high but with a broken authentication scheme an attacker would still be able to access the operations to be performed by the secret key.

\subsection{Software development}
For system developers curious in exploring secret sharing and SMPC, several relevant programming libraries can be found. This list is by no means extensive but highlights somewhat active and usable resources available:
\\
\begin{itemize}
\item{Secret sharing}
  \begin{itemize}
  \item{\emph{Shamir secret sharing library}, written in Java, this is an implementation of the algorithm with a $(k,n)$-threshold that splits a secret $s$ into $n$ shares, where $k$ shares are needed in order to recover $s$. Lagrange interpolation is used to recover a secret. \cite{shamirjava}.}
  \end{itemize}
\item{Secure multi-party computations}
  \begin{itemize}
  \item{\emph{MPyC: Secure Multiparty Computation in Python} \cite{mpyc}, a python library originating from ideas developed from a PhD project at Aarhus university, Denmark and later as a postdoc project at Eindhoven University of Technology, Netherlands.}
  \item{\emph{EMP: Efficient Multi-Party computation Toolkit} \cite{emp-toolkit}, c++ based and includes both primitives and full protocols.}
  \end{itemize}
\item{Bilinear maps / pairings}
  \begin{itemize}
  \item{\emph{JPBC: Java Pairing-Based Cryptography library}, a library in Java used to perform pairing-based operations \cite{ISCC:DecIov11}.}
  \end{itemize}
\item{Homomorphic encryption}
  \begin{itemize}
  \item{\emph{HELib}, a C++ library using Brakerski-Gentry-Vaikuntanathan (BGV) scheme with a set of optimizations \cite{halevi2013design}.}
  \item{\emph{TFHE: Fast Fully Homomorphic Encryption over the Torus} \cite{tfhe}}, also a C/C++ library where a set of interesting implementations associated to Machine Learning and encryption can be found on the GitHub page for the project.
  \end{itemize}
\end{itemize}
\;
We cannot guarantee that any of the above mentioned resources are completely verified or reviewed on a satisfiable level but instead should be considered for inspiration.

\section{Solution proposal}
We structure our proposed solutions into two parts where non-critical and critical system are considered. The former is loosely defined as a system which does not require compliance to security standards or have any risk for high-loss implications if attacked. Normally such non-critical system should also be relatively low in cost when implementing thus the compromise between adequate security and user functionality is not highly relevant (for functionality's favor). We assume that low cost is also associated with no means of investing in a HSM.

Regardless of method for accessing a secret key or using a private key for secure communication, it must inevitably be read into memory at some point. Therefore, from a system development perspective it can be very useful to programatically make sure that any cryptographic material is cleaned out from memory after usage. How to do that differs depending on programming language and underlying platforms, but it should be taken into consideration that sensitive data might also spill over to swap and crash dump files. If possible, make sure that such storage is cleaned out as well.

\subsection{Solutions for non-critical systems}
For non-critical systems it is sufficient of using keystores embedded in the application, or if possible using a Vault-based solution e.g. HashiCorp's Vault open-source version which is free. Most importantly, one should at least avoid storing any keys or passwords in plain text. It is not too uncommon that the application, for simplicity, reads a password from a configuration in order to access a keystore. An alternative is to read that password from a database instead, thus storing database credentials in the configuration. This is of course not a good thing either since the attacker get access to the database. On the other hand, it is at least possible to setup more mitigations on the database layer, e.g. restricted tables/schemes and access filtering on IP/MAC address and so on (thus only entry point into database is from applications server).
\\
\\
Finally, when considering keystores, it is important to have in mind that some implementations suffers from vulnerabilities. Several papers points out these vulnerabilities and contributes with proof-of-concept attacks to show the feasibility; for reference you may read \cite{sabt2016breaking}, \cite{focardi2018mind} and \cite{ryan2019hardware}.

\subsection{Solutions for high critical systems}
For highest security, given the assumption that networks are still needed and automated access to master key is allowed, following solution should be considered. The master key $k_{master}$ is stored in $\mathcal{E}$ (preferably a tamper-resistant, network separated HSM) with no key extraction ability, i.e. the key cannot be fully or partly extracted/exported. Furthermore, only operation that can be performed on the master key from an operational maintenance perspective is to compute the Key Check Value (KCV) in order to verify that the correct master key is present. Typical procedure to compute KCV is to send in the zero string for which $\mathcal{E}$ encrypts under the master key and outputs the cipher text truncated into 48 or 64 bytes.

Architectural setup is $n-1$ segmented subnetworks, all protected by standard means such as firewalls and gateways. Each subnet then contains one secret sharing party holding a share $k_i$ which is needed for access to $k_{master}$, i.e. creating an access key $k_n$ from the secure multi-party computation which unlocks $\mathcal{E}$ in order to access $k_{master}$. The requesting application $\mathcal{R}$ that needs an encryption or signature using $k_{master}$ triggers the multi-party computation by sending an authenticated and encrypted broadcast to all parties or via a facade API which in turn relays the request to all parties, which then securely sends each secret to HSM for final authentication. More precisely, $\mathcal{R}$ sends a request $(m,\omega)$ containing any data $m$ to be operated on and some authentication value $\omega$. Note that $\omega$ may be anything appropriate such as a signature on $m$ if public-key infrastructure is utilized, i.e. the usage of certificates, or it could be an access token if OpenID Connect infrastructure is used.
\\
\begin{figure}[H]
\centering
  \includegraphics[width=8cm]{ss-mpc.png}
  \caption{Secret sharing with multi-party computations using $n-1$ shares}
\end{figure}

Above simplified description requires some clarification on authentication details since it is hard to generalize too much and use cases may differ heavily. We consider two separate cases for the first flow when the request is sent:
\\
\begin{itemize}
\item{Public $\mathcal{R}$: a web application or public API which is exposed to an untrusted environment such as the Internet. In this case we could consider using TLS from the backend part of the API towards the SMPC part, but it does not handle the authenticity of the actual end-user. This would open up for an untrusted user to initiate the SMPC flow for any message $m$. If the use case does not allow this, a separate authentication layer is needed, e.g. OpenID Connect or some 2FA solution.}
\item{Private $\mathcal{R}$: a web application or API within an organization, behind a DMZ. In this case we assume any end-user involved is already authenticated earlier in the use case flow hence focus is on securing the actual message. Simplest solution is TLS.}
\end{itemize}
\;
\subsection{Security analysis}
\subsubsection*{Attack model}
To be more precise in the analysis of securing secret keys we need to setup a framework for how to consider the security of this particular use case; every attempt at securing the keys will suffer from one or several potential attacks. The attack vector is two dimensional, i.e. divided into power of adversary and type of attack surface. Let $\mathcal{R}$ be the requesting party, i.e. the intended user of using the master key; this could be a web application, system or even an end user. Next, let $\mathcal{E}$ be the secure storage entity, e.g. a vault, keystore or HSM. In a mathematical sense we could consider $\mathcal{R}$ sending some request message $m$ which triggers $\mathcal{E}$ to output a desired reply $c$, which can be a cipher text, a signature or a derived ephemeral key. Note that $m$ does not necessarily have to be sent directly to $\mathcal{E}$, but instead to one or several third parties which in turn trigger the computation in $\mathcal{E}$.
With increasing severity we order the attack model as follows:
\\
\subsubsection{Attacking secure channel}
Regardless of solution, may it be using secret sharing, multi-party computations or simply requesting keys or operations from $\mathcal{E}$, some sort of secure channel is needed between $\mathcal{R}$ and $\mathcal{E}$. This attack means that the adversary is eavesdropping on all network packets between $\mathcal{R}$ and $\mathcal{E}$. Naturally, if the secure channel is using TLS then the security is reduced to the security of TLS.
\\
\subsubsection{Attacking $\mathcal{R}$}
If the attacker is able to compromise $\mathcal{R}$ at some stage in order to send its own requests of choice to $\mathcal{E}$, possibly not even successful requests but at least able to trigger a communication flow, it is considered a successful attack. The base scenario is that the attacker constructs a request which $\mathcal{R}$ sends successfully to $\mathcal{E}$, regardless of content. This type of attack could reveal or leak information used for further exploits. If $\mathcal{R}$ is compromised on memory level then the adversary is able to extract any secret keys written into RAM. This implies that a master key should not be extracted from a vault or HSM but rather operating within that secure domain. What an adversary of this level can do is to replace or generate a request to use the master key of her choice; a significant difference compared to the attacking model described above.
\\
\subsubsection{Attacking $\mathcal{P}$ or $\mathcal{T}$}
Another attack possible is in a secret sharing and multi-party computational setting, where one or several third parties are involved; either some trusted third party $\mathcal{T}$ or a set of multi-party computational nodes $\mathcal{P} = \{P_1, ..., P_n\}$. If the attacker is able to read other parties' shares when $\mathcal{R}$ is collecting or handling them before calling $\mathcal{E}$, it implies that $\mathcal{R}$ should only send requests to $\mathcal{E}$ and not be part of any computations; instead $\mathcal{E}$ or other trusted parties, preferably in secure domains, initiate and perform necessary secure computations before accessing the master key.
\\
\\
If $\mathcal{E}$ is compromised on memory level then there is no means of security left, thus the strongest attack possible.
\\
\\
One may consider investigate in certificateless cryptography as an alternative to TLS and certificates, but this would involve a trusted third party service and protocols based on pairings which may be slower in performance. However, in a recent proof of concept of which Java was used as underlying platform, some evidence of practical usage of certificateless cryptography for securing master keys has been shown \cite{fokin2018secure}.

\section{Conclusion}
It seems like much effort and high complexity of securing a master key in this way; the temptation to just leave it as it is and store the key embedded or in a database is understandable. Also, much of the presented cryptography in this paper has not yet reached a level of confidence nor consensus in industry and that is why we highlight them now. As conjured in the paper's title we assume this is an unsolvable problem but the point is to align towards the security need by making it as hard as possible for an adversary to compromise a master key. By using non-traditional approaches such as multi-party computations as proposed, our analysis is that it would not be too complex to utilize such technology and the security benefits would balance out the effort and time of implementation.

\section{Future work}
Considering the secure channel to be used between parties $P_i$ and $\mathcal{E}$, not only do we have secure segmentation between subnets but we would also like to add a layer of security in case messages are eavesdropped or tampered with. For this we propose a few different approaches that can be explored:
\\
\begin{itemize}
\item{Public-key infrastructure, i.e. use of traditional private-public keypairs for which each $P_i$ uses to connect to HSM server via TLS. Drawback is high maintenance of certificates and some risk associated to TLS vulnerabilities \cite{sirohi2016comprehensive}}
\item{Zero-Knowledge Proof (ZKP) based authentication, i.e. setting up a protocol where the HSM stores a secret \emph{claim} (some data $c_i$) which is unique for each party $P_i$. Then each $P_i$ initiates a ZKP protocol and proves that they know $c_i$ without revealing any data; by doing so the HSM can trust that $P_i$ is eligible to contribute with a share $k_i$.}
\item{Certificateless cryptography, as mentioned above having a trusted third party $\mathcal{T}$ within the secure domain of the network which handles the keys needed for encryption and authentication. Many solutions builds on pairings which may not be efficient enough depending on requirements.}
\end{itemize}
\;\;
Regardless of communication protocols chosen we also see that more research should be put into the domain of securing secret keys, especially in untrusted and dishonest environments. Not only the encryption part but rather schemes or methods for securely retrieving sensitive data without leakage; perhaps one should investigate more in secret data sets, secret sharing, ZKP schemes and similar cryptography. We could also expect more use cases where such secret key retrieval is needed but in environments with distributed computing (cloud) and connected devices (IoT).

\bibliographystyle{plain}