text:
\subsection{Evaluation}

\begin{frame}{Evaluation}
    \begin{itemize}
        \item 46920 different simulations

        \item All results are available at \url{https://github.com/GordonLesti/SlidingWindowFilter-evaluator/releases/download/v1.0.1/swf-result.csv.zip}
    \end{itemize}
\end{frame}

\begin{frame}{Evaluation}{Top $F_{1}score_{\mu}$ Results}
    \begin{center}
        \tiny
        \begin{tabular}{llllllllll}
            \textbf{distance} & \textbf{scb} & \textbf{filter} & \textbf{window} & \textbf{threshold} & \textbf{precision\_$\mu$} & \textbf{recall\_$\mu$} & \textbf{f1score\_$\mu$} & \textbf{\#(nnc)}\\
            \hline
            $\eta$DTW & 36 & LNCE(300) & Mid  & HAveD & 0.8414 & 0.6579 & 0.7384 & 4214\\
            $\eta$DTW & 36 & NoFilter & Mid  & HAveD & 0.8414 & 0.6579 & 0.7384 & 4893\\
            $\eta$DTW & 28 & LNCE(300) & Mid  & HAveD & 0.812 & 0.6725 & 0.7359 & 4170\\
            $\eta$DTW & 28 & NoFilter & Mid  & HAveD & 0.8118 & 0.6719 & 0.7353 & 4841\\
            $\eta$DTW & 36 & VAR(240) & Mid  & HAveD & 0.8399 & 0.6485 & 0.7319 & 2975\\
            $\eta$DTW & 36 & VAR(260) & Mid & HAveD & 0.8399 & 0.6485 & 0.7319 & 3126\\
            $\eta$DTW & 36 & VAR(280) & Mid & HAveD & 0.8399 & 0.6485 & 0.7319 & 3330\\
            $\eta$DTW & 36 & VAR(300) & Mid & HAveD & 0.8399 & 0.6485 & 0.7319 & 3574\\
            $\eta$DTW & 36 & LNCE(220) & Mid & HAveD & 0.8399 & 0.6485 & 0.7319 & 3806\\
            $\eta$DTW & 36 & LNCE(240) & Mid & HAveD & 0.8399 & 0.6485 & 0.7319 & 3929
        \end{tabular}
    \end{center}
\end{frame}

\begin{frame}{Evaluation}{Domination Configuration}
    \begin{center}
        \tiny
        \begin{tabular}{llllllllll}
            \textbf{distance} & \textbf{scb} & \textbf{filter} & \textbf{window} & \textbf{threshold} & \textbf{precision\_$\mu$} & \textbf{recall\_$\mu$} & \textbf{f1score\_$\mu$} & \textbf{\#(nnc)}\\
            \hline
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & LNCE(300) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8414 & 0.6579 & 0.7384 & 4214\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & NoFilter & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8414 & 0.6579 & 0.7384 & 4893\\
            $\eta$DTW & 28 & LNCE(300) & Mid  & HAveD & 0.812 & 0.6725 & 0.7359 & 4170\\
            $\eta$DTW & 28 & NoFilter & Mid  & HAveD & 0.8118 & 0.6719 & 0.7353 & 4841\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & VAR(240) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 2975\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & VAR(260) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 3126\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & VAR(280) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 3330\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & VAR(300) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 3574\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & LNCE(220) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 3806\\
            \textcolor{red}{$\eta$DTW} & \textcolor{red}{36} & LNCE(240) & \textcolor{red}{Mid}  & \textcolor{red}{HAveD} & 0.8399 & 0.6485 & 0.7319 & 3929
        \end{tabular}
    \end{center}
\end{frame}

\begin{frame}{Evaluation}{Simulations ranked by $F_{\frac{1}{2}}score_{\mu}$}
    \begin{center}
        \resizebox {0.5\textwidth} {!} {
            \begin{tikzpicture}[spy using outlines={circle, magnification=6, connect spies}]
                \begin{axis}[
                    xmin=0,
                    xmax=1,
                    ymin=0,
                    ymax=1,
                    width=\axisdefaultwidth,
                    height=\axisdefaultwidth,
                    xlabel=$Precision_{\mu}$,
                    ylabel=$Recall_{\mu}$,
                    samples=100,
                    colorbar horizontal,
                    colormap/viridis high res,
                    title=$F_{\frac{1}{2}}score_{\mu}$]
                    \addplot[only marks, scatter, scatter src=explicit, mark size=1] table[x=x,y=y,meta=fscore] {../data/fig/result/f0.5score.dat};
                    \addplot[gray, domain=0.081:1] {(0.25 * 0.1 * x) / (1.25 * x - 0.1)};
                    \addplot[gray, domain=0.161:1] {(0.25 * 0.2 * x) / (1.25 * x - 0.2)};
                    \addplot[gray, domain=0.25:1] {(0.25 * 0.3 * x) / (1.25 * x - 0.3)};
                    \addplot[gray, domain=0.33:1] {(0.25 * 0.4 * x) / (1.25 * x - 0.4)};
                    \addplot[gray, domain=0.41:1] {(0.25 * 0.5 * x) / (1.25 * x - 0.5)};
                    \addplot[gray, domain=0.49:1] {(0.25 * 0.6 * x) / (1.25 * x - 0.6)};
                    \addplot[gray, domain=0.57:1] {(0.25 * 0.7 * x) / (1.25 * x - 0.7)};
                    \addplot[gray, domain=0.65:1] {(0.25 * 0.8 * x) / (1.25 * x - 0.8)};
                    \addplot[gray, domain=0.73:1] {(0.25 * 0.9 * x) / (1.25 * x - 0.9)};
                    \coordinate (spypoint) at (axis cs:0.8767619815,0.6115168539);
                    \coordinate (magnifyglass) at (axis cs:0.2,0.8);
                \end{axis}
                \spy [size=2cm] on (spypoint)
                    in node[fill=white] at (magnifyglass);
            \end{tikzpicture}
        }
    \end{center}
\end{frame}

\begin{frame}{Evaluation}{Simulations ranked by $F_{1}score_{\mu}$}
    \begin{center}
        \resizebox {0.5\textwidth} {!} {
            \begin{tikzpicture}[spy using outlines={circle, magnification=6, connect spies}]
                \begin{axis}[
                    xmin=0,
                    xmax=1,
                    ymin=0,
                    ymax=1,
                    width=\axisdefaultwidth,
                    height=\axisdefaultwidth,
                    xlabel=$Precision_{\mu}$,
                    ylabel=$Recall_{\mu}$,
                    samples=100,
                    colorbar horizontal,
                    colormap/viridis high res,
                    title=$F_{1}score_{\mu}$]
                    \addplot[only marks, scatter, scatter src=explicit, mark size=1] table[x=x,y=y,meta=fscore] {../data/fig/result/f1score.dat};
                    \addplot[gray, domain=0.051:1] {(0.1 * x) / (2 * x - 0.1)};
                    \addplot[gray, domain=0.11:1] {(0.2 * x) / (2 * x - 0.2)};
                    \addplot[gray, domain=0.16:1] {(0.3 * x) / (2 * x - 0.3)};
                    \addplot[gray, domain=0.21:1] {(0.4 * x) / (2 * x - 0.4)};
                    \addplot[gray, domain=0.26:1] {(0.5 * x) / (2 * x - 0.5)};
                    \addplot[gray, domain=0.31:1] {(0.6 * x) / (2 * x - 0.6)};
                    \addplot[gray, domain=0.36:1] {(0.7 * x) / (2 * x - 0.7)};
                    \addplot[gray, domain=0.41:1] {(0.8 * x) / (2 * x - 0.8)};
                    \addplot[gray, domain=0.46:1] {(0.9 * x) / (2 * x - 0.9)};
                    \coordinate (spypoint) at (axis cs:0.8413867433,0.6578651685);
                    \coordinate (magnifyglass) at (axis cs:0.2,0.8);
                \end{axis}
                \spy [size=2cm] on (spypoint)
                    in node[fill=white] at (magnifyglass);
            \end{tikzpicture}
        }
    \end{center}
\end{frame}

\begin{frame}{Evaluation}{Simulations ranked by $F_{2}score_{\mu}$}
    \begin{center}
        \resizebox {0.5\textwidth} {!} {
            \begin{tikzpicture}[spy using outlines={circle, magnification=6, connect spies}]
                \begin{axis}[
                    xmin=0,
                    xmax=1,
                    ymin=0,
                    ymax=1,
                    width=\axisdefaultwidth,
                    height=\axisdefaultwidth,
                    xlabel=$Precision_{\mu}$,
                    ylabel=$Recall_{\mu}$,
                    samples=100,
                    colorbar horizontal,
                    colormap/viridis high res,
                    title=$F_{2}score_{\mu}$]
                    \addplot[only marks, scatter, scatter src=explicit, mark size=1] table[x=x,y=y,meta=fscore] {../data/fig/result/f2score.dat};
                    \addplot[gray, domain=0.021:1] {(4 * 0.1 * x) / (5 * x - 0.1)};
                    \addplot[gray, domain=0.041:1] {(4 * 0.2 * x) / (5 * x - 0.2)};
                    \addplot[gray, domain=0.061:1] {(4 * 0.3 * x) / (5 * x - 0.3)};
                    \addplot[gray, domain=0.081:1] {(4 * 0.4 * x) / (5 * x - 0.4)};
                    \addplot[gray, domain=0.101:1] {(4 * 0.5 * x) / (5 * x - 0.5)};
                    \addplot[gray, domain=0.121:1] {(4 * 0.6 * x) / (5 * x - 0.6)};
                    \addplot[gray, domain=0.141:1] {(4 * 0.7 * x) / (5 * x - 0.7)};
                    \addplot[gray, domain=0.17:1] {(4 * 0.8 * x) / (5 * x - 0.8)};
                    \addplot[gray, domain=0.19:1] {(4 * 0.9 * x) / (5 * x - 0.9)};
                    \coordinate (spypoint) at (axis cs:0.8124893942,0.6724719101);
                    \coordinate (magnifyglass) at (axis cs:0.2,0.8);
                \end{axis}
                \spy [size=2cm] on (spypoint)
                    in node[fill=white] at (magnifyglass);
            \end{tikzpicture}
        }
    \end{center}
\end{frame}

\input{experiment/evaluation/influence_of_time_series_distance_measure.tex}
\input{experiment/evaluation/influence_of_window_size_determination.tex}
\input{experiment/evaluation/influence_of_threshold_determination.tex}
\input{experiment/evaluation/influence_of_sliding_window_filter.tex}
\input{experiment/evaluation/differentiation_according_to_gestures.tex}
\input{experiment/evaluation/differentiation_according_to_experimentees.tex}

max_stars_repo_name: GordonLesti/SlidingWindowFilter

max_issues_repo_name: GordonLesti/SlidingWindowFilter

max_forks_repo_name: GordonLesti/SlidingWindowFilter


text:
\documentclass[onecolumn]{article}
\usepackage{lscape}
\begin{document}
\begin{landscape}
\title{04 - Example 01 - Ideal Solution}
\author{}
\date{}
\maketitle
\section{Example 01 - Ideal Solution} % (fold)
Ideal solution:
Example, 7 components, 3 reactions: \\
\begin{tabular}{llcll|l}
\hline
$H_2SO_3$ & + $H_2O$ & $\rightleftharpoons$ & $H_3O(+)$ & + $HSO_3(-)$ & $pKa_1=1.856985200$ \\
$HSO_3(-)$ & + $H_2O$ & $\rightleftharpoons$ & $H_3O(+)$ & + $SO_3(2-)$ & $pKa_2=7.171984936$ \\
$H_2O$ & + $H_2O$ & $\rightleftharpoons$ & $H_3O(+)$ & + $OH(-)$ & $pKa_3=13.99567863$\\
\hline
\end{tabular}
\\
(1) $Kc_1 \times Ce_{H_2O} = 10^{-1.856985200} = \frac{Ce_{H_3O(+)} \times Ce_{HSO_3(-)}}{Ce_{H_2SO_3}}$
\\
(2) $Kc_2 \times Ce_{H_2O} = 10^{-7.171984936} = \frac{Ce_{H_3O(+)} \times Ce_{SO_3(2-)}}{Ce_{HSO_3(-)}}$
\\
(3) $Kc_3 \times Ce_{H_2O}^2 = 10^{-13.99567863} = Ce_{H_3O(+)} \times Ce_{OH(-)}$\\
\\
\begin{tabular}{ll}
\hline
$C_{0,H2SO3}$ & = 0 mol/L\\
$C_{0,HSO3(-)}$ & = 5.10E+00 mol/L \\
$C_{0,SO3(2-)}$ & = 0 mol/L \\
$C_{0,H3O(+)}$ & = 1.00E-07 mol/L \\
$C_{0,OH(-)}$ & = 1.01E-07 mol/L \\
$C_{0,H2O}$ & = 5.54E+01 mol/L \\
$C_{0,Na(+)}$ & = 5.10E+00 mol/L \\
\hline
\end{tabular}
\\
\begin{tabular}{llllllllllll}
(4) 0 &= -$C_{H2SO3}$  &  &  &  &  &  &  &  & -$\xi_1$ & & \\
(5) $-5.10\frac{mol}{L}$ &=  & -$C_{HSO3(-)}$  &  &  &  &  &  &  & +$\xi_1$ & -$\xi_2$ &  \\
(6) 0 &=  &  &  -$C_{SO3(2-)}$  &  &  &  &  &  &  & +$\xi_2$ &  \\
(7) $-1.00 \times 10^{-7} \frac{mol}{L}$ &=  &  &  & -$C_{H3O(+)}$  &   &  &  &  & +$\xi_1$ & +$\xi_2$ & +$\xi_3$  \\
(8) $-1.01 \times 10^{-7} \frac{mol}{L}$  &= &  &  &  & -$C_{OH(-)}$  &  &  &  &  & & +$\xi_3$ \\
(9) $-55.4 \frac{mol}{L}$  &= &  &  &  &  & -$C_{H2O}$  &  &  & -$\xi_1$ & -$\xi_2$ & -2$\xi_3$ \\
(10) $-5.10\frac{mol}{L}$ &= &  &  &  &  &  &  & -$C_{Na(+)}$ &  &  & \\
\end{tabular}
\\
Non-linear system to solve in matrix form:
\\
\[
\left(
\begin{tabular}{cccccccccc}
-1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\
0 & -1 & 0 & 0 & 0 & 0 & 0 & +1 & -1 & 0 \\
0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & +1 & 0 \\
0 & 0 & 0 & -1 & 0 & 0 & 0 & +1 & +1 & +1 \\
0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & +1 \\
0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & -1 & -2 \\
0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\
0 & $\frac{Ceq_{H_3O(+)}}{Ceq_{H_2SO_3}}$ &
& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & $\frac{Ceq_{SO_3(2-)}}{Ceq_{HSO_3(-)}}$ &
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & $C_{H_3O(+)}$ & 0 & 0 & 0 & 0 & 0 & 0
\end{tabular}
\right)
\times
\left(
\begin{tabular}{c}
$Ceq_{H2SO3}$ \\
$Ceq_{HSO3(-)}$ \\
$Ceq_{SO3(2-)}$ \\
$Ceq_{H3O(+)}$ \\
$Ceq_{OH(-)}$ \\
$Ceq_{H2O}$ \\
$Ceq_{Na(+)}$ \\
$\xi eq_1$ \\
$\xi eq_2$ \\
$\xi eq_3$ \\
\end{tabular}
\right)
=
\left(
\begin{tabular}{c}
0 mol/L\\
5.10E+00 mol/L \\
0 mol/L \\
1.00E-07 mol/L \\
1.01E-07 mol/L \\
5.54E+01 mol/L \\
5.10E+00 mol/L \\
$10^{-1.856985200}$ \\
$10^{-7.171984936}$ \\
$10^{-13.99567863}$ \\
\end{tabular}
\right)
\]
\\
\end{landscape}
\end{document}

ext: tex


text:
\chapter{The foundations of mathematics}

\chlabel{fund}

\input{sec1}
\input{sec2}
\input{sec3}
\input{sec4}
\input{exer}

max_stars_repo_name: gonzalezcastillo/leavingthecave

max_issues_repo_name: gonzalezcastillo/leavingthecave

max_forks_repo_name: gonzalezcastillo/leavingthecave


text:
% TEMPLATE for Usenix papers, specifically to meet requirements of
%  USENIX '05

% See http://static.usenix.org/events/samples/template.la for examples.

% Note that since 2010, USENIX does not require endnotes. If you want
% foot of page notes, don't include the endnotes package in the
% usepackage command, below.

%
% This is a pre-publication paper which we intend to submit to FOCI-14
% While the FOCI14 event has no home page, the previous one was:
%   https://www.usenix.org/conference/foci13
%

\documentclass[letterpaper,twocolumn,10pt]{article}
\usepackage{usenix,epsfig,amssymb,amsmath,url}
\begin{document}
\date{}

\title{
\Large \bf Going Dark: Phrase Automated Nym Discovery Authentication\\
\small or,\\
Finding friends and lovers using the PANDA protocol to re-nymber after everything is lost\\
\small or, \\
discovering new Pond users easily
}

\author{
{\rm Jacob Appelbaum}\\
\and
{\rm another cypherpunk}\\
}

\maketitle

% Use the following at camera-ready time to suppress page numbers.
% Comment it out when you first submit the paper for review.
\thispagestyle{empty}

\subsection*{Abstract}

We consider the problem of two parties seeking to establish secure
communications given {\it only} a shared secret.

Communication between two parties relies on in-band and out-of-band methods
when addressing identifiers change or when they are not yet known to the
interested parties. We summarize similar problems and present a brief overview
of previous attempts at solving the presented problems. Finally we propose a
system, which we have implemented, by which a pair or a group of people or
machines may derive new identifiers using only a password or shared key. Thus
we remove the requirement that any other communication must occur before
re-establishing entirely new identifiers.

\section{Introduction}

% we should rephrase this to not be so closely worded to the Abstract
We propose a system by which a pair or a group of people or machines may derive
new identifiers using only a password or shared key in a forward secret manner.
Additionally, we propose using this shared secret as the basis for
authentication, key exchange and as a discovery process for other identifiers.
We have implemented the described system and describe the specifics of our
implementation.

\section{The context of modern communication systems}
\label{sec:context}

Modern communication systems are designed with intentional flaws such as
CALEA\cite{CALEA} and with an adversaries that have budgets in the tens of
billions of US dollars\cite{NSABUDGET}. Adversaries such as the NSA
specifically attempt to sabatoge cryptographic projects\cite{BULLRUN} used in
the creation of secure communications systems. The current global
communications network allow for dragnet surveillance based on so-called {\it
selectors} and even world leaders\cite{MERKELPHONE} are not exempt from such
surveillance. Static identifiers such as telephone numbers, email addresses,
hardware serial numbers and other unique identifiers ensure linkability across
vast datasets as the core of selector based surveillance.
% XXX: should we cite something about selector based surveillance? Perhaps?

\section{An overview of similar problems and their respective solutions}

Users face many similar discovery or re-discovery problems in common daily
life. Usually these problems are resolved with a hybrid of social and
centralized solutions where a third party is not treated as an adversary.

\subsection{The telephone re-numbering problem}
\label{renumber:telephone}

Telephone numbers change for various reasons. After a new number or a new
device with a new number is issued, a kind of discovery process is started
whereby the party may start to use the new number exclusively. It is also
possible that the old number will link to the new number or only release the
new number as it has superseded the original number.

Telephone numbers are generally not user selected but are rather issued by a
central authority; so called vanity numbers may be selected for a fee from
some operators.

The process of renumbering a telephone is generally solved in five different
ways. The first may come in the form of a message provided by the operator
that discloses the new number and disconnects the caller after an automated
message. The second is socially or through a publication of some kind;
generally when two people meet a new number may be disclosed or when a known
distribution point such as a newspaper begins to print new numbers. The third
is through a party reading the caller information from their received call or
SMS list or by reviewing their bill. The fourth is through
misclosure\cite{kellycaine}, perhaps by a third party who may or may not be
authorized to disclose this information. The fifth is through a central listing
service of some kind, such as a phonebook, published by a network operator.

\subsection{The social nickname re-naming problem}
\label{rename:social-nickname}

People generally have full legal names and names by which they are known
socially. These full legal name mappings change through various legal means
that are out of scope. Nicknames are commonly held names that otherwise have
little or no legal status - when a party changes their nickname, they suffer
from the same issues faced by telephone renumbering\ref{renumber:telephone}.
Unlike telephone re-numbering, generally a person or group may pick any name
they choose as a new nickname. Such new nicknames may collide and cause
confusion though largely this may be irrelevant for a social group that has
other social identifiers.

\subsection{The nym renyming problem}

Electronic identities generally suffer from the same issues as telephone
renumbering\ref{renumber:telephone} and re-naming\ref{rename:social-nickname}
with the additional complexity of not having a central authority or out-of-band
communications methods by which to reconnect.

\subsection{The problem created by data loss}
\label{sec:problem}

Systems are often stolen or compromised in a way that results in total
dataloss for the user. In some cases the data may be compromised after a
variable window of time and in such a window, automatically changing
indentifiers may prevent full and on-going compromise of a pair-wise
communications channel.

\section{Gently Rockin' Zooko's Triangle}
\label{sec:zooko}

Zooko's Triangle\cite{zookostriangle} is generalized as having the choice
between any two of the following three properties when designing a naming
system: secure, decentralized and human-meaningful. In the original Domain Name
System, a domain name is decentralized and human-meaningful. In
Pond\cite{pond}, the addressing system properties are secure and decentralized.

We propose that for a brief window of time that users should have a way to
change the chosen properties of the naming system.  We assert that trading the
secure property for the human-meaningful property in the form of phrases may be
useful trade-off in a time limited, forward secure fashion.

Furthermore, we note that Zooko's Triangle is missing an important qualifier,
which is the passing of time and its relationship with each of the properties.

\section{PANDA}

The PANDA protocol uses EKE2, Diffie-Hellman, a pre-arranged meeting point and
a slow memory intensive key derivation process.

\subsection{EKE2}

EKE2 is very similar to SPAKE2 but uses an ideal cipher to encrypt the
Diffie-Hellman values rather than masking them with secret group elements. EKE2
is used to go from a shared-secret to an ephemeral shared-key and then the
KeyExchange messages are encrypted with that key and exchanged via the second
meeting ID.

\subsection{Diffie-Hellman}

Our Diffie-Hellman group of choice is curve25519\cite{bernstein2006curve25519}
which results in a 255-bit Diffie-Hellman value, which is larger than the
128-bit block size of most ciphers.

\subsection{Password Authenticated Key Exchange}

This problem falls into the topic of Password Authenticated Key Exchange
(PAKE), which is a well studied problem. The first PAKE, Encrypted Key Exchange
(EKE), was described by Bellovin and Merritt\cite{bellovin1992encrypted} in
1992. However, we have one additional requirement: that the protocol execute in
a single round. We define a round as a message sent by each party
simultaneously, thus a message in a given round cannot depend on any other
message in the same round.  We are imposing this requirement as our meeting
point may have very high latency and we have no way of assigning the labels
`client' and `server' to our parties.  Many PAKE protocols implicitly assume
that the parties can behave differently based on these labels (including the
original EKE), but our parties have {\it only} a shared secret. An exchange of
messages could be used to break this symmetry but the additional latency is
undesirable.

The authors are most familiar with Simple Password-Based Encrypted Key Exchange
Protocols number two (SPAKE2)\cite{abdalla2005simple}, but SPAKE2 appears to be
unsuitable because it masks Diffie-Hellman values with a mask value raised to
the power of the password and requires different mask values for the two
parties. Due to our symmetry requirement the two parties would have to use the
same value mask. We have proven that the chosen computational Diffie Hellman
(CCDH) problem from the SPAKE paper is equally strong when the two mask values
are equal, however the mask values appear again in the security proof and it's
not obvious how to patch that second hole.
% XXX: This last sentence could use some rewording to make it clearer

We have chosen to use Encrypted Key Exchange two
(EKE2)\cite{bellare2000authenticated} as our PAKE. EKE2 is very similar to
SPAKE2 but uses an ideal cipher to encrypt the Diffie-Hellman values rather
then masking them with secret group elements.

Using a typical block cipher mode would
result in an attacker having a discomforting amount of control of the resulting
plaintext. Using an Authenticated Encryption with Associated Data (AEAD) mode
would give an attacker an authenticator which they could use to mount an
offline, brute-force attack on the shared secret\footnote{The attacker may
already be able to mount an offline, brute-force attack on the shared secret by
using an identifier revealed to the meeting point. But we still don't want to
give them another avenue for this attack in case a particular meeting point
doesn't require that}. A wide-block
construction like LIONESS\cite{anderson1996two} doesn't appear to be
applicable because the 256-bit block is too small to split into usefully sized
left and right parts for the Luby-Rackoff construction. Many other wide-block
constructions have subsequently been proposed including
EME\cite{halevi2004parallelizable}, CMC\cite{halevi2004parallelizable},
XCB\cite{mcgrew2004extended}, HCTR\cite{wang2005hctr} and others. However, the
area is a patent minefield.

We instantiate the ideal-cipher for EKE2 with a 256-bit block
Rijndael\cite{daemen2002design}. Although AES specified only a 128-bit block
size, Rijndael was originally specified with 128, 192 and 256-bit block sizes.
It's very uncommon to find an Rijndael implementation that implements a 256-bit
block size but since performance isn't a concern and nor are side-channels, a
custom, toy Rijndael implementation is sufficient.

\subsection{Meeting points}

We propose agreeing on a meeting point, such as an address or name of a
centralized HTTP server, one hosted on a Tor Hidden
Service\cite{Dingledine04tor:the}, or the use of a
decentralized key value store system.

Once we have established a meeting point, the two parties need to bootstrap
their shared secret into a cryptographic key exchange and a more efficient
method of communicating in the future.\footnote{For example, the parties may wish to
exchange OpenPGP public keys and email addresses in a confidential and
authentic fashion. As a further example, Pond users may discover the
keys for their peers with such a system.}
% add \cite for OpenPGP

\subsection{Key and meeting point derivation}

Each PANDA user computes a tag and a key as part of a key derivation process.
This process utilizes scrypt\cite{scrypt} to slow brute force or
even well chosen dictionary attacks.
% XXX: We should describe this process in more detail

\section{Key exchange details in practice with Pond}

Pond supports two methods of key exchange. The first is manual: the KeyExchange
messages are serialised with Privacy-enhanced Electronic Mail (PEM)\cite{pem}
and the user is expected to exchange them with the intended contact,
authentically and confidentially. For example, a pre-existing relationship with
Pretty Good Privacy (PGP)\cite{pgp} or Off-The-Record (OTR)\cite{otr} keys
could be used to bootstrap Pond.

We implemented\cite{panda} the PANDA discovery technique for the
Pond\cite{pond} messaging system as the second method of key exchange. PANDA
allows a relationship to be established via a shared-secret. This works by
using a {\it meeting point} which, currently, involves contacting a central
HTTPS server over the Tor\cite{Dingledine04tor:the} network. The shared secret is processed with
scrypt\cite{scrypt} into a key and two {\it meeting} IDs. The meeting point
simply acts as a pinboard where messages can be posted to a given meeting ID.
If a different message has already been posted to the same ID then it's
returned. The meeting point only allows two different messages to exist for a
given meeting ID until it's garbage collected (in about a week).

\subsection{Pond key exchange details}

The Pond key exchange between two users involves each creating a KeyExchange
protobuf\cite{pondprotobufs}. Since Pond servers demand a group signature
before accepting a message for delivery, there are no public Pond addresses
that can be used to bootstrap a Pond relationship.  Rather we currently assume
an external, confidential and authentic means for users to exchange KeyExchange
messages.

A Pond KeyExchange message contains a group member private key (which is why
they need to be confidential), as well as the information needed to direct a
message to a user: their home server address and the user's public identity at
that server.  They also contain an Ed25519 key and the intent is that, in the
future, users will be able to update their home servers by sending messages to
each of their contacts. Group member revocations are also be signed by this
key.

\subsection{Adding entropy to a human-meaningfully memorable phrase}

The shared secret itself can consist of a passphrase, a time, and a deck or two
of cards. Since humans are poor at generating and remembering secrets, a deck
of cards, shuffled and split in half, serves quite well. Decks of cards are also
commonly available and don't have the downsides that bringing a mobile device
to a meeting might have.

Although the two halves of the deck are different, they are sufficient to
define a common, canonical set of cards. For Pond, the cards are ordered and
the canonical half is the one with the majority of the lowest numbered card. If
both halves have the same number of the lowest numbered card then the next
lowest is considered. If each half has exactly the same cards then both are
canonical.

A single deck of cards results in an approximately 49 bit shared secret and two
decks is 100 bits. The stacks of cards are a problem to dispose of (unlike a
memory, they can be obtained by dumpster diving) but they only need to be
protected until the key exchange is complete. After that they are no longer
sensitive.

While we haven't implemented further entropy sources, we believe that many
common household objects may also serve as a time limited entropy source. As an
example, additional entropy could be added from other sources such as the state
of a Rubik's cube or a similar object.

\section{Conclusion}

Our design allows a pair or a group of people to discover or rediscover
each-other with knowledge of only a shared secret or human memorable
passphrase with optional entropy sources. Additionally, we believe that it
provides forward secrecy against attackers who wish to correlate names even
after a full client compromise.

\section*{Acknowledgements}

We would like to thank Leif Ryge, Steve Weis, Ralf Philip-Weinmann, Julian
Assange and other anonymous cypherpunks who contributed valuable feedback in
the creation of this design.

{\footnotesize \bibliographystyle{acm}
\bibliography{bibliography}}

\end{document}

max_stars_repo_name: ioerror/pond

max_issues_repo_name: ioerror/pond

max_forks_repo_name: ioerror/pond


text: \subsection{Entry Rate (ER)}

max_stars_repo_name: adamdboult/nodeHomePage

max_issues_repo_name: adamdboult/nodeHomePage

max_forks_repo_name: adamdboult/nodeHomePage


text:
\documentclass{article}

\usepackage[magicref]{mttex}

\newcommand{\newtmetavar}{\newmetavar{\tfontsym}{\tcolor}{t}}
\newcommand{\newsmetavar}{\newmetavar{\sfontsym}{\scolor}{s}}

\newtmetavar{x}
\newtmetavar{e}
\newtmetavar*{alpha}{\tfontsym{\alpha}}
\newtmetavar{v}
\newtmetavar*{ty}{\tfontsym{\tau}}

\newcommand{\newsmetavars}{\newmetavars{\sfont}{\scolor}{s}}
\newcommand{\newsmetavarsS}{\newmetavarsS{\sfontsym}{\scolor}{s}}
\newsmetavars{x, e, v}
% TODO Star convention is difficult over lists
%\newsmetavars*{x/x, e/e, v/v}
\newsmetavarsS{ty/\sigma, alpha/\alpha}

\newcommand{\stcolor}{\mathcolor{orange}}
\newcommand{\stfont}[1]{\stcolor{\mathbf{#1}}}
\newcommand{\stfontsym}{\stfont}

\newcommand{\newstmetavars}{\newmetavars{\stfont}{\stcolor}{st}}
\newcommand{\newstmetavarsS}{\newmetavarsS{\stfontsym}{\stcolor}{st}}
\newstmetavarsS{x/x, v/v, e/e, world/W, alpha/\alpha}

\newcommand{\trelV}{\lr{\tfontsym}{V}}
\newcommand{\srelE}{\lr{\sfont}{E}}

\newcommand{\newttypes}{\newtypes{\tfontsym}{\tfont}{t}{ty}}
\newcommand{\newtexprs}{\newexprs{\tfontsym}{\tfont}{te}{}}
\newttypes{fun,polyfun,forall,exist,mu,bool,unit,void,pair}
\newtexprs{let,fun,polyfun,app,papp,abstr,inst,pack,unpack,fold,unfold,if,true,false,unit,pair}

\newcommand{\tpfunty}{\tpolyfunty}

\newcommand{\sfune}{\fune{\sfontsym}{\sfont}}
\newcommand{\spolyfune}{\polyfune{\sfontsym}{\sfont}}
\newcommand{\sabstre}{\abstre{\sfontsym}{\sfont}}
\newcommand{\sinste}{\inste{\sfontsym}{\sfont}}
\newcommand{\sappe}{\appe{\sfontsym}{\sfont}}
\newcommand{\spappe}{\pappe{\sfontsym}{\sfont}}

\newcommand{\sexistty}{\existty{\sfontsym}{\sfont}}

\newcommand{\sife}{\ife{\sfontsym}{\sfont}}
\newcommand{\spacke}{\packe{\sfontsym}{\sfont}}
\newcommand{\sunpacke}{\unpacke{\sfontsym}{\sfont}}
\newcommand{\slete}{\lete{\sfontsym}{\sfont}}
\newcommand{\sfolde}{\folde{\sfontsym}{\sfont}}
\newcommand{\sunfolde}{\unfolde{\sfontsym}{\sfont}}
\newcommand{\sunite}{\unite{\sfontsym}{\sfont}}
\newcommand{\struee}{\truee{\sfontsym}{\sfont}}
\newcommand{\sfalsee}{\falsee{\sfontsym}{\sfont}}
\newcommand{\spaire}{\paire{\sfontsym}{\sfont}}

\newcommand{\txdubpr}{\txpr[2]}

\newcommand{\sttfont}[1]{\mathit{#1}\!\!}
\newmetavarsS{\mathit}{}{stt}{world/W}

\begin{document}
\tableofcontents
\listoftodos
\begin{mathpar}
  \metavar{\tfont{x}}{\tcolor{1}}{}{\tprime}{1}

  \metavar{\tfont{x}}{\tcolor{1}}{}{\tprime}{4}

  \txmetavar{}{}{0}

  \txmetavar{}{}{1}

  \tx

  \tx^1

  \tx^1_1

  %should cause an error
  %\txin{1}_1

  \txpr_1

  \tx'_1

  \tx'^1_1

  % should look worse than
  \tx\tfont{'}^1_1
  \txmetavar{1}{1}{1}

  \tx_1

  \tx^{+}

  \txpr

  \txdubpr

  \txpr[5]

  \txone

  \txonepr

  \txtwo

  \txtwopr

  \te

  \tvone

  \temetavar{}{}{0}

  \trelV{\tty}

  \srelE{\stypr}

  \lrV{\tfont}{\tty}

  \tfont{\Gamma}

  \tfontsym{\Gamma}

  \tfunty{\ttyone}{\ttytwo}

  \tpfunty{\talpha}{\ttyone}{\ttytwo}

  \tforallty{\talpha}{\tty}

  \texistty{\talpha}{\tty}

  \tmuty{\talpha}{\tty}

  \tunitty

  \tvoidty

  \tboolty

  \tpairty{\ttyone}{\ttytwo}

  \tefun{\tx}{\tty}{\teone}

  \tetrue

  \tefalse

  \sfune{\sx}{\sty}{\seone}

  \spolyfune{\salpha}{\sx}{\sty}{\sepr}

  \sabstre{\salpha}{\sty}

  \sinste{\se}{\sty}

  \sappe{\seone}{\setwo}

  \spappe{\seone}{\stypr}{\setwopr}

  \sife{\sv}{\seone}{\setwo}

  \spacke{\styone}{\se}{\sexistty{\salpha}{\stytwo}}

  \sunpacke{\salpha}{\sx}{\svpr}{\seone}

  \telet{\tx}{\te}{\teone}

  \slete{\sx}{\se}{\seone}

  \sfolde{\tmuty{\salpha}{\styone}}{\sty}

  \sunfolde{\seone}

  \sunite

  \struee

  \sfalsee

  \spaire{\seone}{\svtwopr}

  \stx

  \stalphaonepr

  \stxpr[100]
  \stxonepr[5]

  \ctxtyjudg{\tfont}{\tfont{\ectx}}{\tfont{\Gamma}}{\tty}{\tfont{\Gamma}}{\ttypr}

  \ciueqvjudg{\tfont{\Gamma}}{\te}{\tepr}{\tty}

  \ctxeqvjudg{\tfont{\Gamma}}{\te}{\tepr}{\tty}

  \rho

  \mapat{\rho}{\talpha}

  \maponeat{\rho}{\talpha}

  \maptwoat{\rho}{\talpha}

  \maprelat{\rho}{\talpha}

  \mapext{\rho}{\talpha}{\tty}

  \te \bnfdef \tx \bnfalt \tefun \tx \tty \te \bnfalt \teapp \te \tepr

  \sttworldin{1}
  W_1
  \metavar{\mathit{W}}{1}{}{}{0}
  \metavar{\mathit{W}}{\stcolor{1}}{}{}{0}

  \metavar{\stcolor{W}\!}{\stcolor{1}}{}{}{0}
  \stcolor{\mathit{W}}_{\stcolor{1}}
  \mathit{\stcolor{W}\!}_{\stcolor{1}}
  \mathit{W}_{\stcolor{1}}

  \stworldto{1}
  \sttworldto{1}
  W^1
  \mathit{W}^1

  \sttworld\!._2
  \metavar{\mathit{W}}{}{}{}{0}._2
  \metavar{W}{}{}{}{0}._2
  \metavar{\stcolor{W}\!}{}{}{}{0}._2
  W._2

\end{mathpar}

%{
%  \newcommand{\meow}{meow}
%
%}
%\meow

\begin{proof}
  Meow
\end{proof}

\begin{proof}[invalid]
  Bark
\end{proof}

\todo{Finish proof}

\subsubsection{Meow}
Meow

\section{Meow}
\label{sec:meow}

\begin{lemma}[Foo] \label{lem:foo} \end{lemma}
\begin{lemma} \label{lem:anon} \end{lemma}

Should be ``Foo'': \nameref{lem:foo}

Should be ``'': \nameref{lem:anon}

Should be ``Foo'' without a hyperlink: \nameref*{lem:foo}

\fullref{lem:foo} produces ``Lemma 1.1 (Foo)''.

\fullref{lem:anon} produces ``Lemma 1.2''

\fullref[Bar]{lem:anon} produces ``Lemma 1.2 (Bar)''

\fullref[]{lem:foo} produces ``Lemma 1.1''

\fullref*{Lemma}{lem:foo} produces ``Lemma 1.1 (Foo)''.

\fullref*{Thing}{lem:foo} produces ``Thing 1.1 (Foo)''.

\fullref*[]{Thing}{lem:foo} produces ``Thing 1.1''.

\end{document}

max_stars_repo_name: jsarracino/mttex

max_issues_repo_name: jsarracino/mttex

max_forks_repo_name: jsarracino/mttex


text:
\chapter{Linear equations}
\section{Linear independent set}
Let $X$ be any vector space. If vectors $\vect{a_1},\vect{a_2},\ldots ,\vect{a_n} \in X$, then for any scalars $s_1,s_2,\ldots ,s_n \in \mathbb{R}$, the vector
\[ \vect{x}=\sum^n_{i=1}s_i \vect{a_i} \]
is called \emph{a linear combination} of $\vect{a_1},\vect{a_2},\ldots ,\vect{a_n}$.
Let $S$ be a set of vectors $S=\lbrace \vect{a_1},\vect{a_2},\ldots ,\vect{a_n} \rbrace$, where all vectors in $S$ belong to the same vector space $X$. Denote the zero-element of vector space $X$ as $\overline{0}$. If the set $S$ is \emph{linearly independent} then   a linear combination of vectors in $S$ equals zero-element if and only if all scalars in the linear combination are zero.
\[ \sum^n_{i=1}s_i \vect{a_i} = \overline{0} \Leftrightarrow s_i = 0, \forall i \in \lbrace 1,2,\ldots ,n \rbrace \]
\begin{example}
Let $X=\mathbb{R}^2$ and $S=\lbrace \vect{a_1},\vect{a_2}\rbrace$, where $\vect{a_1}=(2,4)$ and $\vect{a_2}=(1,2)$. We have
\begin{meq*}
    s_1\vect{a_1} + s_2\vect{a_2} = \overline{0} & \Leftrightarrow & s_1\cvect{2,4} + s_2\cvect{1,2} = \cvect{0,0} \\
    \Leftrightarrow
    \begin{cases}
        2s_1 + s_2 &= 0 \\
        4s_1 + 2s_2 &= 0
    \end{cases}
    & \Leftrightarrow & s_2=-2s_1
\end{meq*}
Thus, the set $S$ is not linearly independent. Notice that the equation $s_2=-2s_1 $ indicates $\vect{a_1},\vect{a_2}$ are on the same line in the two-dimensional coordinate system. We can use $\vect{a_1}$ to define $\vect{a_2}$ based on the equation $s_2=-2s_1$, and vice versa $\vect{a_1}$ can be defined by $\vect{a_2}$.
\end{example}
\begin{example}
Let $X=\mathbb{R}^2$ be a vector space and $S=\lbrace \vect{a_1},\vect{a_2}\rbrace$, where $\vect{a_1}=(2,4)$ and $\vect{a_2}=(-1,2)$. We have
\begin{meq*}
    s_1\vect{a_1} + s_2\vect{a_2} = \overline{0} & \Leftrightarrow & s_1\cvect{2,4} + s_2\cvect{1,2} = \cvect{0,0} \\
    \Leftrightarrow
    \begin{cases}
        2s_1 - s_2 &= 0 \\
        4s_1 + 2s_2 &= 0
    \end{cases}
    & \Leftrightarrow &
    \begin{cases}
        s_2 &= 2s_1 \\
        s_2 &= -2s_1
    \end{cases}
    \Leftrightarrow s_2=s_1=0
\end{meq*}
Thus, the set $S$ is linearly independent. Notice that the equation $s_2=s_1=0$ indicates there is no way to define $\vect{a_1}$ using $\vect{a_2}$, or vice versa.
\end{example}
\begin{example}
Show that vectors $\vect{u},\vect{v}\in \mathbb{R}^5$ does not form a linearly independent set if $\vect{u}=(-1,0,8,5,2)$ and $\vect{v}=(-6,0,48,30,12)$.\par
The set $\lbrace \vect{u},\vect{v} \rbrace$ is linearly independent if and only if
\begin{equation}
\label{ex1-5}
s_1\vect{u} + s_2\vect{v} = \overline{0} \Leftrightarrow s_1=s_2=0
\end{equation}
We have $s_1\vect{u} + s_2\vect{v} = \overline{0}$ is equivalent to
\begin{equation*}
\begin{cases}
-s_1-6s_2 &=0 \\
8s_1+48s_2 &=0 \\
5s_1+30s_2 &=0 \\
2s_1+12s_2 &=0
\end{cases}
\end{equation*}
All of these equations are equivalent to $s_1+6s_2=0$. There are an infinite number of solutions to this equations, which does not satisfies \eqref{ex1-5}.
\end{example}
Let $X$ be a vector space and the set $A \subseteq X$ is linearly independent. If any vectors $\vect{u}\in X$ is a linear combination of vectors in $A$, then $A$ is a \emph{base of X}. Any set which you can prove is linearly independent and its span is the whole space, is a basis of the vector space.

\section{System of linear equations}
\label{linear-eq}
Given $\vect{A}$ an n-square matrix and two column vectors $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. The system of n linear equations in n unknowns is equivalent to the matrix equation: \[ \vect{A}\vect{x}=\vect{b} \]
The matrix $\vect{A}$ is called the \emph{coefficient matrix}. The collection of all columns in $\vect{A}$ form a lineary independent set (rank of $\vect{A}$ is n) iff $\dt{A}\neq 0$. This also means that there exists a unique solution for the equation. On the other hand, if $\dt{A}=0$, then either of two cases occurs: the system has no solutions, or there are an infinite number of solutions. This notebook introduces three matrix-related solutions to solve System of linear equations: Inverse matrix, Crammer's rule, Gaussian elimination.
\subsection{Inverse matrix}
Given the matrix equation $\vect{A}\vect{x}=\vect{b}$ where $\vect{A}$ is an n-square matrix, $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. If  $\dt{A}\neq 0$, then $\vect{A}$ is invertible and there is a unique solution to the equation: \[ \vect{x}=\inverse{A}\vect{b} \]
Observe that this method only works if the determinant of the coefficient matrix is nonzero.
\begin{example}
Solve the following system of equation:
\begin{equation}
\begin{cases}
    2x_1+4x_2 &= 8 \\
    7x_1-2x_2 &= 4
\end{cases}
\label{apple}
\end{equation}
Let define matrix $\vect{A}$, $\vect{x}$, and $\vect{b}$ as follow:
\[ \vect{A}=\smtrx{2,4\\ 7,-2} \quad \vect{x}=\cvect{x_1,x_2} \quad \vect{b}=\cvect{8,4} \]
The system of equations is equivalent to
\begin{equation*}
\vect{A}\vect{x}=\vect{b}
\end{equation*}
The determinant of coefficient matrix is \[ \dt{A}=2\cdot (-2) - 7\cdot 4= -32 \neq 0 \] Thus, the equation has a unique solution, which is
\[ \vect{x}=\inverse{A}\vect{b}=\frac{1}{-32} \smtrx{-2,-4\\-7,2}\cvect{8,4}=\cvect{1,3/2} \]
\end{example}
\subsection{Crammer's rule}
Suppose we need to solve the matrix equation $\vect{A}\vect{x}=\vect{b}$ where $\vect{A}$ is an n-square matrix, $\vect{x}=\rvect{x_1,x_2,\ldots ,x_n}^T$ and $\vect{b}=\rvect{b_1,b_2,\ldots ,b_n}^T$. Let $\vect{A}^{(j)}$ be a matrix $\vect{A}$ but replace \emph{j}th column with $\vect{b}$. Then we have \[ x_j=\frac{\dt{\vect{A}^{(j)}}}{\dt{A}} \] Like Inverse matrix, this method only works if the determinant of the coefficient matrix is nonzero.
\begin{example}
The system of equation \eqref{apple} can solved using Crammer's rule as follow:
\begin{meq*}
    \vect{A} &=& \smtrx{2,4\\7,-2}, \quad \dt{A}=-32 \\
    \dt{A^{(1)}} &=& \dmtrx{8,4\\4,-2}=-32 \Rightarrow x_1=\frac{-32}{-32}=1 \\
    \dt{A^{(2)}} &=& \dmtrx{2,7\\8,4}=-48 \Rightarrow x_2=\frac{-48}{-32}=\frac{3}{2}
\end{meq*}
\end{example}
\subsection{Gaussian elimination}
Gaussian elimination is usually understood as a sequence of operations performed on the corresponding matrix of coefficients. This method can be used to solve system of equations, find the rank of a matrix, calculate the determinant of a matrix, and calculate the inverse of an invertible square matrix.\\

To perform Gaussian elimination, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:
\begin{itemize}
\item Swap the positions of two rows.
\item Multiply a row by a nonzero scalar.
\item Add to one row a scalar multiple of another.
\end{itemize}
These operations are already shown in section \ref{sec:Determinants} as properties of determinants.\par
\begin{example}
The system of equation \eqref{apple} can solved using Gaussian elimination. Let define matrix $\vect{A}$, $\vect{x}$, and $\vect{b}$ as follow:
\[ \vect{A}=\smtrx{2,4\\ 7,-2} \quad \vect{x}=\cvect{x_1,x_2} \quad \vect{b}=\cvect{8,4} \]
First, we create the augmented matrix which is formed by merging matrix $\vect{A}$ and $\vect{b}$.
\begin{equation*}
    \left[{\begin{array}{cc|c}
        2&4&8 \\ 7&-2&4
    \end{array}}\right]
\end{equation*}
Swap the positions of two rows, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        7&-2&4 \\ 2&4&8
    \end{array}}\right]
\end{equation*}
Multiply the first row by 1/7, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 2&4&8
    \end{array}}\right]
\end{equation*}
Replace the second row by $R_2 \leftarrow R_2-2R_1$
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 0&32/7&48/7
    \end{array}}\right]
\end{equation*}
Multiply the first row by 32/7, we have:
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&-2/7&4/7 \\ 0&1&48/32
    \end{array}}\right]
\end{equation*}
Replace the first row by $R_1 \leftarrow R_2+ \frac{2}{7} R_1$
\begin{equation*}
    \left[{\begin{array}{cc|c}
        1&0&1 \\ 0&1&48/32
    \end{array}}\right]
\end{equation*}
Thus, $x_1=1$ and $x_2=48/32$.
\end{example}
\section{Linear least squares}
\textbf{Problem:} Let $\vect{A}$ be an $m\times n$ matrix, $\vect{x}$ be an $n\times 1$ matrix and b be an $m\times 1$ matrix. Solve the matrix equation $\vect{A}\vect{x}=\vect{b}$.\\

\textbf{Solution:} If $m=n$, we can use three methods mentioned in section \ref{linear-eq}. However, if $m>n$, the solution usually does not exist. In that case, if $\dt{\vect{A}} \neq 0$, then

\begin{equation*}
\trans{A}\vect{A}\vect{x}=\trans{A}\vect{b}
\end{equation*}

\begin{equation}\label{least-square}
\vect{x}=\left( \trans{A}\vect{A} \right)^{-1} \trans{A}\vect{b}
\end{equation}

The matrix equation now can be solved with the minimum error, meaning $\norm{\vect{A}\vect{x}-\vect{b}}$ is minimum. Using formula \eqref{least-square} to solve a system of equations is called The method of linear least squares.

\begin{exercise}
Suppose we want to draw a best fitting line through three points (4,-2), (5,0), (5,-1), (6,4), (7,5) and (8,5) so a linear function $y=t+kx$ should be given. Determine this function by means of the Method of Least Squares (LSM). Perform calculations by SAGE then plot points and the line in the same coordinate system.
\end{exercise}

\begin{solution}\label{least-square}
The linear function $y=kx+t$ should satisfies the following system of equations with the minimum error:
\begin{equation}
\label{LSM-linear}
\begin{cases}
4k+t &= -2 \\
5k+t &= 0 \\
5k+t &= -1 \\
6k+t &= 4 \\
7k+t &= 5 \\
8k+t &= 5
\end{cases}
\end{equation}
The equivalent matrix equation of \eqref{LSM-linear} is $\vect{A}\vect{x}=\vect{b}$, where
\[ \vect{A}=\smtrx{4,1\\5,1\\5,1\\6,1\\7,1\\8,1} \quad \vect{x}=\cvect{k,t} \quad \vect{b}=\cvect{-2,0,-1,4,5,5} \]
Using formula \eqref{least-square}, we now can perform calculations by SAGE as follow:
\begin{verbatim}
A=matrix([[4,1], [5,1], [5,1], [6,1], [7,1], [8,1]])
b=matrix([ [-2,0,-1,4,5,5] ]).T
x=(A.T*A).inverse() * (A.T*b)

k=x[0][0]
t=x[1][0]
z=var("z")

S=plot(k*z+t, (z,-1,9))
P = scatter_plot([[4,-2], [5,0], [5,-1], [6,4], [7,5], [8,5]])
show(S+P)
\end{verbatim}
\begin{tikzpicture}
\begin{axis}
[%The axis
    axis lines = middle,
    xlabel = {$x$}, ylabel = {$y$},
    xmin=-3,ymin=-3,xmax=10,ymax=6
]
\addplot [%The line
    domain=3:10,
    color=red,
]
{131/65*x-129/13};
\addplot[color=blue,mark=square]%The points
coordinates {
(4,-2) (5,0) (5,-1) (6,4) (7,5) (8,5)
};
\end{axis}
\end{tikzpicture}
\end{solution}

\begin{exercise}
Suppose we want to draw a best 4th order polynomial line through 6 points $(7,9),(6,12),(4,4),(2,-1),(-1,0),(6,16)$. Determine this function by means of the Method of Least Squares (LSM). Perform calculations by SAGE and plot the points and the line in the same coordinate system.
\end{exercise}

\begin{solution}
We need to find the coefficients of the following polynomial
\[ y=mx^4+nx^3+px^2+qx+r \]
Substitue $x$ and $y$ to this polynomial, we obtain a system of equations:
\begin{equation*}
\begin{cases}
2401m+343n+49p+7q+r &=9\\
1296m+216n+36p+6q+r &=12\\
256m+64n+16p+4q+r &=4\\
16m+8n+4p+2q+r &=-1\\
m-n+p-q+r&=0\\
1296m+216n+36p+6q+r &=16
\end{cases}
\end{equation*}
,which is equivalent to the follwoing matrix equation
\[ \smtrx{2401,343,49,7,1\\1296,216,36,6,1\\256,64,16,4,1\\16,8,4,2,1\\1,-1,1,-1,1\\1296,216,36,6,1} \cvect{m,n,p,q,r} = \cvect{9,12,4,-1,0,16} \]
Using formula \eqref{least-square}, we now can perform calculations by SAGE as follow:
\begin{verbatim}
A=matrix([[2401,343,49,7,1],[1296,216,36,6,1],[256,64,16,4,1],
        [16,8,4,2,1],[1,-1,1,-1,1],[1296,216,36,6,1]])
b=matrix([[9,12,4,-1,0,16]]).T
x=(A.T*A).inverse() * (A.T*b)

m=x[0][0]
n=x[1][0]
p=x[2][0]
q=x[3][0]
r=x[4][0]

z=var("z")
S=plot(m*z**4+n*z**3+p*z*z+q*z+r, (z,-2,8))
P = scatter_plot([[7,9],[6,12],[4,4],[2,-1],[-1,0],[6,16]])
show(S+P)
\end{verbatim}
\end{solution}


text:
\begin{abstract}
\section{Motivation:}
Genome-wide association studies can potentially unravel the mechanisms behind complex traits and common genetic diseases. Despite the valuable results produced thus far, many questions remain unanswered. For instance, which specific genetic compounds are linked to the risk of the disease under investigation; what biological mechanism do they act through; or how do they interact with environmental and other external factors?
The driving force of computational biology is the constantly growing amount of big data generated by high-throughput technologies. A practical framework that can deal with this abundance of information and that consent to discovering genetic associations and interactions is provided by means of networks.
Unfortunately, high dimensionality, the presence of noise and the geometry of data can make the aforementioned problem extremely challenging.
We propose a penalised linear regression approach that can deal with the aforementioned issues that affect genetic data. We analyse the gene expression profiles of individuals with a common trait to infer the network structure of interactions among genes.
\section{Results:}
The permutation-based approach leads to more stable and reliable networks inferred from synthetic microarray data. We show that a higher number of permutations determines the number of predicted edges, improves the overall sensitivity and controls the number of false positives.

\section{Availability:}
availability of source code upon request

\section{Contact:} \href{francesco.gadaleta@ulg.ac.be}{francesco.gadaleta@ulg.ac.be}
\end{abstract}

max_stars_repo_path: LABnet bioinformatics/abstract.tex

max_stars_repo_name: worldofpiggy/academic-papers

max_issues_repo_path: LABnet bioinformatics/abstract.tex

max_issues_repo_name: worldofpiggy/academic-papers

max_forks_repo_path: LABnet bioinformatics/abstract.tex

max_forks_repo_name: worldofpiggy/academic-papers