\def\hs{\hspace{0.4 cm}}

\documentclass{beamer}

\usetheme{Warsaw}
\usecolortheme{beaver}
\setbeamertemplate{footline}[page number]
\beamertemplatenavigationsymbolsempty

\title{Threshold Signatures, Accountability and More}
\author{Andrew Poelstra}
\institute{\texttt{schnorr@wpsoftware.net}}
\date{December 20, 2018}

\usepackage{amsfonts,amsmath,latexsym,color,epsfig,graphicx,multirow,rotating}
\usepackage{anyfontsize}

\begin{document}
\frame{ \frametitle{}
\begin{center}
{\color{darkred} \Huge Threshold Signatures {\Large and} Accountability\\}~\\
Andrew Poelstra\\
{\tiny Director of Research, Blockstream}\\~\\
4 February 2019
\end{center} }

\newcommand{\G}{{\color{black}G}}
\newcommand{\wG}{{\color{white}G}}
\newcommand{\mui}{{\color{blue}\mu_i}}
\newcommand{\wmui}{{\color{white}\mu_i}}
\newcommand{\m}{{\color{blue}m}}
\newcommand{\x}{{\color{red}x}}
\renewcommand{\t}{{\color{red}t}}
\renewcommand{\k}{{\color{red}k}}
\renewcommand{\P}{{\color{blue}P}}
\newcommand{\R}{{\color{blue}R}}
\newcommand{\Rz}{{\color{purple}R^0}}
\renewcommand{\c}{{\color{purple}c}}
\newcommand{\T}{{\color{blue}T}}
\newcommand{\s}{{\color{blue}s}}
\newcommand{\e}{{\color{blue}e}}

\newcommand{\gm}[1]{{\color{red}\gamma_{#1}}}
\newcommand{\poly}[1]{{\color{red}p_{#1}}}
\newcommand{\share}[2]{{\color{red}\zeta_{#1,#2}}}
\newcommand{\boxthing}{{\color{red}\left[\vdots\qquad\vdots\right]_j}}

\frame
{
  \frametitle{Schnorr Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s\wG &= \k\wG + \e\x\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Schnorr Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s\G &= \k\G + \e\x\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Sign-to-Contract}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \Rz &= \k\G\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s\wG &= (\k + H(\Rz\|\c))\wG + \e\x\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Sign-to-Contract}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \Rz &= \k\G\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s\G &= (\k + H(\Rz\|\c))\G + \e\x\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Sign-to-Contract Replay Attack}
Suppose $\k = H(\x\|m)$.
  \begin{center}
  \begin{align*}
      \s &= (\k + H(\Rz\|\c)) + \e\x\\
      -~\s &= (\k + H(\Rz\|\c')) + \e'\x\\
\hline\\
      0 &= H(\Rz\|\c) - H(\Rz\|\c') + (\e - \e')\x
  \end{align*}
  \end{center}~\\
So we'd better have $\k = H(\x\|m\|\c)$!
}
\frame
{
  \frametitle{Sign-to-Contract as an Anti-Nonce-Sidechannel Measure}
  \begin{itemize}
  \item If the hardware device knows $\c$ before producing $\Rz$ it can grind $\k$
      so that $(k + H(\Rz\|\c))$ has detectable bias.\\~\\
  \item If it doesn't know $\c$ how can it prevent replay attacks?\\~\\
  \item Send hardware device $H(\c)$ and receive $\Rz$ before giving it $\c$.\\~\\
  \item Then $\k = H(\x\|m\|H(\c))$.
  \end{itemize}
}



\frame
{
  \frametitle{Schnorr Multisignatures}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P_i &= \wmui\x_i\G\\
      \P &= \sum \P_i\\
\\
      \R_i &= \k_i\G\\
      \R &= \sum \R_i\\
      \e &= H(\P, \R, \m) \\
      \s_i\wG &= \k_i\wG + \e\wmui\x_i\wG\\
      \s\wG &= \sum k_i\wG + \sum \wmui \e\x_i\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Schnorr Multisignatures}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P_i &= \wmui\x_i\G\\
      \P &= \sum \P_i\\
\\
      \R_i &= \k_i\G\\
      \R &= \sum \R_i\\
      \e &= H(\P, \R, \m) \\
      \s_i\G &= \k_i\G + \e\wmui\x_i\G\\
      \s\G &= \sum k_i\G + \sum\wmui \e\x_i\G
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Schnorr Multisignatures}
  \begin{center}
  \begin{align*}
      \mui &= H\left[H(\P_1\|\P_2\|\cdots\|\P_n)\|i\right]\\
      \P_i &= \mui\x_i\G\\
      \P &= \sum \P_i\\
\\
      \R_i &= \k_i\G\\
      \R &= \sum \R_i\\
      \e &= H(\P, \R, \m) \\
      \s_i\G &= \k_i\G + \e\wmui\x_i\G\\
      \s\G &= \sum k_i\G + \sum\mui \e\x_i\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Verifiable Secret Sharing}
Suppose a party with secret $\x_i$ wants to split her secret such that $k$ parties
may produce a signature with it.
  \begin{center}
  \begin{align*}
    \poly{i}(X) &= \x_i + \gm{i,1} X + \gm{i,2} X^2 + \cdots + \gm{i,k} X^{k-1}\\
\\
    \share{i}{j}\wG &= \poly{i}(j)\wG	\\
                &= \x_i\wG + j\gm{i,1}\wG + j^2\gm{i,2} \wG + \cdots + j^{k-1}\gm{i,k-1} \wG	\\
\\
    \poly{i}(0) &= \x_i	\\
                &= \sum_{j\in\textnormal{signers}} \lambda_{i,j}\share{i}{j}
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Verifiable Secret Sharing}
Suppose a party with secret $\x_i$ wants to split her secret such that $k$ parties
may produce a signature with it.
  \begin{center}
  \begin{align*}
    \poly{i}(X) &= \x_i + \gm{i,1} X + \gm{i,2} X^2 + \cdots + \gm{i,k} X^{k-1}\\
\\
    \share{i}{j}\G &= \poly{i}(j)\G	\\
                &= \x_i\G + j\gm{i,1} \G + j^2\gm{i,2} \G + \cdots + j^{k-1}\gm{i,k-1} \G	\\
\\
    \poly{i}(0) &= \x_i	\\
                &= \sum_{j\in\textnormal{signers}} \lambda_{i,j}\share{i}{j}
  \end{align*}
  \end{center}
}
%\frame{ \frametitle{~} \begin{center} \includegraphics[scale=0.90]{matt-green-twitter-troll.png} \end{center} }

\frame
{
  \frametitle{Verifiable Secret Sharing}
  \begin{center}
  \begin{align*}
    \x G &= \sum_{i\in\textnormal{everyone}}\mui\x_i\G\\
         &= \sum_{i\in\textnormal{everyone}}\mui\poly{i}(0)\G\\
         &= \sum_{i\in\textnormal{everyone}}\mui \sum_{j\in\textnormal{signers}} \lambda_{i,j}\share{i}{j}\G\\
         &= \sum_{j\in\textnormal{signers}}\left[\sum_{i\in\textnormal{everyone}} \lambda_{i,j}\mui\share{i}{j}\G\right]\\
         &= \sum_{j\in\textnormal{signers}}\boxthing
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Signing With VSS}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P &= \sum_j \boxthing\G\\
\\
      \R_j &= \k_j\G\\
      \R &= \sum \R_j\\
      \e &= H(\P, \R, \m) \\
      \s_j\wG &= \k_j\wG + \e\boxthing\wG\\
      \s\wG &= \sum k_j\wG + \sum \e\boxthing\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Signing With VSS}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P &= \sum_j \boxthing\G\\
\\
      \R_j &= \k_j\G\\
      \R &= \sum \R_j\\
      \e &= H(\P, \R, \m) \\
      \s_j\G &= \k_j\G + \e\boxthing\G\\
      \s\G &= \sum k_j\G + \sum \e\boxthing\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Accountability}
  \begin{itemize}
  \item Recall the equation $\P = \sum_{j\in\textnormal{signers}} \boxthing$.\\~\\
  \item What is this set ``signers''?\\~\\
  \item In fact any set will do; $\lambda_{i,j}$ depends on the particular set but nothing else does.\\~\\
  \item Importantly \textbf{the signature does not depend on this set}. Such signatures are \emph{unaccountable}.
  \end{itemize}
}

\frame
{
  \frametitle{Accountability}
  \begin{itemize}
  \item What does an accountable signature look like?\\~\\
  \item Satoshi-style ``concatenate individual signatures'' threshold signatures, for one.\\~\\
  \item Can we get a constant-size accountable signature? I doubt it.\\~\\
  \end{itemize}
}

\frame
{
  \frametitle{Accountability}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P &= \sum_j \boxthing\G\\
      \R_j &= \k_j\G\\
      \Rz &= \sum \R_j\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s_j\wG &= \k_j\wG + \e\boxthing\wG\\
      \s\wG &= \sum k_j\wG + \sum \e\boxthing\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Accountability}
  \begin{center}
  \begin{align*}
      \wmui &{\color{white}= H\left[H(P_1\|P_2\|\cdots\|P_n)\|i\right]}\\
      \P &= \sum_j \boxthing\G\\
      \R_j &= \k_j\G\\
      \Rz &= \sum \R_j\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s_j\G &= \k_j\G + e\boxthing\G\\
      \s\G &= \sum k_j\G + \sum \e\boxthing\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Semi-Accountability}
  \begin{itemize}
  \item Suppose that $\c$ commits to an accountable threshold signature.\\~\\
  \item Then we have an unaccountable signature that \emph{commits to an accountable signature}.\\~\\
  \item Signers can refuse to participate if this commitment is missing or invalid; hardware enforced.
  \end{itemize}
}

\frame
{
  \frametitle{Semi-Accountability}
  \begin{itemize}
  \item Then assuming at least one party in the signature is honest and will publish the committed accountable signature, the result is ``accountable''.\\~\\
  \item (Of course, this doesn't help if nobody is honest, which is often what you need accountability for\ldots)
  \end{itemize}
}

\frame
{
  \frametitle{Open Questions}
  \begin{itemize}
  \item Can we construct a commitment that can be reconstructed or brute-forced by third parties?\\~\\
  \item Can we get deniability, \emph{i.e.} can a non-participant prove non-participation without help?\\~\\
  \item Extension to BLS which has no space for committing data?
  \end{itemize}
}

\frame
{
    \frametitle{~}
    \begin{center}
    Thank you.
    ~\\~\\~\\
    Andrew Poelstra\\
    \texttt{clauspschnorr@wpsoftware.net}
    \end{center}
}

\end{document}